学步园

package ds;

public class HeapSort {

public static void main(String[] args) {

long n = 10000;
int[] arr = { 11, 7, 9, 8, 13, 23, 5, 6, 44, 17, 123, 78, 43, 99, 54,
55, 67, 89, 14, 22, 38, 11, 7, 9, 8, 13, 23, 5, 6, 44, 17, 123,
78, 43, 99, 54, 55, 67, 89, 14, 22, 38, 11, 7, 9, 8, 13, 23, 5,
6, 44, 17, 123, 78, 43, 99, 54, 55, 67, 89, 14, 22, 38, 11, 7,
9, 8, 13, 23, 5, 6, 44, 17, 123, 78, 43, 99, 54, 55, 67, 89,
14, 22, 38, 11, 7, 9, 8, 13, 23, 5, 6, 44, 17, 123, 78, 43, 99,
54, 55, 67, 89, 14, 22, 38, 11, 7, 9, 8, 13, 23, 5, 6, 44, 17,
123, 78, 43, 99, 54, 55, 67, 89, 14, 22, 38, 11, 7, 9, 8, 13,
23, 5, 6, 44, 17, 123, 78, 43, 99, 54, 55, 67, 89, 14, 22, 38,
11, 7, 9, 8, 13, 23, 5, 6, 44, 17, 123, 78, 43, 99, 54, 55, 67,
89, 14, 22, 38, 11, 7, 9, 8, 13, 23, 5, 6, 44, 17, 123, 78, 43,
99, 54, 55, 67, 89, 14, 22, 38, 11, 7, 9, 8, 13, 23, 5, 6, 44,
17, 123, 78, 43, 99, 54, 55, 67, 89, 14, 22, 38, 11, 7, 9, 8,
13, 23, 5, 6, 44, 17, 123, 78, 43, 99, 54, 55, 67, 89, 14, 22,
38, 11, 7, 9, 8, 13, 23, 5, 6, 44, 17, 123, 78, 43, 99, 54, 55,
67, 89, 14, 22, 38, 11, 7, 9, 8, 13, 23, 5, 6, 44, 17, 123, 78,
43, 99, 54, 55, 67, 89, 14, 22, 38, 11, 7, 9, 8, 13, 23, 5, 6,
44, 17, 123, 78, 43, 99, 54, 55, 67, 89, 14, 22, 38, 11, 7, 9,
8, 13, 23, 5, 6, 44, 17, 123, 78, 43, 99, 54, 55, 67, 89, 14,
22, 38, 11, 7, 9, 8, 13, 23, 5, 6, 44, 17, 123, 78, 43, 99, 54,
55, 67, 89, 14, 22, 38, 11, 7, 9, 8, 13, 23, 5, 6, 44, 17, 123,
78, 43, 99, 54, 55, 67, 89, 14, 22, 38, 11, 7, 9, 8, 13, 23, 5,
6, 44, 17, 123, 78, 43, 99, 54, 55, 67, 89, 14, 22, 38, 11, 7,
9, 8, 13, 23, 5, 6, 44, 17, 123, 78, 43, 99, 54, 55, 67, 89,
14, 22, 38, 11, 7, 9, 8, 13, 23, 5, 6, 44, 17, 123, 78, 43, 99,
54, 55, 67, 89, 14, 22, 38, 11, 7, 9, 8, 13, 23, 5, 6, 44, 17,
123, 78, 43, 99, 54, 55, 67, 89, 14, 22, 38, 11, 7, 9, 8, 13,
23, 5, 6, 44, 17, 123, 78, 43, 99, 54, 55, 67, 89, 14, 22, 38,
11, 7, 9, 8, 13, 23, 5, 6, 44, 17, 123, 78, 43, 99, 54, 55, 67,
89, 14, 22, 38, 11, 7, 9, 8, 13, 23, 5, 6, 44, 17, 123, 78, 43,
99, 54, 55, 67, 89, 14, 22, 38, 11, 7, 9, 8, 13, 23, 5, 6, 44,
17, 123, 78, 43, 99, 54, 55, 67, 89, 14, 22, 38, 11, 7, 9, 8,
13, 23, 5, 6, 44, 17, 123, 78, 43, 99, 54, 55, 67, 89, 14, 22,
38, 11, 7, 9, 8, 13, 23, 5, 6, 44, 17, 123, 78, 43, 99, 54, 55,
67, 89, 14, 22, 38, 11, 7, 9, 8, 13, 23, 5, 6, 44, 17, 123, 78,
43, 99, 54, 55, 67, 89, 14, 22, 38, 11, 7, 9, 8, 13, 23, 5, 6,
44, 17, 123, 78, 43, 99, 54, 55, 67, 89, 14, 22, 38, 11, 7, 9,
8, 13, 23, 5, 6, 44, 17, 123, 78, 43, 99, 54, 55, 67, 89, 14,
22, 38, 11, 7, 9, 8, 13, 23, 5, 6, 44, 17, 123, 78, 43, 99, 54,
55, 67, 89, 14, 22, 38, 11, 7, 9, 8, 13, 23, 5, 6, 44, 17, 123,
78, 43, 99, 54, 55, 67, 89, 14, 22, 38 };

System.out.println("整数数组长度：" + arr.length);
System.out.println("排序次数：" + n);

testHeapSort(n);

testBubbleSort(n);

testQuickSort(n);

}

private static void testBubbleSort(long n) {
long start = System.currentTimeMillis();
for (long t = 0; t < n; t++) {

int[] arr = { 11, 7, 9, 8, 13, 23, 5, 6, 44, 17, 123, 78, 43, 99, 54,
55, 67, 89, 14, 22, 38, 11, 7, 9, 8, 13, 23, 5, 6, 44, 17, 123,
78, 43, 99, 54, 55, 67, 89, 14, 22, 38, 11, 7, 9, 8, 13, 23, 5,
6, 44, 17, 123, 78, 43, 99, 54, 55, 67, 89, 14, 22, 38, 11, 7,
9, 8, 13, 23, 5, 6, 44, 17, 123, 78, 43, 99, 54, 55, 67, 89,
14, 22, 38, 11, 7, 9, 8, 13, 23, 5, 6, 44, 17, 123, 78, 43, 99,
54, 55, 67, 89, 14, 22, 38, 11, 7, 9, 8, 13, 23, 5, 6, 44, 17,
123, 78, 43, 99, 54, 55, 67, 89, 14, 22, 38, 11, 7, 9, 8, 13,
23, 5, 6, 44, 17, 123, 78, 43, 99, 54, 55, 67, 89, 14, 22, 38,
11, 7, 9, 8, 13, 23, 5, 6, 44, 17, 123, 78, 43, 99, 54, 55, 67,
89, 14, 22, 38, 11, 7, 9, 8, 13, 23, 5, 6, 44, 17, 123, 78, 43,
99, 54, 55, 67, 89, 14, 22, 38, 11, 7, 9, 8, 13, 23, 5, 6, 44,
17, 123, 78, 43, 99, 54, 55, 67, 89, 14, 22, 38, 11, 7, 9, 8,
13, 23, 5, 6, 44, 17, 123, 78, 43, 99, 54, 55, 67, 89, 14, 22,
38, 11, 7, 9, 8, 13, 23, 5, 6, 44, 17, 123, 78, 43, 99, 54, 55,
67, 89, 14, 22, 38, 11, 7, 9, 8, 13, 23, 5, 6, 44, 17, 123, 78,
43, 99, 54, 55, 67, 89, 14, 22, 38, 11, 7, 9, 8, 13, 23, 5, 6,
44, 17, 123, 78, 43, 99, 54, 55, 67, 89, 14, 22, 38, 11, 7, 9,
8, 13, 23, 5, 6, 44, 17, 123, 78, 43, 99, 54, 55, 67, 89, 14,
22, 38, 11, 7, 9, 8, 13, 23, 5, 6, 44, 17, 123, 78, 43, 99, 54,
55, 67, 89, 14, 22, 38, 11, 7, 9, 8, 13, 23, 5, 6, 44, 17, 123,
78, 43, 99, 54, 55, 67, 89, 14, 22, 38, 11, 7, 9, 8, 13, 23, 5,
6, 44, 17, 123, 78, 43, 99, 54, 55, 67, 89, 14, 22, 38, 11, 7,
9, 8, 13, 23, 5, 6, 44, 17, 123, 78, 43, 99, 54, 55, 67, 89,
14, 22, 38, 11, 7, 9, 8, 13, 23, 5, 6, 44, 17, 123, 78, 43, 99,
54, 55, 67, 89, 14, 22, 38, 11, 7, 9, 8, 13, 23, 5, 6, 44, 17,
123, 78, 43, 99, 54, 55, 67, 89, 14, 22, 38, 11, 7, 9, 8, 13,
23, 5, 6, 44, 17, 123, 78, 43, 99, 54, 55, 67, 89, 14, 22, 38,
11, 7, 9, 8, 13, 23, 5, 6, 44, 17, 123, 78, 43, 99, 54, 55, 67,
89, 14, 22, 38, 11, 7, 9, 8, 13, 23, 5, 6, 44, 17, 123, 78, 43,
99, 54, 55, 67, 89, 14, 22, 38, 11, 7, 9, 8, 13, 23, 5, 6, 44,
17, 123, 78, 43, 99, 54, 55, 67, 89, 14, 22, 38, 11, 7, 9, 8,
13, 23, 5, 6, 44, 17, 123, 78, 43, 99, 54, 55, 67, 89, 14, 22,
38, 11, 7, 9, 8, 13, 23, 5, 6, 44, 17, 123, 78, 43, 99, 54, 55,
67, 89, 14, 22, 38, 11, 7, 9, 8, 13, 23, 5, 6, 44, 17, 123, 78,
43, 99, 54, 55, 67, 89, 14, 22, 38, 11, 7, 9, 8, 13, 23, 5, 6,
44, 17, 123, 78, 43, 99, 54, 55, 67, 89, 14, 22, 38, 11, 7, 9,
8, 13, 23, 5, 6, 44, 17, 123, 78, 43, 99, 54, 55, 67, 89, 14,
22, 38, 11, 7, 9, 8, 13, 23, 5, 6, 44, 17, 123, 78, 43, 99, 54,
55, 67, 89, 14, 22, 38, 11, 7, 9, 8, 13, 23, 5, 6, 44, 17, 123,
78, 43, 99, 54, 55, 67, 89, 14, 22, 38 };
bubbleSort(arr);
}
long end = System.currentTimeMillis();
System.out.println("BubbleSort:" + (end - start) + " ms");
}

private static void bubbleSort(int[] arr) {
for (int i = 0; i < arr.length - 1; i++) {
for (int j = i + 1; j < arr.length; j++) {
if (arr[i] > arr[j]) {
DsUtils.swap(arr, i, j);
}
}
// DsUtils.printArray(arr);
}
}

private static void testHeapSort(long n) {
long start = System.currentTimeMillis();
for (long t = 0; t < n; t++) {

int[] arr = { 11, 7, 9, 8, 13, 23, 5, 6, 44, 17, 123, 78, 43, 99, 54,
55, 67, 89, 14, 22, 38, 11, 7, 9, 8, 13, 23, 5, 6, 44, 17, 123,
78, 43, 99, 54, 55, 67, 89, 14, 22, 38, 11, 7, 9, 8, 13, 23, 5,
6, 44, 17, 123, 78, 43, 99, 54, 55, 67, 89, 14, 22, 38, 11, 7,
9, 8, 13, 23, 5, 6, 44, 17, 123, 78, 43, 99, 54, 55, 67, 89,
14, 22, 38, 11, 7, 9, 8, 13, 23, 5, 6, 44, 17, 123, 78, 43, 99,
54, 55, 67, 89, 14, 22, 38, 11, 7, 9, 8, 13, 23, 5, 6, 44, 17,
123, 78, 43, 99, 54, 55, 67, 89, 14, 22, 38, 11, 7, 9, 8, 13,
23, 5, 6, 44, 17, 123, 78, 43, 99, 54, 55, 67, 89, 14, 22, 38,
11, 7, 9, 8, 13, 23, 5, 6, 44, 17, 123, 78, 43, 99, 54, 55, 67,
89, 14, 22, 38, 11, 7, 9, 8, 13, 23, 5, 6, 44, 17, 123, 78, 43,
99, 54, 55, 67, 89, 14, 22, 38, 11, 7, 9, 8, 13, 23, 5, 6, 44,
17, 123, 78, 43, 99, 54, 55, 67, 89, 14, 22, 38, 11, 7, 9, 8,
13, 23, 5, 6, 44, 17, 123, 78, 43, 99, 54, 55, 67, 89, 14, 22,
38, 11, 7, 9, 8, 13, 23, 5, 6, 44, 17, 123, 78, 43, 99, 54, 55,
67, 89, 14, 22, 38, 11, 7, 9, 8, 13, 23, 5, 6, 44, 17, 123, 78,
43, 99, 54, 55, 67, 89, 14, 22, 38, 11, 7, 9, 8, 13, 23, 5, 6,
44, 17, 123, 78, 43, 99, 54, 55, 67, 89, 14, 22, 38, 11, 7, 9,
8, 13, 23, 5, 6, 44, 17, 123, 78, 43, 99, 54, 55, 67, 89, 14,
22, 38, 11, 7, 9, 8, 13, 23, 5, 6, 44, 17, 123, 78, 43, 99, 54,
55, 67, 89, 14, 22, 38, 11, 7, 9, 8, 13, 23, 5, 6, 44, 17, 123,
78, 43, 99, 54, 55, 67, 89, 14, 22, 38, 11, 7, 9, 8, 13, 23, 5,
6, 44, 17, 123, 78, 43, 99, 54, 55, 67, 89, 14, 22, 38, 11, 7,
9, 8, 13, 23, 5, 6, 44, 17, 123, 78, 43, 99, 54, 55, 67, 89,
14, 22, 38, 11, 7, 9, 8, 13, 23, 5, 6, 44, 17, 123, 78, 43, 99,
54, 55, 67, 89, 14, 22, 38, 11, 7, 9, 8, 13, 23, 5, 6, 44, 17,
123, 78, 43, 99, 54, 55, 67, 89, 14, 22, 38, 11, 7, 9, 8, 13,
23, 5, 6, 44, 17, 123, 78, 43, 99, 54, 55, 67, 89, 14, 22, 38,
11, 7, 9, 8, 13, 23, 5, 6, 44, 17, 123, 78, 43, 99, 54, 55, 67,
89, 14, 22, 38, 11, 7, 9, 8, 13, 23, 5, 6, 44, 17, 123, 78, 43,
99, 54, 55, 67, 89, 14, 22, 38, 11, 7, 9, 8, 13, 23, 5, 6, 44,
17, 123, 78, 43, 99, 54, 55, 67, 89, 14, 22, 38, 11, 7, 9, 8,
13, 23, 5, 6, 44, 17, 123, 78, 43, 99, 54, 55, 67, 89, 14, 22,
38, 11, 7, 9, 8, 13, 23, 5, 6, 44, 17, 123, 78, 43, 99, 54, 55,
67, 89, 14, 22, 38, 11, 7, 9, 8, 13, 23, 5, 6, 44, 17, 123, 78,
43, 99, 54, 55, 67, 89, 14, 22, 38, 11, 7, 9, 8, 13, 23, 5, 6,
44, 17, 123, 78, 43, 99, 54, 55, 67, 89, 14, 22, 38, 11, 7, 9,
8, 13, 23, 5, 6, 44, 17, 123, 78, 43, 99, 54, 55, 67, 89, 14,
22, 38, 11, 7, 9, 8, 13, 23, 5, 6, 44, 17, 123, 78, 43, 99, 54,
55, 67, 89, 14, 22, 38, 11, 7, 9, 8, 13, 23, 5, 6, 44, 17, 123,
78, 43, 99, 54, 55, 67, 89, 14, 22, 38 };
heapSort(arr);
}
long end = System.currentTimeMillis();
System.out.println("HeapSort:" + (end - start) + " ms");
}

private static void heapSort(int[] arr) {
for (int i = arr.length - 1; i > 0; i--) {
builtHeap(arr, i);
DsUtils.swap(arr, 0, i);
// DsUtils.print(i);
// DsUtils.printArray(arr);
}
}

private static void builtHeap(int[] ia, int pos) {
int c = pos;
int p = 0;
while (c > 0) {
p = (c - 1) >> 1;
if (ia[c] > ia[p]) {
DsUtils.swap(ia, c, p);
}
c--;
}
}

private static void testQuickSort(long n) {
long start = System.currentTimeMillis();
for (long t = 0; t < n; t++) {

int[] arr = { 11, 7, 9, 8, 13, 23, 5, 6, 44, 17, 123, 78, 43, 99, 54,
55, 67, 89, 14, 22, 38, 11, 7, 9, 8, 13, 23, 5, 6, 44, 17, 123,
78, 43, 99, 54, 55, 67, 89, 14, 22, 38, 11, 7, 9, 8, 13, 23, 5,
6, 44, 17, 123, 78, 43, 99, 54, 55, 67, 89, 14, 22, 38, 11, 7,
9, 8, 13, 23, 5, 6, 44, 17, 123, 78, 43, 99, 54, 55, 67, 89,
14, 22, 38, 11, 7, 9, 8, 13, 23, 5, 6, 44, 17, 123, 78, 43, 99,
54, 55, 67, 89, 14, 22, 38, 11, 7, 9, 8, 13, 23, 5, 6, 44, 17,
123, 78, 43, 99, 54, 55, 67, 89, 14, 22, 38, 11, 7, 9, 8, 13,
23, 5, 6, 44, 17, 123, 78, 43, 99, 54, 55, 67, 89, 14, 22, 38,
11, 7, 9, 8, 13, 23, 5, 6, 44, 17, 123, 78, 43, 99, 54, 55, 67,
89, 14, 22, 38, 11, 7, 9, 8, 13, 23, 5, 6, 44, 17, 123, 78, 43,
99, 54, 55, 67, 89, 14, 22, 38, 11, 7, 9, 8, 13, 23, 5, 6, 44,
17, 123, 78, 43, 99, 54, 55, 67, 89, 14, 22, 38, 11, 7, 9, 8,
13, 23, 5, 6, 44, 17, 123, 78, 43, 99, 54, 55, 67, 89, 14, 22,
38, 11, 7, 9, 8, 13, 23, 5, 6, 44, 17, 123, 78, 43, 99, 54, 55,
67, 89, 14, 22, 38, 11, 7, 9, 8, 13, 23, 5, 6, 44, 17, 123, 78,
43, 99, 54, 55, 67, 89, 14, 22, 38, 11, 7, 9, 8, 13, 23, 5, 6,
44, 17, 123, 78, 43, 99, 54, 55, 67, 89, 14, 22, 38, 11, 7, 9,
8, 13, 23, 5, 6, 44, 17, 123, 78, 43, 99, 54, 55, 67, 89, 14,
22, 38, 11, 7, 9, 8, 13, 23, 5, 6, 44, 17, 123, 78, 43, 99, 54,
55, 67, 89, 14, 22, 38, 11, 7, 9, 8, 13, 23, 5, 6, 44, 17, 123,
78, 43, 99, 54, 55, 67, 89, 14, 22, 38, 11, 7, 9, 8, 13, 23, 5,
6, 44, 17, 123, 78, 43, 99, 54, 55, 67, 89, 14, 22, 38, 11, 7,
9, 8, 13, 23, 5, 6, 44, 17, 123, 78, 43, 99, 54, 55, 67, 89,
14, 22, 38, 11, 7, 9, 8, 13, 23, 5, 6, 44, 17, 123, 78, 43, 99,
54, 55, 67, 89, 14, 22, 38, 11, 7, 9, 8, 13, 23, 5, 6, 44, 17,
123, 78, 43, 99, 54, 55, 67, 89, 14, 22, 38, 11, 7, 9, 8, 13,
23, 5, 6, 44, 17, 123, 78, 43, 99, 54, 55, 67, 89, 14, 22, 38,
11, 7, 9, 8, 13, 23, 5, 6, 44, 17, 123, 78, 43, 99, 54, 55, 67,
89, 14, 22, 38, 11, 7, 9, 8, 13, 23, 5, 6, 44, 17, 123, 78, 43,
99, 54, 55, 67, 89, 14, 22, 38, 11, 7, 9, 8, 13, 23, 5, 6, 44,
17, 123, 78, 43, 99, 54, 55, 67, 89, 14, 22, 38, 11, 7, 9, 8,
13, 23, 5, 6, 44, 17, 123, 78, 43, 99, 54, 55, 67, 89, 14, 22,
38, 11, 7, 9, 8, 13, 23, 5, 6, 44, 17, 123, 78, 43, 99, 54, 55,
67, 89, 14, 22, 38, 11, 7, 9, 8, 13, 23, 5, 6, 44, 17, 123, 78,
43, 99, 54, 55, 67, 89, 14, 22, 38, 11, 7, 9, 8, 13, 23, 5, 6,
44, 17, 123, 78, 43, 99, 54, 55, 67, 89, 14, 22, 38, 11, 7, 9,
8, 13, 23, 5, 6, 44, 17, 123, 78, 43, 99, 54, 55, 67, 89, 14,
22, 38, 11, 7, 9, 8, 13, 23, 5, 6, 44, 17, 123, 78, 43, 99, 54,
55, 67, 89, 14, 22, 38, 11, 7, 9, 8, 13, 23, 5, 6, 44, 17, 123,
78, 43, 99, 54, 55, 67, 89, 14, 22, 38 };
quickSort(arr);
}
long end = System.currentTimeMillis();
System.out.println("QuickSort:" + (end - start) + " ms");
}

private static void quickSort(int[] ia) {
quickSort(ia, 0, ia.length - 1);
}

private static void quickSort(int[] ia, int k1, int k2) {

if (k1 < k2 && k1 > -1) {

if (k1 == k2 - 1) {
if (ia[k1] > ia[k2]) {
DsUtils.swap(ia, k1, k2);
}
} else {

int i = k1;
int m1 = k1 + 1;
int m2 = k2;
while (m1 < m2) {

while (ia[m1] < ia[i] && m1 <= m2) {
DsUtils.swap(ia, m1, i);
i = m1++;
}
while (ia[m2] > ia[i] && m1 <= m2) {
m2--;
}
if (ia[m2] < ia[i] && m1 <= m2) {
DsUtils.swap(ia, i, m1, m2);
i = m1++;
}
m2--;
}

quickSort(ia, k1, i - 1);
quickSort(ia, i + 1, k2);

}
}
}

}

整数数组长度：672
排序次数：10000
堆排序HeapSort:19875 ms
冒泡排序BubbleSort:25328 ms
快速排序QuickSort:3750 ms