本文实例讲述了java堆排序原理与实现方法。分享给大家供大家参考，具体如下：
堆是一个数组，被看成一个近似完全二叉树。
举例说明：
堆的性质：
1.已知元素在数组中的序号为i
其父节点的序号为 i/2的整数
其左孩子节点的序号为2*i
其右孩子节点的序号为2*i+1
2.堆分为最大堆和最小堆
在最大堆中，要保证父节点的值大于等于其孩子节点的值
在最小堆中，要保证父节点的值小于等于其孩子节点的值
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
|
public class myheapsort { public void heap_sort(int[] a) { /** * 这个函数完成堆排序 * 先构建一个最大堆 * 将数组中第一个元素和最后一个交换， * 堆的长度减一 * 在从第一个位置开始保证堆的性质调用max_heapify()函数。 * 这样保证目前最大的元素在数组的最后位置。 * 以此类推，直到最后一个元素。 */ build_max_heap(a); for (int i = a.length - 1; i >= 1; i--) { int temp = a[0]; a[0] = a[i]; a[i] = temp; max_heapify(a, 0, i); } } public void build_max_heap(int[] a) { /** * 这个函数用来构建堆 * a:待排序的数组 * （for循环中i的值从数组长度的一般开始取，是因为完全二叉树的性质， * 一半的节点叶根节点所以从叶节点开始向上遍历来保证堆的性质） */ for (int i = a.length/2; i >= 0; i--) { max_heapify(a, i, a.length); } } public void max_heapify(int[] a, int i, int heap_size) { /**这个函数用来维护堆的性质， * 保证以序号为i的元素为根节点的子树中，父节点的值大于其孩子节点的值。 * a:待排序数组 * i：在数组a中的序号 * heap_size:堆的大小 */ int largest = i; int l = i * 2 + 1; int r = i * 2 + 2; if (l < heap_size && a[l] > a[i]) largest = l; if (r < heap_size && a[r] > a[largest]) largest = r; if (largest != i) { int temp = a[i]; a[i] = a[largest]; a[largest] = temp; max_heapify(a, largest, heap_size); } } public static void main(string[] args) throws exception { system.out.println("服务器之家测试结果："); int[] a = new int[]{1,3,2,5,34,23,44,15,67,45}; new myheapsort().heap_sort(a); for (int x : a) system.out.println(x); }} |
代码中例子的运行结果：
希望本文所述对大家java程序设计有所帮助。
原文链接：https://blog.csdn.net/u014028027/article/details/78626416
