希尔排序(Shell sort)
[toc]
1959年由唐纳德·希尔（Donald Shell）提出
1.思路
- 希尔排序把序列看作是一个矩阵，分成 𝑚 列，逐列进行排序
- 𝑚 从某个整数逐渐减为1
- 当 𝑚 为1时，整个序列将完全有序
- 因此，希尔排序也被称为递减增量排序（Diminishing Increment Sort）
矩阵的列数取决于步长序列（step sequence）
- 比如，如果步长序列为{1,5,19,41,109,...}，就代表依次分成109列、41列、19列、5列、1列进行排序
- 不同的步长序列，执行效率也不同
1.1举例
希尔本人给出的步长序列是 ，比如 𝑛 为16时，步长序列是{1, 2, 4, 8}
例如
原数组为
a1 = [16,15,14,13,12,11,10,9,8,7,6,5,4,3,2,1]
- 第一次分为8列，则分成2个数组
[16,15,14,13,12,11,10,9]
[ 8, 7, 6, 5, 4, 3, 2,1]
逐列进行比较数组变成
[ 8, 7, 6, 5, 4, 3, 2,1]
[16,15,14,13,12,11,10,9]
然后合并成一个数组
a2=[ 8, 7, 6, 5, 4, 3, 2,1,16,15,14,13,12,11,10,9] - 再将数组a2分为4列，则分为4个数组
[ 8, 7, 6, 5]
[ 4, 3, 2, 1]
[16,15,14,13]
[12,11,10, 9]
逐列进行比较
[ 4, 3, 2, 1]
[ 8, 7, 6, 5]
[12,11,10, 9]
[16,15,14,13]
然后合并成一个数组
a3=[ 4, 3, 2, 1, 8, 7, 6, 5,12,11,10, 9,16,15,14,13] - 再将数组a3分为2列，则分成的那个8个数组
[ 4, 3]
[ 2, 1]
[ 8, 7]
[ 6, 5]
[12,11]
[10, 9]
[16,15]
[14,13]
逐列进行比较
[ 2, 1]
[ 4, 3]
[ 6, 5]
[ 8, 7]
[10, 9]
[12,11]
[14,13]
[16,15]
然后合并成一个数组
a4=[ 2, 1, 4, 3, 6, 5, 8, 7,10, 9,12,11,14,13,16,15] - 在将数组a4分为1列，则分成16个数组，
[ 2]
[ 1]
[ 4]
……
[16]
[15]
逐列进行比较,然后合并成一个数组
a5=[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16]完成
每次进行拆分列数后，逆数对的个数减少
因此希尔排序底层一般使用插入排序对每一列进行排序，也很多资料认为希尔排序是插入排序的改进版
1.2代码思路
1.2.1 编写函数返回步长序列
这里给希尔给的步长序列希尔本人给出的步长序列是 ，比如 𝑛 为16时，步长序列是{1, 2, 4, 8}
///
/// Author: liyanjun
/// description:
///采用希尔给出的步长序列
List<int> _createShellStepSequence() {
List<int> stepSequence = [];
int step = list.length;
if (step == 0) return [];
if (step == 1) return [1];
while (step > 1) {
step >>= 1;
stepSequence.add(step);
}
return stepSequence;
}
1.2.2 编写函数对第col列进行插入排序
- 假设元素在第 col 列、第 row 行，步长（总列数）是 step
- 那么这个元素在数组中的索引是 col + row * step
- 所以插入排序for循环中每次增加的数字为step，而不再是1
- 因此原来插入排序相应的加1减1的操作都变成了 加step减step
///
/// Author: liyanjun
/// description: 分成step列进行排序
_sout(int step) {
//col 代表列，从
for (var col = 0; col < step; col++) {
//第col列进行排序 进行插入排序 这里的代码是插入排序的移动代码的优化版本
// 原来相应的加1减1的操作都变成了 加step减step
for (var begin = col+step; begin < list.length; begin +=step) {
int cur = begin;
T v = list[cur];
while (cur > col && cmpElement(v, list[cur - step]) < 0) {
list[cur] = list[cur - step];
cur -= step;
}
list[cur] = v;
}
}
}
1.2.3 遍历步长序列
sort() {
List<int> stepSequence = _createShellStepSequence();
for (var step in stepSequence) {
_sout(step);
}
}
2.代码
/// Date: 2020-11-09 00:01:18
/// FilePath: /algorithm/sort/shell_sort.dart
/// Description: 希尔排序
///
class ShellSort<T extends Comparable<T>> extends Sort<T> {
@override
sort() {
List<int> stepSequence = _createShellStepSequence();
for (var step in stepSequence) {
_sout(step);
}
}
///
/// Author: liyanjun
/// description: 分成step列进行排序
_sout(int step) {
//col 代表列，从
for (var col = 0; col < step; col++) {
//第col列进行排序 进行插入排序 这里的代码是插入排序的移动代码的优化版本
// 原来相应的加1减1的操作都变成了 加step减step
for (var begin = col+step; begin < list.length; begin +=step) {
int cur = begin;
T v = list[cur];
while (cur > col && cmpElement(v, list[cur - step]) < 0) {
list[cur] = list[cur - step];
cur -= step;
}
list[cur] = v;
}
}
}
///
/// Author: liyanjun
/// description:
///采用希尔给出的步长序列
List<int> _createShellStepSequence() {
List<int> stepSequence = [];
int step = list.length;
if (step == 0) return [];
if (step == 1) return [1];
while (step > 1) {
step >>= 1;
stepSequence.add(step);
}
return stepSequence;
}
验证
main(List<String> args) {
// List<int> list = IntergerTools.random(10000, 1, 20000); //生成10000个数，最小是1，最大是20000
List<int> list = IntergerTools.random(10, 1, 20); //生成10000个数，最小是1，最大是20000
List<Sort> sortList = [
// HeapSort<num>(),
// SelectSort<num>(),
// BubbleSort2<num>(),
// BubbleSort1<num>(),
// BubbleSort<num>(),
// InsertSort<num>(),
// InsertSort1<num>(),
// InsertSort2<num>(),
// MergeSort<num>(),
// QuickSort<num>(),
ShellSort<num>(),
];
testSorts(list, sortList);
}
void testSorts(List<int> list, List<Sort> sorts) {
print('排序前 ：$list');
for (Sort sort in sorts) {
List<int> newList = List.from(list);
sort.setList(newList);
sort.sortPrint();
Asserts.test(IntergerTools.isAscOrder(sort.list));
print('排序后 ：${sort.list}');
}
sorts.sort(); //比较
for (Sort sort in sorts) {
print(sort);
}
}
结果
排序前 ：[2, 18, 8, 20, 10, 9, 10, 12, 7, 9]
排序后 ：[2, 7, 8, 9, 9, 10, 10, 12, 18, 20]
【ShellSort<num>】
耗时：0.002s (2ms) 比较：27 交换：0
-----------------
3.时间复杂度
空间复杂度为O(1)，属于不稳定排序
最好情况是步长序列只有1，且序列几乎有序，时间复杂度为 O(n)
希尔给出的步长序列 ，的最坏情况时间复杂度是
目前已知的最好的步长序列，最坏情况时间复杂度是 ，1986年由Robert Sedgewick提出
步长算法思路：
- 如果k是偶数，则步长序列为
- 如果k是奇数，则步长序列为
///
/// Author: liyanjun
/// description: 科学家发现最快的步长序列 ，最坏情况时间复杂度是 $O(n^{4/3})$
///
List<int> _sedgewickStepSequence() {
List<int> stepSequence = [];
int k = 0, step = 0;
while (true) {
if (k % 2 == 0) {
int powResult = pow(2, k >> 1); //求2^{k/2}的结果
step = 1 + 9 * (powResult * powResult - powResult);
} else {
int pow1 = pow(2, (k - 1) >> 1); //求2^{k-1/2}的结果
int pow2 = pow(2, (k + 1) >> 1); //求2^{k-1/2}的结果
step = 1 + 8 * pow1 * pow2 - 6 * pow2;
}
if (step >= list.length) break;
stepSequence.insert(0, step);
k++;
}
return stepSequence;
}
