堆是一种特殊的完全二叉树，其特点是所有父节点都比子节点要小，或者所有父节点都比字节点要大。前一种称为最小堆，后一种称为最大堆。
比如下面这两个：
那么这个特性有什么作用？既然题目是堆排序，那么肯定能用来排序。想要用堆排序首先要创建一个堆，如果对4 3 6 2 7 1 5这七个数字做从小到大排序，需要用这七个数创建一个最大堆，来看代码：
|
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
|
public class heapsort {
private int[] numbers;
private int length;
public heapsort(int[] numbers) {
this.numbers = numbers;
this.length = numbers.length;
}
/**
* 调整二叉树
* 如果父节点编号为x, 那么左子节点的编号是2x, 右子节点的编号是2x+1
* 节点编号从1开始, 对应数组中的索引是编号-1
* @param nodeid 节点编号, 从1开始
*/
public void adjust(int nodeid) {
int swapid;
int flag = 0; //是否需要继续向下调整
while(nodeid * 2 <= this.length && flag == 0) {
//首先判断它和左子节点的关系, 并用swapid记录值较小的节点编号(最大堆是记录较大的)
int index = nodeid - 1; //节点对应数组中数字的索引
int leftchild = nodeid * 2 - 1; //左子节点对应数组中数字的索引
int rightchild = nodeid * 2; //右子节点对应数组中数字的索引
if(numbers[index] < numbers[leftchild]) {
swapid = nodeid * 2;
} else {
swapid = nodeid;
}
//如果有右子节点, 再与右子节点比较
if(nodeid * 2 + 1 <= this.length) {
if(numbers[swapid - 1] < numbers[rightchild])
swapid = nodeid * 2 + 1;
}
//如果最小的节点编号不是自己, 说明子节点中有比父节点更小的
if(swapid != nodeid) {
swap(swapid, nodeid);
nodeid = swapid;
} else {
flag = 1;
}
}
}
/**
* 交换两个节点的值
* @param nodeid1
* @param nodeid2
*/
public void swap(int nodeid1, int nodeid2) {
int t = numbers[nodeid1 - 1];
numbers[nodeid1 - 1] = numbers[nodeid2 - 1];
numbers[nodeid2 - 1] = t;
}
/**
* 创建最大堆
*/
public void createmaxheap() {
//从最后一个非叶节点到第一个节点依次向上调整
for(int i = this.length / 2; i >= 1; i--) {
adjust(i);
}
}
public static void main(string[] args) {
int[] numbers = new int[] { 4, 3, 6, 2, 7, 1, 5 };
for(int x = 0; x < numbers.length; x++) {
system.out.print(numbers[x] + " ");
}
system.out.println();
heapsort heap = new heapsort(numbers);
heap.createmaxheap();
}
}
|
对本例中的数列，从this.length / 2到1，共执行了三轮循环。
第一轮：
第二轮：
第三轮：
调整完成后，当前的二叉树已经符合最大堆的特性，可以用来从小到大排序。堆排序的原理是，交换堆顶和最后一个节点的数字，即把最大的数字放到数组最后，然后对除了最大数的前n-1个数从新执行调整过程，使其符合最大堆特性。重复以上过程直到堆中只剩下一个数字。
|
1
2
3
4
5
6
7
8
9
10
|
public void sort() {
while(this.length > 1) {
swap(1, this.length);
this.length--;
adjust(1);
}
for(int x = 0; x < numbers.length; x++) {
system.out.print(numbers[x] + " ");
}
}
|
堆排序的时间复杂度和快速排序的平均时间复杂度一样，是o(nlogn)。
总结
以上就是本文关于java算法之堆排序代码示例的全部内容，希望对大家有所帮助。有什么问题可以随时留言，小编会及时回复大家的。感谢朋友们对本站的支持！
原文链接：https://www.2cto.com/kf/201609/549030.html