-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathHeapSort.java
More file actions
66 lines (60 loc) · 2.12 KB
/
HeapSort.java
File metadata and controls
66 lines (60 loc) · 2.12 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
package com.yangchd.sort;
/**
* @author yangchd 2018/5/29.
* 堆排序
* 1.将序列构建成大顶堆。
* 2.将根节点与最后一个节点交换，然后断开最后一个节点。
* 3.重复第一、二步，直到所有节点断开。
*/
public class HeapSort {
public void heapSort(int[] a) {
int len = a.length;
//循环建堆
for (int i = 0; i < len - 1; i++) {
//建堆
buildMaxHeap(a, len - 1 - i);
//交换堆顶和最后一个元素
swap(a, 0, len - 1 - i);
}
}
/**
* 对data数组从0到lastIndex建大顶堆
*/
private void buildMaxHeap(int[] data, int lastIndex) {
//从lastIndex处节点（最后一个节点）的父节点开始
for (int i = (lastIndex - 1) / 2; i >= 0; i--) {
//k保存正在判断的节点
int k = i;
//如果当前k节点的子节点存在
while (k * 2 + 1 <= lastIndex) {
//k节点的左子节点的索引
int biggerIndex = 2 * k + 1;
//如果biggerIndex小于lastIndex，即biggerIndex+1代表的k节点的右子节点存在
if (biggerIndex < lastIndex) {
//若果右子节点的值较大
if (data[biggerIndex] < data[biggerIndex + 1]) {
//biggerIndex总是记录较大子节点的索引
biggerIndex++;
}
}
//如果k节点的值小于其较大的子节点的值
if (data[k] < data[biggerIndex]) {
//交换他们
swap(data, k, biggerIndex);
//将biggerIndex赋予k，开始while循环的下一次循环，重新保证k节点的值大于其左右子节点的值
k = biggerIndex;
} else {
break;
}
}
}
}
/**
* 交换方法
*/
private void swap(int[] data, int i, int j) {
int tmp = data[i];
data[i] = data[j];
data[j] = tmp;
}
}