Algorithm/src/com/dang/Sort.java at master · DangHT/Algorithm · GitHub

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
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
packagecom.dang;

/**
 * 排序算法
 * @author dht925nerd@126.com
 * @date 2019/02/25
 */
publicclassSort {

/**
 * 使用快速排序的最低阈值
 */
privatestaticfinalintQUICKSORT_THRESHOLD = 10;

/**
 * 选择排序
 * @param array 待排数组
 */
publicstaticvoidselectionSort(int[] array){
if (array == null || array.length == 0){ return; }
for (inti = 0; i < array.length; i++){
intmin = Integer.MAX_VALUE;
intminPos = i;
for (intj = i; j < array.length; j++) {
if (array[j] < min) {
min = array[j];
minPos = j;
 }
 }
array[minPos] = array[i];
array[i] = min;
 }
 }

/**
 * 冒泡排序
 * @param array 待排数组
 */
publicstaticvoidbubbleSort(int[] array){
if (array == null || array.length == 0){ return; }
for (inti = array.length - 1; i >= 0; i--){
booleanflag = true;
for (intj = 0; j < i; j++){
if (array[j] > array[j + 1]){
inttemp = array[j];
array[j] = array[j + 1];
array[j + 1] = temp;
flag = false;
 }
 }
if (flag) return;
 }
 }

/**
 * 插入排序
 * @param array 待排数组
 */
publicstaticvoidinsertionSort(int[] array){
if (array == null || array.length ==0){ return; }
for (inti = 1; i < array.length; i++){
for (intj = i; j > 0; j--){
if (array[j] < array[j - 1]){
inttemp = array[j];
array[j] = array[j - 1];
array[j - 1] = temp;
 } else {
break;
 }
 }
 }
 }

/**
 * 希尔排序
 * @param array 待排数组
 */
publicstaticvoidshellSort(int[] array){
if (array == null || array.length ==0){ return; }
for (intdis = array.length / 2; dis > 0; dis /= 2){
for (intpos = dis; pos < array.length; pos++){
for (inti = pos; i >= dis && array[i] < array[i - dis]; i -= dis){
inttemp = array[i];
array[i] = array[i - dis];
array[i - dis] = temp;
 }
 }
 }
 }

/**
 * 堆排序
 * @param array 待排数组
 */
publicstaticvoidheapSort(int[] array){
if (array == null || array.length ==0){ return; }
buildHeap(array);
for (inti = array.length - 1; i >= 0; i--){
inttemp = array[i];
array[i] = array[0];
array[0] = temp;
intj = 0;
downAdjust(array, j, i);
 }
 }

/**
 * 建立最大堆
 * @param array 待调数组
 */
privatestaticvoidbuildHeap(int[] array){
if (array == null || array.length ==0){ return; }
for (inti = array.length / 2 - 1; i >= 0; i--){
downAdjust(array, i, array.length);
 }
 }

/**
 * 最大堆向下过滤调整
 * @param array 待调数组
 * @param j 堆顶
 * @param height 调整高度
 */
privatestaticvoiddownAdjust(int[] array, intj, intheight) {
while (j * 2 < height) {
if (j * 2 + 2 < height && array[j * 2 + 2] > array[j] && array[j * 2 + 2] > array[j * 2 + 1]){
inttemp = array[j * 2 + 2];
array[j * 2 + 2] = array[j];
array[j] = temp;
j = j * 2 + 2;
 } elseif (j * 2 + 1 < height && array[j * 2 + 1] > array[j]){
inttemp = array[j * 2 + 1];
array[j * 2 + 1] = array[j];
array[j] = temp;
j = j * 2 + 1;
 } elsebreak;
 }
 }

/**
 * 归并排序(递归)
 * @param array 待排数组
 */
publicstaticvoidmergeSort(int[] array){
if (array == null || array.length ==0){ return; }
int[] tempArray = newint[array.length];
mergeSort(array, tempArray, 0, array.length - 1);
 }

/**
 * 将有序子列归并
 * @param array 原始数组
 * @param tempArray 归并缓存数组
 * @param lFrom 左子列起始位置
 * @param rFrom 右子列起始位置
 * @param rTo 右子列终点位置
 */
privatestaticvoidmerge(int[] array, int[] tempArray, intlFrom, intrFrom, intrTo){
//左子列终点位置, 假设左右两列紧挨
intlTo = rFrom - 1;
//缓存数组存储的起始位置
inttemp = lFrom;
//归并元素总数
intsum = rTo - lFrom + 1;
while (lFrom <= lTo && rFrom <= rTo){
if (array[lFrom] <= array[rFrom]) tempArray[temp++] = array[lFrom++];
elsetempArray[temp++] = array[rFrom++];
 }
while (lFrom <= lTo) tempArray[temp++] = array[lFrom++];
while (rFrom <= rTo) tempArray[temp++] = array[rFrom++];
for (inti = 0; i < sum; i++, rTo--){
array[rTo] = tempArray[rTo];
 }
 }

/**
 * 归并排序递归实现体
 * @param array 待排数组
 * @param tempArray 归并缓存数组
 * @param from 排序起始位置
 * @param to 排序终点位置
 */
privatestaticvoidmergeSort(int[] array, int[] tempArray, intfrom, intto){
if (from < to){
intcenter = (from + to) / 2;
mergeSort(array, tempArray, from, center);
mergeSort(array, tempArray, center + 1, to);
merge(array, tempArray, from, center + 1, to);
 }
 }

/**
 * 快速排序
 * @param array 待排数组
 */
publicstaticvoidquickSort(int[] array){
quickSort(array, 0, array.length - 1);
 }

/**
 * 快速排序实现体
 * 因为快速排序的不稳定性, 利用阈值保证效率,
 * 低于阈值执行插入排序{@link Sort#insertionSort(int[])}
 * @param array 待排数组
 * @param left 排序起始位置
 * @param right 排序终点位置
 */
privatestaticvoidquickSort(int[] array, intleft, intright){
if (array == null || array.length ==0){ return; }
if (right - left >= QUICKSORT_THRESHOLD){
intpivot = median3(array, left, right);
inti = left, j = right - 1, temp;
for (;;){
while (array[++i] < pivot){}
while (array[--j] > pivot){}
if (i < j){
temp = array[i];
array[i] = array[j];
array[j] = temp;
 } elsebreak;
 }
temp = array[i];
array[i] = array[right - 1];
array[right - 1] = temp;
quickSort(array, left, i - 1);
quickSort(array, i + 1, right);
 } else {
insertionSort(array);
 }
 }

/**
 * 选取数组头, 中, 尾三者的中位数
 * @param array 原始数组
 * @param left 头
 * @param right 尾
 * @return 中位数
 */
privatestaticintmedian3(int[] array, intleft, intright){
intcenter = (left + right) / 2;
inttemp;
if (array[left] > array[center]){
temp = array[left];
array[left] = array[center];
array[center] = temp;
 }
if (array[left] > array[right]){
temp = array[left];
array[left] = array[right];
array[right] = temp;
 }
if (array[center] > array[right]){
temp = array[center];
array[center] = array[right];
array[right] = temp;
 }
/* 前三步执行完毕后, 取值情况一定为: array[left] <= array[center] <= array[right] */
temp = array[center];
array[center] = array[right - 1];
array[right - 1] = temp;
/* 将array[center](主元)放在right - 1位置上,
 后续子集划分仅需考虑array[left + 1]~array[right - 2]即可 */
returnarray[right - 1];
 }

}