【排序】希尔排序，选步长最关键

一、前言

希尔排序：是由希尔提出的一种排序算法，它是插入排序的改进版本。

希尔排序通过引入步长 gap，将数组分成多个子序列分别进行插入排序，这样可以让一个元素朝最终位置跳跃一大步。
步长在每一轮排序后递减，最后减至 1，变成简单插入排序。
这个时候，数组已经基本有序，只需要再做少量的对比和移动即可完成最后的排序。

举栗，动图如下：

如何想出这个方法的？

还记的 逆序对 嘛？

忘了？下面知识点也有罗列，记得回顾哦。

根据逆序对可知：要提高算法效率，必须：

每次消去不止 1个逆序对
每次交换相隔较远的 2个元素

所以，希尔排序就采取第二种方式来提高算法效率 ———— 增长步长。

希尔排序，常用步长方法是 长度折半序列：length/2，length/4，length/8 。。。

二、知识点

知识点，如下：

时间复杂度
逆序对
实现：希尔排序就是使用 gap 序列的插入排序

PS: 实习生的面试，会遇到

（1）时间复杂度

最好情况：时间复杂度 O(N * log^2N)
最坏情况：时间复杂度 O(N ^ 2)，增量元素不互质，则小增量可能根本不起作用
稳定性：不稳定。

例如，原数组 {4, 1, 4}

不稳定：排序过程中，第二个 4 排在了第一个 4 前面。

排序总图，如图：

（2）逆序对

逆序对（inversion）：对于下标 i < j，如果 arr[i] > a[j]，则称 (i, j) 是一对逆序对。

举个栗子，序列 {34, 8, 64, 51, 32, 21} 有多少逆序对？

有9对：

(34, 8), (34, 32), (34, 21), (64, 51), 

(64, 32), (64, 21), (51, 32), (51, 21), (32, 21)
复制代码

可得定理：

定理：任意 N 个不同元素组成的序列平均具有 N(N-1)/4 个逆序对
定理：任何仅以交换相邻两元素来排序的算法，其平均时间复杂度为 O(N^2)

那么逆序对，有什么用呢？

代表了，需要交换的次数。
为提高算法效率提供基础

那么要提高算法效率，必须：

每次消去不止 1个逆序对
每次交换相隔较远的 2个元素

（3）实现

从前往后排序，代码如下：

public class SelectSort {

    // 希尔排序
    // Time: O(n^2), Space: O(1)
    public void sort(int[] arr) {
        if (arr == null || arr.length == 0) return;
        
        // 每次折半 >> 1 表示为: 右移 1位，即 /2
        for (int gap = arr.length >> 1; gap > 0; gap >>= 1) {
            for (int i = gap; i < arr.length; ++i) {
                int cur = arr[i];
                int j = i - gap;
                while (j >= 0 && arr[j] > cur) {
                    arr[j+gap] = arr[j];
                    j -= gap;
                }
                arr[j+gap] = cur;
            }
        }
    }

    // 对比插入排序，如下：
    // 可以理解为：希尔排序就是 使用 gap 序列的插入排序
    // Time: O(n^2), Space: O(1)
    public void insertionSort(int[] arr) {
        if (arr == null || arr.length == 0) return;
        for (int i = 1; i < arr.length; ++i) {
            int cur = arr[i];
            int j = i - 1;
            while (j >= 0 && arr[j] > cur) {
                arr[j + 1] = arr[j];
                j -= 1;
            }
            arr[j + 1] = cur;
        }
    }
}
复制代码