接上文
7 堆排序（Heap Sort）
堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。堆排序可以说是一种利用堆的概念来排序的选择排序。分为两种方法：
大顶堆：每个节点的值都大于或等于其子节点的值，在堆排序算法中用于升序排列；
小顶堆：每个节点的值都小于或等于其子节点的值，在堆排序算法中用于降序排列；
堆排序的平均时间复杂度为 Ο(nlogn)。
算法描述
将待排序序列构建成一个堆 H[0……n-1]，根据（升序降序需求）选择大顶堆或小顶堆；
把堆首（最大值）和堆尾互换；
把堆的尺寸缩小 1，并调用 shift_down(0)，目的是把新的数组顶端数据调整到相应位置；
重复步骤 2，直到堆的尺寸为 1。
动图演示
详解
下图是一棵深度为4的完全二叉树
堆（二叉堆）可以视为一棵完全的二叉树。完全二叉树的一个“优秀”的性质是，除了最底层之外，其余每一层都是满的，这使得堆可以利用数组来表示（普通的一般的二叉树通常用链表作为基本容器表示），每一个结点对应数组中的一个元素。
如下图，是一个堆和数组的相互关系。
对于给定的某个节点的下标i，可以很容易的计算出这个结点的父结点、孩子结点的下标：
Parent(i) = i/2 // i 父节点的下标
Left(i) = 2i // i 左子节点的下标
Right(i) = 2i + 1 // i 右子节点的下标
堆（二叉堆）又分为2种：最大堆（大顶堆）、最小堆（小顶堆）。
大顶堆
堆中的最大元素值出现在根结点（堆顶）
堆中每个父节点的元素值都大于等于其孩子结点（如果存在）
小顶堆
堆中的最小元素值出现在根结点（堆顶）
堆中每个父节点的元素值都小于等于其孩子结点（如果存在）
堆排序就是把最大堆堆顶的最大数取出，将剩余的堆继续调整为最大堆，再次将堆顶的最大数取出，这个过程持续到剩余数只有一个时结束。在堆中定义以下几种操作：
堆调整
建堆
继续进行下面的讨论前，需要注意的一个问题是：数组都是 Zero-Based，这就意味着我们的堆数据结构模型要发生改变：
相应的，几个计算公式也要作出相应调整：
Parent(i) = (i-1)/2 // i 父节点下标
Left(i) = 2i + 1 // i 左子节点下标
Right(i) = 2i + 2 // i 右子节点下标
堆调整
最大堆调整（Max‐Heapify）的作用是保持最大堆的性质，是创建最大堆的核心子程序，过程如图所示：
由于一次调整后，堆仍然违反堆性质，所以需要递归的测试，使得整个堆都满足堆性质。
1/**
2 * 最大堆调整
3 *
4 * @param index 检查起始的下标
5 * @param heapSize 堆大小
6 */
7 public void heapify(int[] array, int index, int heapSize) {
8 int left = 2 * index + 1;// 左孩子的下标（如果存在的话）
9 int right = 2 * index + 2;// 左孩子的下标（如果存在的话）
10 int iMax = index;// 寻找3个节点中最大值节点的下标
11 if (left < heapSize && array[left] > array[index]) {
12 iMax = left;
13 }
14 if (right < heapSize && array[right] > array[iMax]) {
15 iMax = right;
16 }
17 if (iMax != index) {
18 swap(array, iMax, index);
19 heapify(array, iMax, heapSize);
20 }
21 }
22
23 public void swap(int[] array, int i, int j) {
24 int temp = array[i];
25 array[i] = array[j];
26 array[j] = temp;
27 }
28
29```java
30
31递归在调用递归子函数的时候，会先将传给子函数的参数压栈，然后将当前指令的下一条指令的地址压栈，以便子函数执行完后返回到原函数中继续执行，在原函数继续执行之前还涉及到清理子函数的栈。因此，递归的效率比迭代低一点点。其实上面的调整堆也可以用迭代来实现：
32
33```cpp
34public void heapify(int[] array, int index, int heapSize) {
35 int left, right, iMax;
36 while (true) {
37 left = 2 * index + 1;// 左孩子的下标（如果存在的话）
38 right = 2 * index + 2;// 左孩子的下标（如果存在的话）
39 iMax = index;// 寻找3个节点中最大值节点的下标
40 if (left < heapSize && array[left] > array[index]) {
41 iMax = left;
42 }
43 if (right < heapSize && array[right] > array[iMax]) {
44 iMax = right;
45 }
46 if (iMax != index) {
47 swap(array, iMax, index);
48 index = iMax;
49 } else {
50 break;
51 }
52 }
53 }
54
55```java
56
57### 建堆
58
59创建最大堆（Build-Max-Heap）的作用是将一个数组改造成一个最大堆，接受数组和堆大小两个参数，Build-Max-Heap 将自下而上的调用 Max-Heapify 来改造数组，建立最大堆。**因为 Max-Heapify 能够保证下标 i 的结点之后结点都满足最大堆的性质，所以自下而上的调用 Max-Heapify 能够在改造过程中保持这一性质。**如果最大堆的数量元素是 n，那么 Build-Max-Heap 从 Parent(n) 开始，往上依次调用 Max-Heapify。流程如下：
60
61
62
63```cpp
64public void buildHeap(int[] array) {
65 int n = array.length;// 数组中元素的个数
66 for (int i = n / 2 - 1; i >= 0; i--)
67 heapify(array, i, n);
68}
69
70```java
71
72### 堆排序
73
74堆排序（Heap-Sort）先调用Build-Max-Heap将原数组改造为最大堆，这个时候堆顶元素最大，将其与堆底（当前堆对应数组的最后一个元素）交换，堆的大小减去1，当前堆堆底后面的元素已经排好序。然后，从堆顶元素开始检查，调用Max-Heapify保持最大堆性质，这样可以将第二大的元素调到堆顶，然后将其与当前堆堆底元素交换。重复这个过程n-1次，直到堆中只有1个元素为止。整个流程如下：
75
76
77
78**完整代码实现**
79
80```java
81public class HeapSort implements IArraySort {
82
83 @Override
84 public int[] sort(int[] sourceArray) throws Exception {
85 // 对 arr 进行拷贝，不改变参数内容
86 int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);
87
88 int len = arr.length;
89
90 buildMaxHeap(arr, len);
91
92 for (int i = len - 1; i > 0; i--) {
93 swap(arr, 0, i);
94 len--;
95 heapify(arr, 0, len);
96 }
97 return arr;
98 }
99
100 private void buildMaxHeap(int[] arr, int len) {
101 for (int i = (int) Math.floor(len / 2); i >= 0; i--) {
102 heapify(arr, i, len);
103 }
104 }
105
106 private void heapify(int[] arr, int i, int len) {
107 int left = 2 * i + 1;
108 int right = 2 * i + 2;
109 int largest = i;
110
111 if (left < len && arr[left] > arr[largest]) {
112 largest = left;
113 }
114
115 if (right < len && arr[right] > arr[largest]) {
116 largest = right;
117 }
118
119 if (largest != i) {
120 swap(arr, i, largest);
121 heapify(arr, largest, len);
122 }
123 }
124
125 private void swap(int[] arr, int i, int j) {
126 int temp = arr[i];
127 arr[i] = arr[j];
128 arr[j] = temp;
129 }
130
131}
参考
关注公众号 获取更多精彩内容