简介
插入排序的优化, 也叫缩小增量排序
算法思路
分组排序
步长, 同组中2个元素在数组中的间隔数
- 定义分组的步长, step = arrLength / 2
- 对每个分组进行插入排序
- step = step / 2
- 重复 1~2 直到 step <= 0 (step == 1, 是最后一次分组)
第一次分组, step = 4
第一次分组, step = 2
第一次分组, step = 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
private static void sort(int[] array) {
if (array == null || array.length <= 1) {
return;
}
int length = array.length;
int step = length / 2;
// step 为步长, 每次缩减为原来的 1/2
for (; step > 0; step /= 2) {
// 一共有step个序列
for (int i = 0; i < step; i++) {
// 对单个序列进行排序
for (int j = i; j < length; j += step) {
int value = array[j];
int pre = j - step;
while (pre >= 0 && array[pre] > value) {
array[pre + step] = array[pre];
pre -= step;
}
array[pre + step] = value;
}
}
}
}
时间复杂度
参考
算法的时间复杂度和步长的定义相关
空间复杂度
O(1), 和插入排序一样, 并没有使用到对于空间
完整代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
class ShellSort {
private static void sort(int[] array) {
if (array == null || array.length <= 1) {
return;
}
int length = array.length;
int step = length / 2;
// step 为步长, 每次缩减为原来的 1/2
for (; step > 0; step /= 2) {
// 一共有step个序列
for (int i = 0; i < step; i++) {
// 对单个序列进行排序
for (int j = i; j < length; j += step) {
int value = array[j];
int pre = j - step;
while (pre >= 0 && array[pre] > value) {
array[pre + step] = array[pre];
pre -= step;
}
array[pre + step] = value;
}
}
}
}
public static void main(String[] args) {
int[] array = {111, 522, 77, 98, 36, 12, 13, 48};
sort(array);
System.out.println(arrayToString(array));
}
private static String arrayToString(int[] array) {
StringBuilder builder = new StringBuilder();
for (int t : array) {
builder.append(t + " ");
}
return builder.toString();
}
}
