希尔排序

希尔排序是插入排序的改进，插入排序比较的时候是逐个元素进行处理的，希尔排序就是设定一个初始步长gap，分为gap个子序列，

例如gap=3 时，子序列为：

• 索引 0, 3, 6, …
• 索引 1, 4, 7, …
• 索引 2, 5, 8, …

然后分别对每个子序列进行插入排序。

初始位置就是gap到n-1，和0~gap之间的元素进行比较。假设现在要处理的是gap，先拿gap和(gap-gap)也就是位置0的元素进行比较。然后比较到gap+1，gap+1和(gap+1-gap)也就是gap+1比较，直到k（gap<k<n）的时候，k和k-gap比较，判断逻辑和插入排序一样，如果k-gap比k处的元素位置大的话，k-gap的元素右移gap个位置，也就是移动到k，后续处理直到k<0或者找到符合条件的插入间隙。当gap为1的时候，就会对数组整体进行一个标准的插入排序，排序完成。

希尔排序并不是一种新的排序，而是对插入排序的一种优化和提升，插入排序最坏情况时间复杂度是O(n²)，希尔排序通过步长的方式提前优化了整体数组，使得整体有序后再执行一次插入排序，效率更高（主要取决于步长gap和数据集的有序情况和大小）。

Java实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

/**
 * 希尔排序
 */
public static void shellSort(int [] arr){
    int gap = arr.length;
    // 设定初始步长，并且后续每次为原来的一半，直到1的时候会整体执行一遍插入排序，然后跳出循环
    while((gap /= 2) > 0){
        // 内层逻辑和插入排序一样，只不过把固定的1换成了gap
        for (int i = gap; i < arr.length; i++) {
            int temp = arr[i];
            int j = i - gap;
            while(j >= 0 && arr[j] > temp){
                arr[j + gap] = arr[j];
                j -= gap;
            }
            arr[j + gap] = temp;
        }
    }
}

时间复杂度的话主要也是取决于步长的选择，常用的就是数组arr长度n的一半，n/2,n/4,……1，也可以自行定义。采用每次除以2的步长序列时，希尔排序的最坏时间复杂度为 O(n²)。但通过选择更优的步长（如 Hibbard 步长 2^k-1），可将最坏情况优化到 O(n^(3/2)) 或更好。平均时间复杂度通常介于 O(n log n) 和 O(n²) 之间。

空间复杂度也是O(1)，由于gap不为1时可能会把元素移到相同元素的左边，所以希尔排序是不稳定的。

总结

时间复杂度：通常介于 O(n log n) 和 O(n²) 之间

空间复杂度：O(1)

稳定性：不稳定