希尔排序（Shell Sort）
一、概念
-
希尔排序把序列看作一个矩阵，分为m列，逐列进行排序。 -
m从某个整数逐渐减为1，当m为1时，整个序列将完全有序。因此也被称为递减增量排序。 - 矩阵的列数取决于
步长序列，如果步长序列为【1，5，19，41，109...】就代表依次分为109列，41列，19列，5列，1列进行排序。不同的步长序列，执行效率也不同。
二、实例
1、实例一
- 希尔本人给出的步长序列是
n/2^k，比如n为16，k为2时，步长序列是【1，2，4，8】。
image
- 分为
8列进行排序。
image
- 逐列进行排序，必须
16和8这一列排序，则8在上16在下。
image
- 最终输出的结果为：
image
- 接着分为
4列进行排序。
image
- 得到的结果为：
image
- 接着分为2列进行排序。
image
- 分为一列排序。
image
- 总结：从
8列变为1列的过程中，逆序对的数量在逐渐减少。 - 因此
希尔排序底层一般使用插入排序对每一列进行排序。
2、实例二
- 假设有
11个元素，步长序列是【1，2，5】。
image
- 假设元素在第
col列、第row行，步长（总列数）是step - 那么这个元素在数组中的索引是
col + row * step - 比如
9在排序前是第2列、第0行，那么它排序前的索引是2 + 0 * 5 = 2 - 比如
4在排序前是第2列、第1行，那么它排序前的索引是2 + 1 * 5 = 7
三、代码实现
- 首先需要一个生成
步长序列的函数。
private List<Integer> shellStepSequence() {
List<Integer> stepSequence = new ArrayList<>();
int step = array.length;
while ((step >>= 1) > 0) {
stepSequence.add(step);
}
return stepSequence;
}
复制代码
- 排序代码：
/**
* 分成step列进行排序
*/
private void sort(int step) {
// 一共有多少列，就排多少次
// col : 第几列，column的简称
for (int col = 0; col < step; col++) { // 对第col列进行排序
// 每一列元素的索引为：col、col+step、col+2*step、col+3*step
// 插入排序
for (int begin = col + step; begin < array.length; begin += step) {
int cur = begin;
while (cur > col && cmp(cur, cur - step) < 0) {
swap(cur, cur - step);
cur -= step;
}
}
}
}
复制代码
四、最好的步长序列
- 目前已知的
最好的步长序列，最坏情况时间复杂度是O(n^4/3)。
image
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;
}
