希尔排序是一种改进后的，更高效的插入排序

开篇

本文最好结合上篇插入排序阅读，因为希尔排序其实是插入排序改进而来的一种更高效的插入排序。此排序算法由 Donald Shell 于 1959 年提出，故得此名。

希尔排序是比普通插入排序要更高效一些的。从最坏时间复杂度来说，插入排序的最坏时间复杂度是平方级别的 О(n²)，而希尔排序的最坏时间复杂度为稍差于线性对数级别的 О(n log²n) ，好像有点绕，其实这等价于 О(n (log n)²) 。

希尔排序是如何改进插入排序的？答案是步长。什么意思呢？插入排序中元素值的比较和移动是按步长为1一个一个来的，希尔排序的改进思路是这样子，我们一开始先不以步长为1来操作数组中的元素。设现在数组的长度为 n，Donald Shell 当年建议我们一开始以 n/2 为步长对数组分组进行插入排序，然后再将步长除以 2 再对数组分组进行插入排序，步长最后总会迭代为 1。当步长变为 1 时，整个算法其实回到了最原始的插入排序（此步长序列通常不是效率最高的，这个我们后面会说到）。你会发现，希尔排序其实是递归地将数组分组反复对其进行插入排序，颇有点分而治之的意思。千万注意这里的按步长分组，这是理解希尔排序的关键所在，下面我偷懒直接把维基百科上的一个例子搬过来加深下理解。

设有这样一只整型数组： [13, 14, 94, 33, 82, 25, 59, 94, 65, 23, 45, 27, 73, 25, 39, 10]，如果我们以步长序列(5, 3, 1)对其进行希尔排序。刚开始，我们可以通过将这组数字放在有5列（也就是把数组中的数分成五组）的表中来更好地描述算法，这样数组元素看起来是这样的：

//表1，步长为 5 对数组元素分组。注意每列是一组，不是行！不是行！不是行！
13 14 94 33 82
25 59 94 65 23
45 27 73 25 39
10

这里千万注意是怎么对数组中的元素分组的，以步长为 5 对数组元素分组，不是连续的五个数为一组，而是：

[13, 14, 94, 33, 82, 25, 59, 94, 65, 23, 45, 27, 73, 25, 39, 10] -> 原数组
-13------------------25 -----------------45------------------10  -> [13, 25, 45, 10]，这是个步长为 5 的子数组
-----14------------------59 -----------------27----------------  -> [14, 59, 27]，    又是个步长为 5 的子数组
---------94------------------94 -----------------73------------  -> [94, 94, 73]，    又是个步长为 5 的子数组
-------------33------------------65 -----------------25--------  -> [33, 65, 25]，    又是个步长为 5 的子数组
-----------------82------------------23 -----------------39----  -> [82, 23, 39]，    又是个步长为 5 的子数组

这样给数组中元素分组的。

以步长为 5 对原数组进行插入排序，也就是对表 1 中每一列组成的子数组分别进行插入排序，待每列都排好序后数组变成：

10 14 73 25 23
13 27 94 33 39
25 59 94 65 82
45

上述四行数字，再依序接在一起时我们得到：[10, 14, 73, 25, 23, 13, 27, 94, 33, 39, 25, 59, 94, 65, 82, 45]，可发现这时10 已经移至数组整体有序时的正确位置了，然后再以3为步长进行分组：

10 14 73
25 23 13
27 94 33
39 25 59
94 65 82
45

排序后数组变成：

10 14 13
25 23 33
27 25 59
39 65 73
45 94 82
94

最后以1为步长进行排序，此时就是简单原始的插入排序了。

正文

OK 希望上面说那么多能让你完全理解希尔排序是怎么一回事。下面我们直接上代码，代码逻辑完全遵照上面所梳理逻辑而写，可能会显得有点啰嗦，但却易于理解（步长序列我们使用数组长度除以 2 迭代至 1）：

