【排序】希尔排序算法

特别说明：

对于算法，重在理解其思想、解决问题的方法，思路。因此，以下内容全都假定待排序序列的存储结构为：顺序存储结构。

希尔排序算法摘要：

希尔排序又称为“缩小增量排序”。直接插入排序算法在效率上虽说没办法突破 $O(n^{2})$ ，但其在少量数据或待排序列基本有序的情况下，效率却是非常高效的。因此，为进一步提高排序算法的效率，就需要适当地构造前述的那些条件。希尔排序就是第一批突破排序算法时间复杂度 $O(n^{2})$ 的一个算法。希尔排序算法算是一种属于插入排序类别的方法。

希尔排序算法思想：

算法总体描述：将待排序序列按指定步长，划分成多个子序列，分别对每个子序列应用插入排序进行排序，待全部子序列全部排序完成后，将步长缩小后，再次重新划分子序列并重新排序。如此重复，直至步长降至1为止。

具体描述：

假设待排序序列为 $R_{1..n}$ 。即为： $R_{1}$ 、 $R_{2}$ 、 $R_{3}$ 、...、 $R_{n - 1}$ 、 $R_{n}$ ，步长增量 step 初始为 $\left \lfloor n/2 \right \rfloor$ ，以后每将缩短为 step = $\left \lfloor step/2 \right \rfloor$ ，则算法可描述如下：

01.step = $\left \lfloor n/2 \right \rfloor$ ；

02.将整个待排序序列划分为以下 $\left \lfloor n/step \right \rfloor$ 个子序列：

{ $R_{1}$ 、 $R_{1 + step}$ 、 $R_{1 + 2 \times step}$ 、 $R_{1 + 3 \times step}$ 、...、 $R_{1 + i \times step}$ }、

{ $R_{2 + 1 \times step}$ 、 $R_{2 + 2 \times step}$ 、 $R_{2 + 3 \times step}$ 、...、 $R_{2 + i \times step}$ }、

...、

{ $R_{(step - 1) + 1 \times step}$ 、 $R_{(step - 1) + 2 \times step}$ 、 $R_{(step - 1) + 3 \times step}$ 、...、 $R_{(step - 1) + i \times step}$ }；

注意：以上各子序列的最后一个元素的下标均不超过 n。即：

$1 + i \times step$ $\leqslant$ n；

$2 + i \times step$ $\leqslant$ n；

....

$(step - 1) + i \times step$ $\leqslant$ n；

03.分别对以上划分好的各子序列进行插入排序；

04.如果 step = 1，则排序完成退出；

05.否则，缩小步长增量 step = $\left \lfloor step/2 \right \rfloor$ ，重新回到 02 点执行；

下面简要分析下，为何希尔排序能成功构造出前文摘要部分所述的条件。首先，将待排序序列按步长划分成多个子序列，则每个子序列的个数就比原子序列少 step 倍，因此，执行插入排序时的效率会比对 n 个数的序列来的高。其次，虽说随着步长 step 的不断缩小，每个子序列的数据量逐渐增大，但每执行完一趟后，待排序序列相比之前一趟都更为有序了一些，此时执行起插入排序，其效率又会有所提高。因此，希尔排序就是如此巧妙地构造出了前文摘要所述的两个条件：少数据量或者待排序序列基本有序。从而提高插入排序的效率，最终提高希尔排序的效率。

希尔排序算法编码参考如下：

 1 // 
 2 // summary     : 希尔排序算法.(希尔排序其实算是对直接插入排序算法的改进)
 3 // in param    : seqlist 待排序列表.同时也是排完序列表.
 4 // in param    : nLen 列表长度
 5 // out param   : --
 6 // return      : --
 7 // !!!note       : 01.以下实现均假设一切输入数据都合法.即:内部不对参数全法性进行校验,默认它们全都合法有效.
 8 //               02.排序开始前 seqlist 是无序的,排序结束后 seqlist 是有序的.
 9 //               03.该实现版本,步长每次折半.
10 void shell_sort(int seqlist[/*nLen*/], const int nLen) {
11     auto nTemp     = 0;
12     auto nStep     = nLen >> 1;
13     auto nLoopIdx  = 0; // 趟循环
14     auto nOuterIdx = 0;
15     auto nInnerIdx = 0;
16     while (nStep > 0) {
17         for (nLoopIdx = 0; nLoopIdx < nStep; ++nLoopIdx) {
18             for (nOuterIdx = nLoopIdx + nStep; nOuterIdx < nLen; nOuterIdx += nStep) {
19                 nTemp = seqlist[nOuterIdx];
20                 for (nInnerIdx = nOuterIdx; nInnerIdx > 0; nInnerIdx -= nStep) {
21                     if (seqlist[nInnerIdx] >= seqlist[nInnerIdx - nStep]) {
22                         break;
23                     }
24                     seqlist[nInnerIdx] = seqlist[nInnerIdx - nStep];
25                 }
26                 seqlist[nInnerIdx] = nTemp;
27             }
28         }
29         nStep = nStep >> 1;
30     }
31 }

希尔排序算法编码参考

上面编码其实可以使用3个循环即可实现希尔排序算法，但从理解思想的角度看，上述编码更容易理解些(还是那句话，本人是重要理解算法的思想，解决问题的思路、方法，因此并没有在编码简洁等方面做太多的完善，有些时间，算法写的过于简洁，反而不容易理解)。

算法分析：

关于希尔排序算法的时间复杂度是与步长的取定有关系的，目前在数学上还没有明确的论证。

在严蔚敏的书中述：经过大量实验，有的人认为增量序列公式为 $\Delta (k)$ = $2^{t - k + 1} - 1$ 时，希尔排序时间复杂度为 $O(n^{3/2})$ ，其中 t 为排序的趟数，1 $\leqslant$ k $\leqslant$ t $\leqslant$ $\left \lfloor log_2^{(n + 1)} \right \rfloor$ 。

Wiki中描述：当步长取 step = $2^{k} - 1$ 时，时间复杂度为 $O(n^{3/2})$ 。

在其他数据结构书本中(如：《大话数据结构》)，则描述时间复杂度为 $O(nlogn)$ 。

在其他有关该算法描述的资料上，如：Web上等，有的也是直接描述为 $O(nlogn)$ 。

在算导中倒没有见到对Shell sort的内容，所以有点可惜。因为算导是比较偏向理论性论述、论证的一本书籍，算是比较权威的。

不论怎么样，目前认为shell sort算法在最好情况下的时间复杂度为 $O(n^{3/2})$ ，最坏情况下为 $O(n^{2})$ 。在少数据量的情况下，shell sort 算是非常不错的一个排序算。且相较插入排序算法，其主要操作是在数据的比较上，数据移动操作相对更少。但希尔排序算法是不稳定排序算法，而直接插入排序算法却是稳定的。二者需要的辅助空间都是 $O(1)$ 。另外，一定要注意：不论步长计算取什么样的公式，该公式都要保证最后一次的步长值，必需为 1。