发布时间：2025-06-24 18:12:55  作者：北方职教升学中心  阅读量：429


下面是希尔排序时间复杂度的估算：

外层循环：

外层循环的时间复杂度可以直接给出为：O ( l o g 2 n ) O(log_2n) O(log2​n)或者 O ( l o g 3 n ) O(log_3 n) O(log3​n)，即O ( l o g n ) O(logn) O(logn)

内层循环：

在这里插入图片描述

假设一共有n个数据，合计gap组，则每组为n/gap个；在每组中，插入移动的次数最坏的情况下为

1 + 2 + 3 + . . . . + ( n g a p − 1 ) 1 + 2 + 3 + .... + ({nover gap} - 1) 1+2+3+....+(gapn​−1)，一共是gap组，因此：

总计最坏情况下移动总数为：g a p ∗ [ 1 + 2 + 3 + . . . . + ( n g a p − 1 ) ] gap∗[1 + 2 + 3 + .... + ({n over gap} - 1)] gap∗[1+2+3+....+(gapn​−1)]

gap取值有（以除3为例）：n/3 n/9 n/27 … 2 1

  • 当gap为n/3时，移动总数为：n 3 ∗ ( 1 + 2 ) = n {n over 3}*(1+2)=n 3n​∗(1+2)=n

  • 当gap为n/9时，移动总数为：n 9 ∗ ( 1 + 2 + 3 + . . . . + 8 ) = n 9 ∗ 8 ( 1 + 8 ) 2 = 4 n {n over 9}*(1+2+3+....+8)={n over 9}*{8(1+8) over 2}=4n 9n​∗(1+2+3+....+8)=9n​∗28(1+8)​=4n

  • 最后一躺，gap=1即直接插入排序，内层循环排序消耗为n

通过以上的分析，可以画出这样的图：

在这里插入图片描述

因此，希尔排序在最初和最后的排序的次数都为n，即前一阶段排序次数是逐渐上升的状态，当到达某一顶点时，排序次数逐渐下降至n，而该顶点的计算暂时无法给出具体的计算过程

希尔排序时间复杂度不好计算，因为gap的取值很多，导致很难去计算，因此很多书中给出的希尔排序的时间复杂度都不固定。这样整体而言，可以达到优化的效果。是第一个突破O ( n 2 ) O(n^2) O(n2)的排序算法，它与插入排序的不同之处在于，它会优先比较距离较远的元素。

也可以点点关注，避免以后找不到我哦！

Crossoads主页还有很多有趣的文章，欢迎小伙伴们前去点评，您的支持就是作者前进的动力！

带你初步了解排序算法：https://blog.csdn.net/2301_80191662/article/details/142211265
直接插入排序：https://blog.csdn.net/2301_80191662/article/details/142300973
希尔排序：https://blog.csdn.net/2301_80191662/article/details/142302553
直接选择排序：https://blog.csdn.net/2301_80191662/article/details/142312028
堆排序：https://blog.csdn.net/2301_80191662/article/details/142312338
冒泡排序：https://blog.csdn.net/2301_80191662/article/details/142324131
快速排序：https://blog.csdn.net/2301_80191662/article/details/142324307
归并排序：https://blog.csdn.net/2301_80191662/article/details/142350640
计数排序：https://blog.csdn.net/2301_80191662/article/details/142350741
桶排序：https://blog.csdn.net/2301_80191662/article/details/142375338
基数排序：https://blog.csdn.net/2301_80191662/article/details/142375592
十大经典排序算法总结与分析：https://blog.csdn.net/2301_80191662/article/details/142211564

在这里插入图片描述

空间复杂度：

希尔排序的空间复杂度为O ( 1 ) O(1) O(1)。

2. 算法步骤

