[Java] 纯文本查看 复制代码
1 public class HeapSort
2 {
3 public static void main(String[] args)
4 {
5 int[] arr = { 50, 10, 90, 30, 70, 40, 80, 60, 20 };
6 System.out.println("排序之前：");
7 for (int i = 0; i < arr.length; i++)
8 System.out.print(arr + " ");
9
10 // 堆排序
11 heapSort(arr);
12 System.out.println();
13 System.out.println("排序之后：");
14 for (int i = 0; i < arr.length; i++)
15 System.out.print(arr + " ");
16 }
17
18 /**
19 * 堆排序
20 */
21 private static void heapSort(int[] arr)
22 {
23 // 将待排序的序列构建成一个大顶堆
24 for (int i = arr.length / 2; i >= 0; i--)
25 heapAdjust(arr, i, arr.length);
26
27 // 逐步将每个最大值的根节点与末尾元素交换，并且再调整二叉树，使其成为大顶堆
28 for (int i = arr.length - 1; i > 0; i--)
29 {
30 swap(arr, 0, i); // 将堆顶记录和当前未经排序子序列的最后一个记录交换
31 heapAdjust(arr, 0, i); // 交换之后，需要重新检查堆是否符合大顶堆，不符合则要调整
32 }
33 }
34 /**
35 * 构建堆的过程
36 * @param arr 需要排序的数组
37 * @param i 需要构建堆的根节点的序号
38 * @param n 数组的长度
39 */
40 private static void heapAdjust(int[] arr, int i, int n)
41 {
42 int child;
43 int father;
44 for (father = arr; leftChild(i) < n; i = child)
45 {
46 child = leftChild(i);
47 // 如果左子树小于右子树，则需要比较右子树和父节点
48 if (child != n - 1 && arr[child] < arr[child + 1])
49 child++; // 序号增1，指向右子树
50 // 如果父节点小于孩子结点，则需要交换
51 if (father < arr[child])
52 arr = arr[child];
53 else
54 break; // 大顶堆结构未被破坏，不需要调整
55 }
56 arr = father;
57 }
58
59 // 获取到左孩子结点
60 private static int leftChild(int i)
61 {
62 return 2 * i + 1;
63 }
64
65 // 交换元素位置
66 private static void swap(int[] arr, int index1, int index2)
67 {
68 int tmp = arr[index1];
69 arr[index1] = arr[index2];
70 arr[index2] = tmp;
71 }
72 }