希尔排序¶
一、什么是希尔排序？¶
- 希尔排序是一种基于插入排序进行了优化后的排序算法
- 希尔排序比普通插入排序更适用于大规模数组排序
二、为什么要用希尔排序？¶
普通的插入排序存在一个问题：
- 对于大规模乱序数组排序很慢
而它这么慢的原因是：
- 插入排序只是交换相邻元素，因此元素只能一点点从一端移动到另一端
比如说，数组 [7, 2, 3, 5, 6, 4, 1]，插入排序只能一点点地将 1 移动到最前面。
希尔排序为了加快这种情况的排序速度，对插入排序进行了优化：
- 对数组元素按照指定间隔进行跳跃式的分组
- 对分组内进行局部排序，交换不相邻的元素
- 最终用插入排序将局部有序数组进行排序
比如说，数组 [7, 2, 3, 5, 6, 4, 1]。
希尔排序会将其划分为多个组，假设按照间隔为 3 分组，可分成 3 组：
_______________________________________________
| | |
v v v
___ ___ ___ ___ ___ ___ ___
| 7 | | 2 | | 3 | | 5 | | 6 | | 4 | | 1 |
_______________________
| |
v v
___ ___ ___ ___ ___ ___ ___
| 7 | | 2 | | 3 | | 5 | | 6 | | 4 | | 1 |
_______________________
| |
v v
___ ___ ___ ___ ___ ___ ___
| 7 | | 2 | | 3 | | 5 | | 6 | | 4 | | 1 |
然后分别对每个组内进行排序：
[7, 5, 1] --> [1, 5, 7]
_______________________________________________
| | |
v v v
___ ___ ___ ___ ___ ___ ___
| 1 | | 2 | | 3 | | 5 | | 6 | | 4 | | 7 |
[2, 6] --> [2, 6]
_______________________
| |
v v
___ ___ ___ ___ ___ ___ ___
| 1 | | 2 | | 3 | | 5 | | 6 | | 4 | | 7 |
[3, 4] --> [3, 4]
_______________________
| |
v v
___ ___ ___ ___ ___ ___ ___
| 1 | | 2 | | 3 | | 5 | | 6 | | 4 | | 7 |
可以看到，1 已经直接移动到最前面了，从一端移动到另一端的速度很快。
而且，在局部有序的情况下，整个数组看起来也基本是有序的了。
希尔排序就是采用间隔分组排序的方式，来优化对大规模的数组排序。
三、如何实现希尔排序？¶
希尔排序的基本思想是按照间隔进行跳跃式分组，并对组内进行排序。
其排序过程是这样：
- 按照间隔 h 对数组进行跳跃式分组
- 对每个分组内的元素进行排序
- 缩小间隔 h，重新回到第 1 步，直到 h = 1 为止
这里面有 2 个核心的点：
- 分组内的排序
- 间隔 h 的选择和缩小
当间隔 h = 1 时，其实就是普通的插入排序了。
3.1 分组内排序¶
一般来说，希尔排序的实现中，分组内排序采用的是插入排序。
比如对这个分组进行插入排序：
_______________________________________________
| | |
v v v
___ ___ ___ ___ ___ ___ ___
| 7 | | 2 | | 3 | | 5 | | 6 | | 4 | | 1 |
_______________________________________________
| | |
v v v
___ ___ ___ ___ ___ ___ ___
| 5 | | 2 | | 3 | | 7 | | 6 | | 4 | | 1 | -- (5 插到 7 前)
_______________________________________________
| | |
v v v
___ ___ ___ ___ ___ ___ ___
| 1 | | 2 | | 3 | | 5 | | 6 | | 4 | | 7 | -- (1 插到 5 前)
所以说希尔排序本质就是插入排序，只是插入的方式有点不同。
插入排序是相邻元素之间的交换，而希尔排序是跳跃式的交换。
3.2 增量序列¶
希尔排序中的间隔 h 变化序列，一般称为增量序列。
比如说，开始间隔 h = n / 2，后面以 h = h / 2 缩小增量：
n/2 n/4 n/8 ... 1
那么这样的一个序列，就称为增量序列。
- 目前来说，希尔排序的增量序列的选择还没有最优的方案
因为增量序列的选择和证明还是一个数学难题。
除了上面取中的增量序列，在《算法》一书中还给出了 2 种增量序列：
1, 4, 13, 40, 121, 364 ... (h = 3 * h + 1)
1, 5, 19, 41, 109, 209, 505, 929, 2161, 3905, 8929, 16001, 36289, 64769, 146305, 260609
希尔排序的性能会受到增量序列的影响，但是目前暂时没有办法证明哪个增量序列是最优的。
四、算法分析¶
4.1 时间复杂度¶
- 目前尚未能准确算出来复杂度
- 只能知道大概范围：nlogn < O < n^2
4.2 空间复杂度¶
- 空间复杂度：O(1)
- 原地算法
4.3 稳定性¶
- 非稳定排序算法
总结¶
- 希尔排序是一种基于插入排序进行了优化后的排序算法
- 希尔排序比普通插入排序更适用于大规模数组排序
- 希尔排序的关键点包括增量序列的选择和分组内排序
- 目前还没有找到最优的增量序列
- 暂时无法证明希尔排序的时间复杂度
参考¶
https://www.cnblogs.com/chengxiao/p/6104371.html
附录¶
/**
* 希尔排序
* <p>
* 时间复杂度：暂时无法分析，但是达不到 O(n^2)
* <p>
* 空间复杂度：O(1)
* <p>
* 稳定性：不稳定
*/
public void shellSort(int[] arr) {
int n = arr.length;
// 递增序列：1, 4, 13, 40, 121, ...
int h = 1;
while (h < n / 3) {
h = 3 * h + 1;
}
// 增量序列倒序递减至 1
while (h >= 1) {
// 局部插入排序
for (int i = h; i < n; i++) {
int x = arr[i];
int j = i;
for (; j >= h && x < arr[j - h]; j -= h) {
arr[j] = arr[j - h];
}
arr[j] = x;
}
// 递减 h 间隔
h /= 3;
}
}