[scode type=”yellow”]堆排序思路[/scode]
- 将传入的数组看作是一个没有完成的堆
- 将堆整理排序成一个大顶堆
- 将大顶堆最大的元素，也就是堆顶，与这个堆最后的元素进行交换
- 然后视这个除刚刚交换的那个元素外的数组为一个堆，对它进行大顶堆标准检查，并将其整理成一个大顶堆
- 有一点需要注意的是每次交换之后接下来需要接着排序的堆的大小需要减一！
- 为了减小空间的占用，可以视交换到末尾的元素为已经出堆的元素，仅仅对这些元素之前的数组进行大顶堆检查。
[scode type=”yellow”]大顶堆概念[/scode]
大顶堆是一个被完全填满的二叉树，除了堆底部的叶子节点以外.其父节点必定要大于它的子节点，由这个特性，我们可以构造大顶堆。
[scode type=”yellow”]堆的数列表示[/scode]
设其父节点的下标为i,那么它的左儿子的下标就是2i+1,其右儿子的下标就是左儿子加一也就是2i+2。
由上面这个下标的规律我们可以直接从整个堆数组的中部开始遍历整个堆，因为观察堆的结构可知，length/2 - 1下标的节点是必定存在有左儿子的，所以我们不用担心下标越界的问题。
[scode type=”yellow”]堆的遍历与调整[/scode]
[scode type=”blue”]遍历的本质就是将每一个元素都访问到，这里可以用递归，也可以用循环，递归对大数据并不友好，所以应该视情况而定！
调整的话主要是实现父节点与子节点的比较，如果父节点小于子节点的较大者，那么就下沉。这里小于较大者的原因是：因为小的元素要下沉就必须要跟两个子树中较大的那个进行交换，否则如果跟较小的节点进行交换的话可能还需要交换两次！。[/scode]
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
|
public class MyHeapSort {
public static void main(String[] args) {
int[] arr = { 50, 10, 90, 30, 70, 40, 80, 60, 20 };
System.out.println("排序之前：");
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
heapSort(arr);
System.out.println();
System.out.println("排序之后：");
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
}
public static void heapSort(int[] arr) {
for (int i = arr.length/2; i >=0; i--) {
heapAdjust(arr, i, arr.length);
}
for (int i = arr.length-1; i >= 0; i--) {
exchange(arr, 0, i);
heapAdjust(arr, 0, i);
}
}
public static void heapAdjust(int[] arr,int root,int length) {
int child;
int father;
for(father = arr[root];2*root+1 < length;root = child){
child = 2*root+1;
if (child != length-1 && arr[child] < arr[child+1]) {
child++;
}
if (father < arr[child]) {
arr[root] = arr[child];
}else{
break;
}
}
arr[root] = father;
}
public static void exchange(int[] arr,int began,int end) {
int temp = arr[began];
arr[began] = arr[end];
arr[end] = temp;
}
public static void heapSort(int[] A, int index) {
int[] temp = createHeap(A,index);
int temp1 = temp[0];
temp[0] = temp[temp.length-1-index];
temp[temp.length-1-index] = temp1;
if (index == A.length-1) {
return;
}
heapSort(temp, ++index);
}
public static int[] createHeap(int[] A,int max) {
int[] B = new int[A.length-max];
for (int i = 0; i < B.length; i++) {
B[i] = A[i];
}
for (int i = B.length / 2 - 1; i >= 0; i--) {
comparePartOfHeapSort(B, i);
}
for (int i = 0; i < B.length; i++) {
A[i] = B[i];
}
return A;
}
public static void comparePartOfHeapSort(int[] A, int index) {
int j = index * 2 + 1;
int k = index * 2 + 2;
if (j < A.length) {
if (A[index] < A[j]) {
int temp = A[index];
A[index] = A[j];
A[j] = temp;
comparePartOfHeapSort(A, j);
}
if (k < A.length && A[index] < A[k]) {
int temp = A[index];
A[index] = A[k];
A[k] = temp;
comparePartOfHeapSort(A, k);
}
return;
} else {
return;
}
}
}
|
