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

Bertha 。 2023-07-20 05:59 4阅读 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

发表评论取消回复

表情：

评论列表（有 0 条评论，4人围观）

还没有评论，来说两句吧...

相关阅读

相关希尔排序(Shell Sort)

是插入排序经过改进之后的高效版本，也称缩小增量排序。 1959 年提出，是突破时间复杂度 O(n2) 的第一批算法之一。缩小增量排序的最优增量选择是一个数学难题，一般采用

约定不等于承诺〃/ 2023年07月25日 05:26/ 0 赞/ 14 阅读

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

import random import timeit def randomList(n): '''返回一个长度为n

Bertha 。/ 2023年07月20日 05:59/ 0 赞/ 5 阅读

相关 python希尔排序、归并排序

希尔排序，也称递减增量排序算法，是插入排序的一种更高效的改进版本。但希尔排序是非稳定排序算法。希尔排序的基本思想是：先将整个待排序的记录序列分割成为若干子序列分别进行直接插

Myth丶恋晨/ 2023年06月11日 10:21/ 0 赞/ 118 阅读

相关排序——希尔排序（Shell Sort）

希尔排序(Shell Sort)是插入排序的一种。也称缩小增量排序，是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。希尔排序是把记录按下标的一定增量分组，对

ゞ浴缸里的玫瑰/ 2022年08月20日 11:18/ 0 赞/ 149 阅读

相关 Python 算法 - 希尔排序

coding=utf-8 希尔排序 def shell_sort(lst=[]): """ 希尔排序(Shell

￡神魔★判官ぃ/ 2022年06月17日 03:55/ 0 赞/ 174 阅读

相关用python实现希尔排序(shell_sort)

def shell_sort(a): n = len(a) gap = n >> 1 gap是长度的一半 while

╰+攻爆jí腚メ/ 2022年06月07日 07:17/ 0 赞/ 215 阅读

相关【数据结构算法】：Python实现希尔排序

动图展示算法时间复杂度o(n1.3) ![849589-20180331170017421-364506073.gif][] python 希尔排序的思路就

分手后的思念是犯贱/ 2022年05月16日 00:42/ 0 赞/ 201 阅读

相关 python实现希尔排序算法

前面我们详细讲解了[希尔排序算法][Link 1]，现在我们直接上python代码 !/usr/bin/python -- coding: utf-8 --

秒速五厘米/ 2022年05月12日 09:50/ 0 赞/ 465 阅读

相关用Python实现希尔排序

1.希尔排序算法思想 > 将待排序数组按照步长gap进行分组，然后将每组的元素利用直接插入排序的方法进行排序；每次将gap折半减小，循环上述操作；当gap=1时，

偏执的太偏执、/ 2022年04月17日 02:10/ 0 赞/ 570 阅读

相关 Python之希尔排序

希尔排序：也称缩小增量排序，是插入排序的一种更高效的改进版本。希尔排序是非稳定排序算法。希尔排序的基本思想： 1、先将整个待排序列分割成若干个子序列(由相隔某个“

╰+哭是因爲堅強的太久メ/ 2022年02月20日 08:49/ 0 赞/ 194 阅读