-
Notifications
You must be signed in to change notification settings - Fork 1
/
HeasportEx.java
94 lines (81 loc) · 1.9 KB
/
HeasportEx.java
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
package chapterSeven;
/**
* 堆排序:跟二叉堆的最小值优先不一样,为了满足排序时的升序顺序,
* 我们调整二叉堆为最大值优先,并且从0开始记数组。
*
* @Author: dhcao
* @Version: 1.0
*/
public class HeasportEx<T extends Comparable<? super T>> {
/**
* 左儿子,
* 二叉堆的下标从1开始,这里明显从0开始,所以左儿子需要 +1 返回
*
* @param i
* @return
*/
private static int leftChild(int i) {
return 2 * i + 1;
}
/**
* 下滤
*
* @param a 堆数组
* @param i 下滤节点位置
* @param n 二叉堆大小
* @param <T>
*/
private static <T extends Comparable<? super T>> void percDown(T[] a, int i, int n) {
int child;
T 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;
}
/**
* 堆排序
*
* @param a 排序数组
* @param <T>
*/
public static <T extends Comparable<? super T>> void heapsort(T[] a) {
for (int i = a.length / 2 - 1; i >= 0; i--) {
percDown(a, i, a.length);
}
for (int i = a.length - 1; i > 0; i--) {
swapReferences(a, 0, i);
percDown(a, 0, i);
}
}
/**
* 交换位置
* @param <T>
*/
public static <T extends Comparable<? super T>> void swapReferences(T[] a, int i, int n) {
T tmp = a[i];
a[i] = a[n];
a[n] = tmp;
}
public static void main(String[] args) {
Integer[] aaa = {1,5,2,5,3,4,6,3,7};
for (int i = 0; i < aaa.length; i++) {
System.out.print(aaa[i]+" ");
}
System.out.println("");
heapsort(aaa);
for (int i = 0; i < aaa.length; i++) {
System.out.print(aaa[i]+" ");
}
}
}