堆排序介绍
堆排序是指利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。
学习堆排序之前，有必要了解堆！若读者不熟悉堆，建议先了解堆（建议可以通过二叉堆、左倾堆、斜堆、二项堆或斐波那契堆等文章进行了解），然后再来学习本章。
我们知道，堆分为”最大堆”和”最小堆”。最大堆通常被用来进行”升序”排序，而最小堆通常被用来进行”降序”排序。鉴于最大堆和最小堆是对称关系，理解其中一种即可，本文将对最大堆实现的升序排序进行详细说明。
最大堆进行升序排序的基本思想：
- 初始化堆：将数列 a[1…n] 构造成最大堆；
- 交换数据：将 a[1] 和 a[n] 交换，使 a[n] 是 a[1…n] 中的最大值；然后将 a[1…n-1] 重新调整为最大堆。接着，将 a[1] 和 a[n-1] 交换，使 a[n-1] 是 a[1…n-1] 中的最大值；然后将 a[1…n-2] 重新调整为最大堆。依次类推，直到整个数列都是有序的。
下面通过图文来解析堆排序的实现过程（原文图片丢失，据文字与代码重绘）。注意实现中用到了”数组实现的二叉堆的性质”。在第一个元素的索引为 0 的情形中：
- 性质一：索引为 i 的左孩子的索引是 (2*i+1)；
- 性质二：索引为 i 的右孩子的索引是 (2*i+2)；
- 性质三：索引为 i 的父结点的索引是 floor((i-1)/2)。
例如，对于最大堆 {110,100,90,40,80,20,60,10,30,50,70} 而言：索引为 0 的左孩子是 1；索引为 0 的右孩子是 2；索引为 8 的父节点是 3。
堆排序实现
下面演示 heapSortAsc(a, n) 对 a={20,30,90,40,70,110,60,10,100,50,80}、n=11 进行堆排序的过程。
初始化堆
在堆排序算法中，首先要将待排序的数组转化成二叉堆。下面演示将数组 {20,30,90,40,70,110,60,10,100,50,80} 转换为最大堆 {110,100,90,40,80,20,60,10,30,50,70} 的步骤（i 从 n/2-1 = 4 递减到 0，每次对以 a[i] 为根的子树执行 maxHeapDown 向下调整）：
- 1.1 i=4：maxHeapDown(a, 4, 10) 的作用是将 a[4…10] 进行下调；a[4] 的左孩子是 a[9]，右孩子是 a[10]。调整时，选择左右孩子中较大的一个（即 a[10]）和 a[4] 交换。
- 1.2 i=3：maxHeapDown(a, 3, 10) 的作用是将 a[3…10] 进行下调；a[3] 的左孩子是 a[7]，右孩子是 a[8]。调整时，选择左右孩子中较大的一个（即 a[8]）和 a[3] 交换。
- 1.3 i=2：maxHeapDown(a, 2, 10) 的作用是将 a[2…10] 进行下调；a[2] 的左孩子是 a[5]，右孩子是 a[6]。调整时，选择左右孩子中较大的一个（即 a[5]）和 a[2] 交换。
- 1.4 i=1：maxHeapDown(a, 1, 10) 的作用是将 a[1…10] 进行下调；a[1] 的左孩子是 a[3]，右孩子是 a[4]。调整时，选择左右孩子中较大的一个（即 a[3]）和 a[1] 交换。交换之后，a[3] 为 30，它比它的右孩子 a[8] 要小，接着，再将它们交换。
- 1.5 i=0：maxHeapDown(a, 0, 10) 的作用是将 a[0…10] 进行下调；a[0] 的左孩子是 a[1]，右孩子是 a[2]。调整时，选择左右孩子中较大的一个（即 a[2]）和 a[0] 交换。交换之后，a[2] 为 20，它比它的左右孩子要小，选择较大的孩子（即左孩子 a[5]）和 a[2] 交换。
调整完毕，就得到了最大堆。此时，数组 {20,30,90,40,70,110,60,10,100,50,80} 也就变成了 {110,100,90,40,80,20,60,10,30,50,70}：
flowchart TD
n0((110)) --> n1((100))
n0 --> n2((90))
n1 --> n3((40))
n1 --> n4((80))
n2 --> n5((20))
n2 --> n6((60))
n3 --> n7((10))
n3 --> n8((30))
n4 --> n9((50))
n4 --> n10((70))交换数据
在将数组转换成最大堆之后，接着要进行交换数据，从而使数组成为一个真正的有序数组。交换数据部分相对比较简单，下面给出将最大值放到数组末尾的过程示意。
当 n=10 时，首先交换 a[0] 和 a[10]，使得 a[10] 是 a[0…10] 之间的最大值；然后，调整 a[0…9] 使它成为最大堆。交换之后：a[10] 是有序的！
当 n=9 时，首先交换 a[0] 和 a[9]，使得 a[9] 是 a[0…9] 之间的最大值；然后，调整 a[0…8] 使它成为最大堆。交换之后：a[9…10] 是有序的！
依此类推，直到 a[0…10] 是有序的：
flowchart TD
c0["最大堆顶 110 与 a[10] 交换, 再调整 a[0..9] | 有序区: 110"]
c1["堆顶 100 与 a[9] 交换, 再调整 a[0..8] | 有序区: 100 110"]
c2["堆顶与 a[8] 交换, 再调整 a[0..7] | 有序区继续扩大"]
c3["重复直到堆中只剩 a[0] | 整个数组有序"]
c0 --> c1 --> c2 --> c3
style c3 fill:#c8e6c9堆排序复杂度和稳定性
堆排序时间复杂度
堆排序的时间复杂度是 O(N·logN)。
假设被排序的数列中有 N 个数。遍历一趟的时间复杂度是 O(N)，需要遍历多少次呢？堆排序是采用二叉堆进行排序的，二叉堆就是一棵二叉树，它需要遍历的次数就是二叉树的深度，而根据完全二叉树的定义，它的深度至少是 log(N+1)，最多是多少呢？由于二叉堆是完全二叉树，因此它的深度最多也不会超过 log(2N)。因此，遍历一趟的时间复杂度是 O(N)，而遍历次数介于 log(N+1) 和 log(2N) 之间；因此得出它的时间复杂度是 O(N·logN)。
堆排序稳定性
堆排序是不稳定的算法，它不满足稳定算法的定义。它在交换数据的时候，是比较父结点和子节点之间的数据，所以，即便是存在两个数值相等的兄弟节点，它们的相对顺序在排序中也可能发生变化。
算法稳定性——假设在数列中存在 a[i]=a[j]，若在排序之前，a[i] 在 a[j] 前面；并且排序之后，a[i] 仍然在 a[j] 前面。则这个排序算法是稳定的！
| 指标 | 值 |
|---|---|
| 平均时间复杂度 | O(N·logN) |
| 最坏时间复杂度 | O(N·logN) |
| 最好时间复杂度 | O(N·logN) |
| 空间复杂度 | O(1) |
| 稳定性 | 不稳定 |
代码实现
/**
* 堆排序: Java
*
* @author skywang
* @date 2014/03/11
*/
public class HeapSort {
/*
* (最大)堆的向下调整算法
*
* 注: 数组实现的堆中，第N个节点的左孩子的索引值是(2N+1)，右孩子的索引是(2N+2)。
* 其中，N为数组下标索引值，如数组中第1个数对应的N为0。
*
* 参数说明:
* a -- 待排序的数组
* start -- 被下调节点的起始位置(一般为0，表示从第1个开始)
* end -- 截至范围(一般为数组中最后一个元素的索引)
*/
public static void maxHeapDown(int[] a, int start, int end) {
int c = start; // 当前(current)节点的位置
int l = 2*c + 1; // 左(left)孩子的位置
int tmp = a[c]; // 当前(current)节点的大小
for (; l <= end; c=l,l=2*l+1) {
// "l"是左孩子，"l+1"是右孩子
if ( l < end && a[l] < a[l+1])
l++; // 左右两孩子中选择较大者，即a[l+1]
if (tmp >= a[l])
break; // 调整结束
else { // 交换值
a[c] = a[l];
a[l]= tmp;
}
}
}
/*
* 堆排序(从小到大)
*
* 参数说明:
* a -- 待排序的数组
* n -- 数组的长度
*/
public static void heapSortAsc(int[] a, int n) {
int i,tmp;
// 从(n/2-1) --> 0逐次遍历。遍历之后，得到的数组实际上是一个(最大)二叉堆。
for (i = n / 2 - 1; i >= 0; i--)
maxHeapDown(a, i, n-1);
// 从最后一个元素开始对序列进行调整，不断的缩小调整的范围直到第一个元素
for (i = n - 1; i > 0; i--) {
// 交换a[0]和a[i]。交换后，a[i]是a[0...i]中最大的。
tmp = a[0];
a[0] = a[i];
a[i] = tmp;
// 调整a[0...i-1]，使得a[0...i-1]仍然是一个最大堆。
// 即，保证a[i-1]是a[0...i-1]中的最大值。
maxHeapDown(a, 0, i-1);
}
}
/*
* (最小)堆的向下调整算法
*
* 注: 数组实现的堆中，第N个节点的左孩子的索引值是(2N+1)，右孩子的索引是(2N+2)。
* 其中，N为数组下标索引值，如数组中第1个数对应的N为0。
*
* 参数说明:
* a -- 待排序的数组
* start -- 被下调节点的起始位置(一般为0，表示从第1个开始)
* end -- 截至范围(一般为数组中最后一个元素的索引)
*/
public static void minHeapDown(int[] a, int start, int end) {
int c = start; // 当前(current)节点的位置
int l = 2*c + 1; // 左(left)孩子的位置
int tmp = a[c]; // 当前(current)节点的大小
for (; l <= end; c=l,l=2*l+1) {
// "l"是左孩子，"l+1"是右孩子
if ( l < end && a[l] > a[l+1])
l++; // 左右两孩子中选择较小者
if (tmp <= a[l])
break; // 调整结束
else { // 交换值
a[c] = a[l];
a[l]= tmp;
}
}
}
/*
* 堆排序(从大到小)
*
* 参数说明:
* a -- 待排序的数组
* n -- 数组的长度
*/
public static void heapSortDesc(int[] a, int n) {
int i,tmp;
// 从(n/2-1) --> 0逐次遍历。遍历之后，得到的数组实际上是一个最小堆。
for (i = n / 2 - 1; i >= 0; i--)
minHeapDown(a, i, n-1);
// 从最后一个元素开始对序列进行调整，不断的缩小调整的范围直到第一个元素
for (i = n - 1; i > 0; i--) {
// 交换a[0]和a[i]。交换后，a[i]是a[0...i]中最小的。
tmp = a[0];
a[0] = a[i];
a[i] = tmp;
// 调整a[0...i-1]，使得a[0...i-1]仍然是一个最小堆。
// 即，保证a[i-1]是a[0...i-1]中的最小值。
minHeapDown(a, 0, i-1);
}
}
public static void main(String[] args) {
int i;
int a[] = {20,30,90,40,70,110,60,10,100,50,80};
System.out.printf("before sort:");
for (i=0; i<a.length; i++)
System.out.printf("%d ", a[i]);
System.out.printf("\n");
heapSortAsc(a, a.length); // 升序排列
//heapSortDesc(a, a.length); // 降序排列
System.out.printf("after sort:");
for (i=0; i<a.length; i++)
System.out.printf("%d ", a[i]);
System.out.printf("\n");
}
}参考文章
本文主要参考至 https://www.cnblogs.com/skywang12345/p/3602162.html ，在此基础上做了内容的增改。