常见的排序算法（七）：堆排序

　　堆排序（英语：Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构，并同时满足堆积的性质：即子节点的键值或索引总是小于（或者大于）它的父节点。

　　堆是通过一维数组来实现的。在数组起始位置为0(根节点)的情形中：

父节点i的左子节点在位置(2i+1)
父节点i的右子节点在位置 $(2i+2)$
子节点i的父节点在位置floor $((i-1)/2)$

　　若以升序排序说明，把数组转换成最大堆积(Max-Heap Heap)，这是一种满足最大堆积性质(Max-Heap Property)的二叉树：对于除了根之外的每个节点i, A[parent(i)] ≥ A[i]。

　　重复从最大堆积取出数值最大的结点，把根结点和最后一个结点交换，把交换后的最后一个结点移出堆)，并让残余的堆积维持最大堆积性质。

　　通俗来说就是把数组维持成一个最大堆，最大堆的根节点是最大的数值，然后与数组最后一个元素交换，并把最后那个位置移除堆，剩下的堆因为交换过去的元素破坏了最大堆的性质，所以要维持最大堆的性质，再继续把最大的根节点与堆数组的最后一个交换，重复值堆中只有两个元素，最后两个元素比较后叫完成了排序。

堆排序算法如下：

　　维持最大堆的函数

 1     /**
 2      * 调整索引为 index 处的数据，使其符合堆的特性。
 3      *
 4      * @param index 需要堆化处理的数据的索引
 5      * @param len 未排序的堆（数组）的长度
 6      */
 7     private void maxHeapify(int index, int len) {
 8         int li = (index << 1) + 1;  // 左子节点索引
 9         int ri = li + 1;            // 右子节点索引
10         int cMax = li;              // 子节点值最大索引，默认左子节点。
11         if(li > len)                // 左子节点索引超出计算范围，直接返回。
12             return;
13         if(ri <= len && arr[ri] > arr[li]) // 先判断左右子节点，哪个较大。
14             cMax = ri;
15         if(arr[cMax] > arr[index]) {
16             swap(cMax, index);      // 如果父节点被子节点调换，
17             maxHeapify(cMax, len);  // 则需要继续判断换下后的父节点是否符合堆的特性。
18         }
19     }

堆调整的时间复杂度：

　　从堆调整的代码可以看到是当前节点与其值较大的子节点(子节点比较一次)比较，交换一次。父节点与哪一个子节点进行交换，就对该子节点递归进行此操作，设对调整的时间复杂度为T(k)（k为该层节点到叶节点的距离），那么有
　　T(k)=T(k-1)+3, k∈[2,h]
　　T(1)=3
　　迭代法计算结果为：
　　　　T(h)=3h=3 floor(log n)
　　所以堆调整的时间复杂度是O(log n) 。

建堆的时间复杂度：

　　n个节点的堆，树高度是h=floor(log n)。对深度为于 h-1 层的节点，比较2次，交换1次，这一层最多有2^(h-1)个节点，总共操作次数最多为3*2^(h-1))；对深度为h-2层的节点，总共有2^(h-2)个，每个节点最多比较4次，交换2次，所以操作次数最多为3*2^(h-2))……
　　以此类推，从最后一个父节点到根结点进行堆调整的总共操作次数为O(n)，建堆时间复杂度为O(n)。

　　空间复杂度为O(1)。

　　堆排序入口：

 1     /**
 2      * 堆排序的主要入口方法，共两步。
 3      */
 4     public void sort() {
 5         /*
 6          *  第一步：将数组堆化
 7          *  beginIndex = 第一个非叶子节点。
 8          *  从第一个非叶子节点开始即可。无需从最后一个叶子节点开始。
 9          *  叶子节点可以看作已符合堆要求的节点，根节点就是它自己且自己以下值为最大。
10          */
11         int len = arr.length - 1;
12         int beginIndex = (arr.length >> 1) - 1;
13         for(int i = beginIndex; i>=0; i--) {
14             maxHeapify(i, len);
15         }
16         /*
17          * 第二步：对堆化数据排序
18          * 每次都是移出最顶层的根节点A[0]，与最尾部节点位置调换，同时遍历长度 - 1。
19          * 然后从新整理被换到根节点的末尾元素（比较小），使其符合堆的特性。
20          * 直至未排序的堆长度为 0。
21          */
22         for(int i = len; i > 0; i--) {
23             swap(0, i);
24             maxHeapify(0, i-1);
25         }
26     }

　　测试代码：

1     public static void main(String[] args) {
2         int[] arr = new int[] {3, 5, 3, 0, 8, 6, 1, 5, 8, 6, 2, 4, 9, 4, 7, 0, 1, 8, 9, 7, 3, 1, 2, 5, 9, 7, 4, 0, 2, 6};
3         new HeapSort(arr).sort();
4         System.out.println(Arrays.toString(arr));
5     }