希尔排序(Shell Sort)算法是插入排序(Insertion Sort)算法的改良版。它解决了插入排序法一次只能把元素移动一个索引距离的问题,加入间距(gap)的概念来分批并分组完成插入排序法,有效提升原本插入排序法的速度。

希尔排序法(Shell Sort)

希尔排序法的概念

希尔排序法是基于插入排序法的算法,如果您还不了解插入排序法的话,请先参考这篇文章:

希尔排序法在插入排序法的基础上添加了间距(gap)的概念,使得插入排序法可以分组运行,并且元素的移动距离可以大于一。希尔排序法会对串行由大至小,小则至 1,来选择应用在插入排序法上的间距,这样一来就可以让串行后端比较小的元素,在被使用前面几次的大间距插入排序法排序之后,就先被移动到较前端的位置,使它们在最后的插入排序法中,不需要大老远的从后端以一次一个索引距离的方式来移动到前端。

希尔排序法的过程

假设现在有个数组数据,内容如下:

索引    0   1   2   3   4   5   6   7   8   9
数值   69  81  30  38   9   2  47  61  32  79

要如何将它递增排列呢?

如果在一开始我们选择使用的间距是 3 的话,希尔排序法则会以以下的分组方式来运行插入排序法:

索引    0   1   2   3   4   5   6   7   8   9
数值   69          38          47          79
           81           9          61
               30           2          32

所以经过排序后,数组内的元素分布如下:

索引    0   1   2   3   4   5   6   7   8   9
数值   38          47          69          79
            9          61          81
                2         30          32

索引    0   1   2   3   4   5   6   7   8   9
数值   38   9   2  47  61  30  69  81  32  79

如果在下一次我们选择使用的间距是 2 的话,希尔排序法则会以以下的分组方式来运行插入排序法:

索引    0   1   2   3   4   5   6   7   8   9
数值   38       2      61      69      32
            9      47      30      81      79

经过排序后,数组内的元素分布如下:

索引    0   1   2   3   4   5   6   7   8   9
数值    2      32      38      61      69
            9      30      47      79      81

索引    0   1   2   3   4   5   6   7   8   9
数值    2   9  32  30  38  47  61  79  69  81

最后使用间距 1,来完成排序:

索引    0   1   2   3   4   5   6   7   8   9
数值    2   9  30  32  38  47  61  69  79  81

希尔排序法的排序过程动画

希尔排序法的程序实作

希尔排序法的复杂度

以 #{{n}}# 来表示要排序的数据笔数。

项目 值 备注
最差时间复杂度 #{{O(n^2)}}#
#{{O(n \log^2 n)}}#
使用最差的间距。
使用 Pratt 的间距值(#{{2^p 3^q}}#)。
最佳时间复杂度 #{{O(n \log n)}}#
#{{O(n \log^2 n)}}#
使用最佳的间距。
使用 Pratt 的间距值(#{{2^p 3^q}}#)。
平均时间复杂度 ?
#{{O(n \log^2 n)}}#
根据间距值来决定。
使用 Pratt 的间距值(#{{2^p 3^q}}#)。
最差空间复杂度 #{{O(1)}}#
是否稳定 否 如果是普通的插入排序法则是稳定的。