-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathSort.java
More file actions
364 lines (320 loc) · 9.59 KB
/
Sort.java
File metadata and controls
364 lines (320 loc) · 9.59 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
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
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
package dp;
/**
* A class that contains several sorting routines,
* implemented as static methods.
* Arrays are rearranged with smallest item first,
* using compareTo.
*
* @author Mark Allen Weiss
*/
public final class Sort {
private static final int CUTOFF = 3;
private static final int NUM_ITEMS = 1000;
private static int theSeed = 1;
/**
* Simple insertion sort.
*
* @param a an array of Comparable items.
*/
public static <AnyType extends Comparable<? super AnyType>>
void insertionSort(AnyType[] a) {
int j;
for (int p = 1; p < a.length; p++) {
AnyType tmp = a[p];
for (j = p; j > 0 && tmp.compareTo(a[j - 1]) < 0; j--)
a[j] = a[j - 1]; //tmp的位置还在前面
a[j] = tmp;
}
}
/**
* Shellsort, using Shell's (poor) increments.
*
* @param a an array of Comparable items.
*/
public static <AnyType extends Comparable<? super AnyType>>
void shellsort(AnyType[] a) {
int j;
for (int gap = a.length / 2; gap > 0; gap /= 2)
for (int i = gap; i < a.length; i++) {
AnyType tmp = a[i];
for (j = i; j >= gap &&
tmp.compareTo(a[j - gap]) < 0; j -= gap)
a[j] = a[j - gap];
a[j] = tmp;
}
}
/**
* Internal method for heapsort.
*
* @param i the index of an item in the heap.
* @return the index of the left child.
*/
private static int leftChild(int i) {
return 2 * i + 1;
}
/**
* Internal method for heapsort that is used in deleteMax and buildHeap.
*
* @param a an array of Comparable items.
* @index i the position from which to percolate down.
* @int n the logical size of the binary heap.
*/
private static <AnyType extends Comparable<? super AnyType>>
void percDown(AnyType[] a, int i, int n) {
int child;
AnyType tmp;
for (tmp = a[i]; leftChild(i) < n; i = child) {
child = leftChild(i);
if (child != n - 1 && a[child].compareTo(a[child + 1]) < 0)
child++;
if (tmp.compareTo(a[child]) < 0)
a[i] = a[child];
else
break;
}
a[i] = tmp;
}
/**
* Standard heapsort.
*
* @param a an array of Comparable items.
*/
public static <AnyType extends Comparable<? super AnyType>>
void heapsort(AnyType[] a) {
for (int i = a.length / 2 - 1; i >= 0; i--) /* buildHeap */
percDown(a, i, a.length);
for (int i = a.length - 1; i > 0; i--) {
swapReferences(a, 0, i); /* deleteMax */
percDown(a, 0, i);
}
}
/**
* Mergesort algorithm.
*
* @param a an array of Comparable items.
*/
public static <AnyType extends Comparable<? super AnyType>>
void mergeSort(AnyType[] a) {
AnyType[] tmpArray = (AnyType[]) new Comparable[a.length];
mergeSort(a, tmpArray, 0, a.length - 1);
}
/**
* Internal method that makes recursive calls.
*
* @param a an array of Comparable items.
* @param tmpArray an array to place the merged result.
* @param left the left-most index of the subarray.
* @param right the right-most index of the subarray.
*/
private static <AnyType extends Comparable<? super AnyType>>
void mergeSort(AnyType[] a, AnyType[] tmpArray,
int left, int right) {
if (left < right) {
int center = (left + right) / 2;
mergeSort(a, tmpArray, left, center);
mergeSort(a, tmpArray, center + 1, right);
merge(a, tmpArray, left, center + 1, right);
}
}
/**
* Internal method that merges two sorted halves of a subarray.
*
* @param a an array of Comparable items.
* @param tmpArray an array to place the merged result.
* @param leftPos the left-most index of the subarray.
* @param rightPos the index of the start of the second half.
* @param rightEnd the right-most index of the subarray.
*/
private static <AnyType extends Comparable<? super AnyType>>
void merge(AnyType[] a, AnyType[] tmpArray, int leftPos, int rightPos, int rightEnd) {
int leftEnd = rightPos - 1;
int tmpPos = leftPos;
int numElements = rightEnd - leftPos + 1;
// Main loop
while (leftPos <= leftEnd && rightPos <= rightEnd)
if (a[leftPos].compareTo(a[rightPos]) <= 0)
tmpArray[tmpPos++] = a[leftPos++];
else
tmpArray[tmpPos++] = a[rightPos++];
while (leftPos <= leftEnd) // Copy rest of first half
tmpArray[tmpPos++] = a[leftPos++];
while (rightPos <= rightEnd) // Copy rest of right half
tmpArray[tmpPos++] = a[rightPos++];
// Copy tmpArray back
for (int i = 0; i < numElements; i++, rightEnd--)
a[rightEnd] = tmpArray[rightEnd];
}
/**
* Quicksort algorithm.
*
* @param a an array of Comparable items.
*/
public static <AnyType extends Comparable<? super AnyType>>
void quicksort(AnyType[] a) {
quicksort(a, 0, a.length - 1);
}
/**
* Method to swap to elements in an array.
*
* @param a an array of objects.
* @param index1 the index of the first object.
* @param index2 the index of the second object.
*/
public static <AnyType> void swapReferences(AnyType[] a, int index1, int index2) {
AnyType tmp = a[index1];
a[index1] = a[index2];
a[index2] = tmp;
}
/**
* Return median of left, center, and right.
* Order these and hide the pivot.
*/
private static <AnyType extends Comparable<? super AnyType>>
AnyType median3(AnyType[] a, int left, int right) {
int center = (left + right) / 2;
if (a[center].compareTo(a[left]) < 0)
swapReferences(a, left, center);
if (a[right].compareTo(a[left]) < 0)
swapReferences(a, left, right);
if (a[right].compareTo(a[center]) < 0)
swapReferences(a, center, right);
// Place pivot at position right - 1
swapReferences(a, center, right - 1);
return a[right - 1];
}
/**
* Internal quicksort method that makes recursive calls.
* Uses median-of-three partitioning and a cutoff of 10.
*
* @param a an array of Comparable items.
* @param left the left-most index of the subarray.
* @param right the right-most index of the subarray.
*/
private static <AnyType extends Comparable<? super AnyType>>
void quicksort(AnyType[] a, int left, int right) {
if (left + CUTOFF <= right) {
AnyType pivot = median3(a, left, right);
// Begin partitioning
int i = left, j = right - 1;
for (; ; ) {
while (a[++i].compareTo(pivot) < 0) {
}
while (a[--j].compareTo(pivot) > 0) {
}
if (i < j)
swapReferences(a, i, j);
else
break;
}
swapReferences(a, i, right - 1); // Restore pivot
quicksort(a, left, i - 1); // Sort small elements
quicksort(a, i + 1, right); // Sort large elements
} else // Do an insertion sort on the subarray
insertionSort(a, left, right);
}
/**
* Internal insertion sort routine for subarrays
* that is used by quicksort.
*
* @param a an array of Comparable items.
* @param left the left-most index of the subarray.
* @param right the right-most index of the subarray.
*/
private static <AnyType extends Comparable<? super AnyType>>
void insertionSort(AnyType[] a, int left, int right) {
for (int p = left + 1; p <= right; p++) {
AnyType tmp = a[p];
int j;
for (j = p; j > left && tmp.compareTo(a[j - 1]) < 0; j--)
a[j] = a[j - 1];
a[j] = tmp;
}
}
/**
* Quick selection algorithm.
* Places the kth smallest item in a[k-1].
*
* @param a an array of Comparable items.
* @param k the desired rank (1 is minimum) in the entire array.
*/
public static <AnyType extends Comparable<? super AnyType>>
void quickSelect(AnyType[] a, int k) {
quickSelect(a, 0, a.length - 1, k);
}
/**
* Internal selection method that makes recursive calls.
* Uses median-of-three partitioning and a cutoff of 10.
* Places the kth smallest item in a[k-1].
*
* @param a an array of Comparable items.
* @param left the left-most index of the subarray.
* @param right the right-most index of the subarray.
* @param k the desired index (1 is minimum) in the entire array.
*/
private static <AnyType extends Comparable<? super AnyType>>
void quickSelect(AnyType[] a, int left, int right, int k) {
if (left + CUTOFF <= right) {
AnyType pivot = median3(a, left, right);
// Begin partitioning
int i = left, j = right - 1;
for (; ; ) {
while (a[++i].compareTo(pivot) < 0) {
}
while (a[--j].compareTo(pivot) > 0) {
}
if (i < j)
swapReferences(a, i, j);
else
break;
}
swapReferences(a, i, right - 1); // Restore pivot
if (k <= i)
quickSelect(a, left, i - 1, k);
else if (k > i + 1)
quickSelect(a, i + 1, right, k);
} else // Do an insertion sort on the subarray
insertionSort(a, left, right);
}
private static void checkSort(Integer[] a) {
for (int i = 0; i < a.length; i++)
if (a[i] != i)
System.out.println("Error at " + i);
System.out.println("Finished checksort");
}
public static void main(String[] args) {
Integer[] a = new Integer[NUM_ITEMS];
for (int i = 0; i < a.length; i++)
a[i] = i;
for (theSeed = 0; theSeed < 20; theSeed++) {
Random.permute(a);
Sort.insertionSort(a);
checkSort(a);
Random.permute(a);
Sort.heapsort(a);
checkSort(a);
Random.permute(a);
Sort.shellsort(a);
checkSort(a);
Random.permute(a);
Sort.mergeSort(a);
checkSort(a);
Random.permute(a);
Sort.quicksort(a);
checkSort(a);
Random.permute(a);
Sort.quickSelect(a, NUM_ITEMS / 2);
System.out.println(a[NUM_ITEMS / 2 - 1] + " " + NUM_ITEMS / 2);
}
Integer[] b = new Integer[10_000_000];
for (int i = 0; i < b.length; i++)
b[i] = i;
Random.permute(b);
long start = System.currentTimeMillis();
Sort.quickSelect(b, b.length / 2);
long end = System.currentTimeMillis();
System.out.println("Timing for Section 1.1 example: ");
System.out.println("Selection for N = " + b.length + " takes " +
(end - start) + "ms.");
System.out.println(b[b.length / 2 - 1] + " " + b.length / 2);
}
}