forked from algorithmzuo/algorithmbasic2020
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathCode05_ShellSort.java
More file actions
136 lines (126 loc) · 3.77 KB
/
Code05_ShellSort.java
File metadata and controls
136 lines (126 loc) · 3.77 KB
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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
package class08;
// 这是希尔排序，课上没有讲，因为比较简单，有兴趣的同学可以看一下
// 今天在面试场上也基本不怎么问了
// 这个排序就是调整步长的插入排序，也可以认为是插入排序的小改进版本
// 改变不了时间复杂度，只是优化了常数时间
// 我还写了和插入排序的性能对比
public class Code05_ShellSort {
public static void shellSort(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
// 步长依次为5、2、1
// 在插入排序中，一步一步往前交换，直到左边的数<=当前的数，停止
// 在希尔排序中，如果步长依次为5、2、1
// 那么来到每个数，每次跳5步往前交换，直到往前5步的数<=当前的数，停止
// 然后再来到每个数，每次跳3步往前交换，直到往前3步的数<=当前的数，停止
// 然后再来到每个数，每次跳1步往前交换，直到往前1步的数<=当前的数，停止
int[] step = { 5, 2, 1 };
for (int s = 0; s < step.length; s++) {
for (int i = step[s]; i < arr.length; i++) {
for (int j = i - step[s]; j >= 0 && arr[j] > arr[j + step[s]]; j -= step[s]) {
swap(arr, j, j + step[s]);
}
}
}
}
public static void swap(int[] arr, int i, int j) {
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
// 为了测试
public static void insertionSort(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
// 不只1个数
for (int i = 1; i < arr.length; i++) { // 0 ~ i 做到有序
for (int j = i - 1; j >= 0 && arr[j] > arr[j + 1]; j--) {
swap(arr, j, j + 1);
}
}
}
// 为了测试
public static int[] generateRandomArray(int len, int maxValue) {
int[] arr = new int[len];
for (int i = 0; i < arr.length; i++) {
arr[i] = (int) ((maxValue + 1) * Math.random()) - (int) (maxValue * Math.random());
}
return arr;
}
// 为了测试
public static int[] copyArray(int[] arr) {
if (arr == null) {
return null;
}
int[] res = new int[arr.length];
for (int i = 0; i < arr.length; i++) {
res[i] = arr[i];
}
return res;
}
// 为了测试
public static boolean isEqual(int[] arr1, int[] arr2) {
if ((arr1 == null && arr2 != null) || (arr1 != null && arr2 == null)) {
return false;
}
if (arr1 == null && arr2 == null) {
return true;
}
if (arr1.length != arr2.length) {
return false;
}
for (int i = 0; i < arr1.length; i++) {
if (arr1[i] != arr2[i]) {
return false;
}
}
return true;
}
// 为了测试
public static void printArray(int[] arr) {
if (arr == null) {
return;
}
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
System.out.println();
}
// 为了测试
public static void main(String[] args) {
int testTime = 500000;
int maxSize = 100;
int maxValue = 100;
boolean succeed = true;
for (int i = 0; i < testTime; i++) {
int len = (int) (Math.random() * maxSize);
int[] arr1 = generateRandomArray(len, maxValue);
int[] arr2 = copyArray(arr1);
shellSort(arr1);
insertionSort(arr2);
if (!isEqual(arr1, arr2)) {
succeed = false;
printArray(arr1);
printArray(arr2);
break;
}
}
System.out.println(succeed ? "功能测试通过！" : "功能测试不通过！");
int len = 100000;
System.out.println("数据样本长度 : " + len);
int[] arr1 = generateRandomArray(len, maxValue);
int[] arr2 = copyArray(arr1);
long start = 0;
long end = 0;
start = System.currentTimeMillis();
shellSort(arr1);
end = System.currentTimeMillis();
System.out.println("希尔排序运行时间 : " + (end - start) + " 毫秒");
start = System.currentTimeMillis();
insertionSort(arr2);
end = System.currentTimeMillis();
System.out.println("插入排序运行时间 : " + (end - start) + " 毫秒");
}
}