我的《恋上数据结构》源码（第1季 + 第2季）：https://github.com/szluyu99/Data_Structure_Note

经典的十大排序算法！

前言

请==务必==看一下这个：排序算法前置知识+代码环境准备。

当上面的内容都准备好以后，那就开始希尔排序吧！

希尔排序思路

希尔排序把序列看作是一个矩阵，分成 𝑚 列，逐列进行排序

• 𝑚 从某个整数逐渐减为1
• 当 𝑚 为1时，整个序列将完全有序

因此，希尔排序也被称为递减增量排序（Diminishing Increment Sort）

矩阵的列数取决于步长序列（step sequence）：

• 不同的步长序列，执行效率也不同

实例图解

希尔本人给出的步长序列是 𝑛 / 2^𝑘^，比如 𝑛 为16时，步长序列是 { 1, 2, 4, 8 }

假设有如下序列：{ 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1 }

按照步长序列，首先分为8列，对每一列进行排序：

然后分为4列，对每一列进行排序：

然后分为 2 列，对每一列进行排序：

最后分为 1 列，变成升序序列。

不难看出来，从8列变为1列的过程中，逆序对的数量在逐渐减少

还记得插入排序的这个性质吗：

• 插入排序的时间复杂度与逆序对的数量成正比关系

逆序对的数量越多，插入排序的时间复杂度越高。

因此希尔排序底层一般使用插入排序对每一列进行排序，可以认为希尔排序是插入排序的改进版。

列的划分思路

假设有11个元素，步长序列是 {1, 2, 5}

假设元素在第 col 列、第 row 行，步长（总列数）是 step

• 那么这个元素在数组中的索引是 row * step + col
• 比如 9 在排序前是第 0 行、第 2 列，那么它排序前的索引是 0 * 5 + 2 = 2
• 比如 4 在排序前是第 1 行、第 2 列，那么它排序前的索引是 1 * 5 + 2 = 7

步长序列计算代码

使用希尔本人给出的步长序列： 𝑛 / 2^𝑘^ ，比如 𝑛 为16时，步长序列是 { 1, 2, 4, 8 }

/**
 * 希尔本人提出的步长序列
 */
public List<Integer> shellStpSequence(){
    List<Integer> stepSequence = new ArrayList<>();
    int step = array.length; // 16
    while((step >>= 1) > 0){ // 8 4 2 1
        stepSequence.add(step);
    }
    return stepSequence;
}

希尔排序完整实现

/**
 * 希尔排序
 */
public class ShellSort <T extends Comparable<T>> extends Sort<T>{

    @Override
    protected void sort() {
        // 根据元素数量算出步长序列
        List<Integer> stepSequence = shellStpSequence();
        // 按步长序列划分进行排序
        for (Integer step : stepSequence) {
            sort(step); // 按step进行排序
        }
    }
    
    /**
     * 分成step列进行排序
     */
    private void sort(int step){
        // col: 第几列, column的简称
        for(int col = 0; col < step; col++){
            // 插入排序对每一列进行排序
            for(int begin = col + step; begin < array.length; begin += step){
                // col、col+step、col+2*step、col+3*step
                int cur = begin;
                while(cur > col && cmp(cur, cur - step) < 0){
                    swap(cur, cur - step);
                    cur -= step;
                }
                
            }
        }
    }
    
    /**
     * 希尔本人提出的步长序列
     */
    public List<Integer> shellStpSequence(){
        List<Integer> stepSequence = new ArrayList<>();
        int step = array.length;
        while((step >>= 1) > 0){
            stepSequence.add(step);
        }
        return stepSequence;
    }
    
}

将速率过慢的几个排序去掉，只比较有可比性的几个排序。
生成 100000 个取值在[1, 10000] 的随机数进行排序：

步长序列优化

目前已知的最好的步长序列，最坏情况时间复杂度是 O(n^4/3^) ，1986年由 Robert Sedgewick 提出

/**
 * 目前效率最高的步长序列
 */
private List<Integer> sedgewickStepSequence() {
    List<Integer> stepSequence = new LinkedList<>();
    int k = 0, step = 0;
    while (true) {
        if (k % 2 == 0) {
            int pow = (int) Math.pow(2, k >> 1);
            step = 1 + 9 * (pow * pow - pow);
        } else {
            int pow1 = (int) Math.pow(2, (k - 1) >> 1);
            int pow2 = (int) Math.pow(2, (k + 1) >> 1);
            step = 1 + 8 * pow1 * pow2 - 6 * pow2;
        }
        if (step >= array.length) break;
        stepSequence.add(0, step);
        k++;
    }
    return stepSequence;
}

注：只是提高了最坏和平均时间复杂度，但是没有突破最好时间复杂度O(n)。

插入排序优化

上面代码中的插入排序是无优化的插入排序，可以通过二分搜索优化插入排序。
具体见这个：插入排序及二分搜索优化

复杂度和稳定性

• 最好情况是步长序列只有1，且序列几乎有序，时间复杂度为 O(n)
• 最坏和平均时间复杂度取决步长序列, 范围在 O(n^3/4^) ~ O(n^2^)
• 空间复杂度为O(1)
• 希尔排序属于不稳定排序