python面试：实现希尔（shell）排序（python经典编程案例）

Bertha 。 2023-07-20 05:59 75阅读 0赞

import random
    import timeit
    
    
    def randomList(n):
        '''返回一个长度为n的整数列表，数据范围[0,1000) '''
        iList = []
        for i in range(n):
            iList.append(random.randrange(1000))
        return iList
    
    
    def shellSort(iList):
        if len(iList) <= 1:
            return iList
        # if len(iList) <= 20 :
        # n = 2
        # else:
        # n = len(iList)//10 #子序列的个数
        gap = len(iList)
        while gap > 1:
            # gap = gap//n
            gap = gap//2
            for i in range(gap, len(iList)):
                for j in range(i%gap, i, gap):
                    if iList[i] < iList[j]:
                        iList[i], iList[j] = iList[j], iList[i]
                        print(iList)
        return iList
    
    
    if __name__ == "__main__":
        iList = randomList(8)
        print(iList)
        print(shellSort(iList))
        print(timeit.timeit("shellSort(iList)", "from __main__ import shellSort,iList", number=100))

执行结果如下：

[651, 705, 67, 852, 566, 326, 61, 643]
    [566, 705, 67, 852, 651, 326, 61, 643]
    [566, 326, 67, 852, 651, 705, 61, 643]
    [566, 326, 61, 852, 651, 705, 67, 643]
    [566, 326, 61, 643, 651, 705, 67, 852]
    [61, 326, 566, 643, 651, 705, 67, 852]
    [61, 326, 67, 643, 651, 705, 566, 852]
    [61, 326, 67, 643, 566, 705, 651, 852]
    [61, 67, 326, 643, 566, 705, 651, 852]
    [61, 67, 326, 566, 643, 705, 651, 852]
    [61, 67, 326, 566, 643, 651, 705, 852]
    [61, 67, 326, 566, 643, 651, 705, 852]
    0.001073921999999998