盒子
盒子
文章目录
  1. 基本步骤
  2. 实现
  3. 总结

算法(六)希尔排序

希尔排序是插入排序的一种,是直接插入排序的更高效的改进版。希尔排序是记录增量来进行分组,再对分组内部进行直接插入排序,随着增量的不断减小,直到增量减小到1时,即每个分组中的数据量为1,此时排序结束。

基本步骤

设待排序的数组为a[0...n-1]

  1. 一般开始取增量数d=n/2。从a[0]~a[d-1]将数组中数据之间的间隔为增量数d的倍数归为相同组。
  2. 依次对每组中的数据进行直接插入排序,使其有序。
  3. 再增量数d=d/2,重复上面的步骤,直到d=1为止。

例如取d=10为例:

23, 4, 6, 34, 35, 47, 546, 32, 6,10

d=5,以后依次区d的一半

23, 4, 6, 34, 35, 47, 546, 32, 6,10
23 ————— 47
—–4 —————–546
———6 ——————— 32
————34 ——————— 6
—————— 35 —————– 10
第一趟结果:
23, 4, 6, 6, 10, 47, 546, 32, 34, 35

d=2

23610546—–34
—–4647—— 3235
第二趟结果:
6, 4, 10, 6, 23, 32, 34, 35, 546, 47

d=1

6, 4, 10, 6, 23, 32, 34, 35, 546, 47
第三趟结果:
4, 6, 6, 10, 23, 32, 34, 35, 47, 546

序列有序,此时排序结束。

实现

按照上面的分析步骤,可以发现主要是对d的值进行控制,所以实现代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public static void shellSort(int[] arr) {
int temp;
//增量值
int d = arr.length / 2;
while (true) {
for (int i = 0; i < d; i++) {//分成若干组进行排序
for (int j = i; j + d < arr.length; j += d) {
for (int k = j + d; k - d >= 0; k -= d) {//使用直接插入排序
if (arr[k] < arr[k - d]) {
temp = arr[k];
arr[k] = arr[k - d];
arr[k - d] = temp;
} else {
break;
}
}
}
}
if (d == 1) break;
d = d / 2;
}
}

总结

快速排序是不稳定排序,虽然对每组的排序是使用直接插入排序,在分组中是稳定的,但由于会进行分组,数组所在组会发生变化,所以并不能保证它整体是稳定排序。至于d的取值也没有绝对,也可以根据情况取值与变化。

转载请指明出处 idisfkj博客:https://idisfkj.github.io

支持一下
赞赏是一门艺术