/**
     * @see: 希尔排序的 Java 实现
     * @param array: 待排序数组，我们采用原地排序
     */
    public static void sortShell(int[] array){
        //步长迭代，步长越大，分的子数组越多。步长为1时只有一个子数组，就是原数组本身，步长最小为 1
        for (int step = array.length/2; step >= 1; step /= 2){
            //从第一个元素始，按步长给数组元素分组分组，对每组进行插入排序
            for (int start = 0; start < step; start++){
                //对当前步长分出来的其中一个子数组单独做插入排序
                sortInsert(array, start, step);
            }
        }
    }

/**
     * @see: 插入排序的 Java 实现，只对数组中按步长分的子数组进行插入排序
     * @param array: 待排序数组，我们采用原地排序
     * @param start: 排序从数组的哪个元素开始
     * @param step: 遍历步长
     */
    public static void sortInsert(int[] array, int start, int step){
        // 开始对子数组进行插入排序排序，千万注意子数组是按步长分出来的，不是连续地分出来的
        // 从子数组第二个元素开始遍历，当然子数组长度可能小于2
        for (int slow = start + step; slow < array.length; slow += step){
            //待重新插入元素 array[slow]
            int insertion = array[slow];
            //内循环遍历，主要为确定待插入元素array[slow]的待插入位置
            int fast = slow - step;
            for (; fast >= 0; fast -= step){
                if (array[fast] > insertion){
                    array[fast + step] = array[fast];
                }else {
                    //待插入元素的待插入位置，总是从后往前看，最后一个值比它大的那个位置，
                    // 值比它大的那些值整体往后移动一个位置
                    break;
                }
            }
            //插入待插入元素，即最后一个值比它大的那个位置
            array[fast + step] = insertion;
        }
    }

以上代码关键是 sortShell 方法的实现，虽然多拆了个插入排序的子方法，不过还是比较容易理解的！

希尔排序的大体逻辑如此，不过上面代码为便于理解写得实在啰嗦，下面我们来写下跟以上写法等价的精简版本：

/**
     * @see: 希尔排序的 Java 实现，精简版
     * @param array: 待排序数组，我们采用原地排序
     */
    public static void sortShell__(int[] array){
        //步长迭代，步长越大，分的子数组越多。步长为1时只有一个子数组，就是原数组本身，步长最小为 1
        for (int step = array.length/2; step >= 1; step /= 2){
            //开始对当前步长下所有子数组进行插入排序排序，千万注意子数组是按步长分出来的，不是连续地分出来的
            //子数组从第二个元素开始遍历，等于步长的下标即为子数组第二个元素
            //下面这种写法循环嵌套少了一层，其实是交替排序每个子数组（同时开始插入排序各个子数组），与上面啰嗦的写法是等价的其实
            for (int slow = step; slow < array.length; slow ++){
                //待重新插入元素 array[slow]
                int insertion = array[slow];
                //内循环遍历，主要为确定待插入元素array[slow]的待插入位置
                int fast = slow - step;
                for (; fast >= 0; fast -= step){
                    if (array[fast] > insertion){
                        array[fast + step] = array[fast];
                    }else {
                        //待插入元素的待插入位置，总是从后往前看，最后一个值比它大的那个位置，
                        // 值比它大的那些值整体往后移动一个位置
                        break;
                    }
                }
                //插入待插入元素，即最后一个值比它大的那个位置
                array[fast + step] = insertion;
            }
        }
    }

结尾

希尔排序真的比插入排序更高效嘛？光看代码可能一头雾水，作者不打算在这里聊太多数学以证明希尔排序确实比插入排序更高效。事实是希尔排序确实比插入排序更高效，这点读者可结合插入排序的代码运行些测试用例自行对比。

希尔排序最重要的地方在于当用较小步长排序后，以前用较大步长的排序结果仍是有序的。比如，如果一个数列以步长5进行了排序然后再以步长3进行排序，那么该数列不仅是以步长3有序，而且是以步长5有序。如果不是这样，那么算法在迭代过程中会打乱以前的顺序，那就不会以如此短的时间完成排序了。

关于希尔排序的步长序列选择，上面代码所使用的使用数组长度除以 2 迭代至 1 是效率最佳的选择吗？

不是的。

希尔排序步长序列选择的问题就比较复杂了，本文且略过不谈，读者可求助伟大的互联网自行研究此问题！

下篇，我们聊聊堆排序，和优先队列。

完。