排序对不相邻的记录进行比较和移动：

  1. 将待排序序列分为若干子序列（每个子序列的元素在原始数组中间距相同）；
  2. 对这些子序列进行插入排序；
  3. 减小每个子序列中元素之间的间距，重复上述过程直至间距减少为1。动态定义间隔序列的算法是《算法（第4版）》的合著者Robert Sedgewick提出的。当g a p = = 1 gap == 1 gap==1时，数组已经接近有序的了，这样就会很快。《数据结构(C语言版)》— 严蔚敏书中给出的时间复杂度为：

    在这里插入图片描述

    5. 算法分析

    希尔排序的核心在于间隔序列的设定。

    它是在直接插入排序算法的基础上进行改进而来的，综合来说它的效率肯定是要高于直接入排序算法的。

    希尔排序的平均时间复杂度和最坏时间复杂度与间距序列的选取有关。

    在这里插入图片描述

    文章目录

    • 1. 定义
    • 2. 算法步骤
    • 3. 动图演示
    • 4. 性质
    • 5. 算法分析
    • 6. 代码实现
      • C语言
      • Python
      • Java
      • C++
      • Go
    • 结语

    1. 定义

    希尔排序（英语：Shell sort），也称为缩小增量排序法，是[直接插入排序]的一种改进版本。

    时间复杂度：

    希尔排序的最优时间复杂度为O ( n ) O(n) O(n)。

    6. 代码实现

    C语言

    voidShellSort(int*a,intn){intgap =n;while(gap >1){//推荐写法：除3gap =gap /3+1;for(inti =0;i <n -gap;i++){intend =i;inttmp =a[end +gap];while(end >=0){if(a[end]>tmp){a[end +gap]=a[end];end -=gap;}else{break;}}a[end +gap]=tmp;}}}

    Python

    defshellSort(arr):importmath    gap=1while(gap <len(arr)/3):gap =gap*3+1whilegap >0:fori inrange(gap,len(arr)):temp =arr[i]j =i-gap            whilej >=0andarr[j]>temp:arr[j+gap]=arr[j]j-=gap            arr[j+gap]=temp        gap =math.floor(gap/3)returnarr

    Java

    publicstaticvoidshellSort(int[]arr){intlength =arr.length;inttemp;for(intstep =length /2;step >=1;step /=2){for(inti =step;i <length;i++){temp =arr[i];intj =i -step;while(j >=0&&arr[j]>temp){arr[j +step]=arr[j];j -=step;}arr[j +step]=temp;}}}

    C++

    template<typename T>voidshell_sort(T array[],intlength){inth =1;while(h <length /3){h =3*h +1;}while(h >=1){for(inti =h;i <length;i++){for(intj =i;j >=h &&array[j]<array[j -h];j -=h){std::swap(array[j],array[j -h]);}}h =h /3;}}

    Go

    funcshellSort(arr []int)[]int{length :=len(arr)gap :=1forgap <length/3{gap =gap*3+1}forgap >0{fori :=gap;i <length;i++{temp :=arr[i]j :=i -gap                        forj >=0&&arr[j]>temp {arr[j+gap]=arr[j]j -=gap                        }arr[j+gap]=temp                }gap =gap /3}returnarr}

    结语

    今天的分享到这里就结束啦！如果觉得文章还不错的话，可以三连支持一下。设间距序列为H H H，有H H H的两种经典选取方式，这两种选取方式均使得排序算法的复杂度降为级别O ( n 2 ) O(n^2) O(n2)。

    4. 性质

    稳定性：

    希尔排序是一种不稳定的排序算法。希尔排序以它的发明者希尔（英语：Donald Shell）命名。既可以提前设定好间隔序列，也可以动态的定义间隔序列。

    希尔排序的平均时间复杂度可以降为O ( n 1.3 ) O(n^{1.3}) O(n1.3)。

    在这里插入图片描述

    当g a p > 1 gap > 1 gap>1时都是预排序，目的是让数组更接近于有序。

3. 动图演示

在这里插入图片描述

基本思想：先选定一个整数（通常是g a p = n / 3 + 1 gap = n/3+1 gap=n/3+1），把待排序文件所有记录分成各组，所有的距离相等的记录分在同一组内，并对每一组内的记录进行排序，然后g a p = g a p / 3 + 1 gap=gap/3+1 gap=gap/3+1得到下一个整数，再将数组分成各组，进行插入排序，当g a p = 1 gap=1 gap=1时，就相当于直接插入排序。