各类排序方法在时间、空间复杂度及稳定性（通俗地讲，就是两个相等的数不会交换位置）方面各有优势：
堆排序（Heap sort）是指利用堆这种数据结构所设计的一种选择排序算法。堆是一种近似完全二叉树的结构，并满足性质：以最大堆（也叫大根堆、大顶堆）为例，其中父结点的值总是大于它的孩子节点。
堆排序可以把数组看作堆，第i个结点的孩子结点为第2*i+1和2*i+2个结点（不超出数组长度前提下）。
我们可以很容易的定义堆排序的过程：
I 由输入的无序数组构造一个最大堆，作为初始的无序区；
II 把堆顶元素（最大值）和堆尾元素（不一定是最小元素）互换；
III 把堆（无序区）的尺寸缩小1，并从新的堆顶元素开始进行堆调整（调用heapify(A, 0)函数）；
IV 重复步骤2，直到堆的尺寸为1。
1 算法描述
堆排序的主要时间花在初始建堆期间，建好堆后，堆这种数据结构以及它奇妙的特征，使得找到数列中最大的数字这样的操作只需要O(1)的时间复杂度，维护需要logn的时间复杂度。堆排序不适宜于记录数较少的数据结构。
- 将初始待排序关键字序列(R1,R2….Rn)构建成大顶堆，此堆为初始的无序区；
- 将堆顶元素R[1]与最后一个元素R[n]交换，此时得到新的无序区(R1,R2,……Rn-1)和新的有序区(Rn),且满足R[1,2…n-1]<=R[n]；
- 由于交换后新的堆顶R[1]可能违反堆的性质，因此需要对当前无序区(R1,R2,……Rn-1)调整为新堆；
- 再次将R[1]与无序区最后一个元素交换，得到新的无序区(R1,R2….Rn-2)和新的有序区(Rn-1,Rn)。不断重复此过程直到有序区的元素个数为n-1，则整个排序过程完成。
在堆的数据结构中，堆中的最大值总是位于根节点（在优先队列中使用堆的话堆中的最小值位于根节点）。堆中定义以下几种操作：
- 最大堆调整（Max Heapify）：将堆的末端子节点作调整，使得子节点永远小于父节点；
- 创建最大堆（Build Max Heap）：将堆中的所有数据重新排序；
- 堆排序（HeapSort）：移除位在第一个数据的根节点，并做最大堆调整的递归运算；
2 理解堆这种数据结构
堆排序，就是以堆的形式去排序，毫无疑问，了解堆很重要。
那么，什么是堆呢？
这里，必须引入一个完全二叉树的概念，然后过渡到堆的概念。
上图，就是一个完全二叉树，其特点在于：
I 从作为第一层的根开始，除了最后一层之外，第N层的元素个数都必须是2的N次方；第一层一个元素，第二层4个，第三层8个，以此类推。
II 而最后一行的元素，都要紧贴在左边，换句话说，每一行的元素都从最左边开始安放，两个元素之间不能有空闲，具备了这两个特点的树，就是一棵完全二叉树。
那么，完全二叉树与堆有什么关系呢？
我们假设有一棵完全二叉树，在满足作为完全二叉树的基础上，对于任意一个拥有父节点的子节点，其数值均不小于父节点的值；这样层层递推，就是根节点的值最小，这样的树，称为小根堆。
同理，又有一棵完全二叉树，对于任意一个子节点来说，均不大于其父节点的值，如此递推，就是根节点的值是最大的，这样的数，称为大根堆。
如上图，左边就是大根堆；右边则是小根堆，这里必须要注意一点，只要求子节点与父节点的关系，两个节点的大小关系与其左右位置没有任何关系。
2 逐步理解堆排序
现在对于堆排序来说，我们先要做的是，把待排序的一堆无序的数，整理成一个大根堆，或者小根堆，下面讨论以大根堆为例子。
给定一个列表array=[16,7,3,20,17,8]，对其进行堆排序（使用大根堆）。
2.1 构造初始堆。
将给定无序序列构造成一个大顶堆（一般升序采用大顶堆，降序采用小顶堆)。
a.假设给定无序序列结构如下
2.2 堆调整
此时我们从最后一个非叶子结点开始（叶结点自然不用调整，第一个非叶子结点 arr.length/2-1=5/2-1=1，也就是下面的6结点），从左至右，从下至上进行调整。
此处必须注意，我们把6和9比较交换之后，必须考量9这个节点对于其子节点会不会产生任何影响？因为其是叶子节点，所以不加考虑；但是，一定要熟练这种思维，写代码的时候就比较容易理解为什么会出现一次非常重要的交换了。
找到第二个非叶节点4，由于[4,9,8]中9元素最大，4和9交换。
在真正代码的实现中，这时候4和9交换过后，必须考虑9所在的这个节点位置，因为其上的值变了，必须判断对其的两个子节点是否造成了影响，这么说不合适，实际上就是判断其作为根节点的那棵子树，是否还满足大根堆的原则，每一次交换，都必须要循环把子树部分判别清楚。
这时，交换导致了子根[4,5,6]结构混乱，继续调整，[4,5,6]中6最大，交换4和6。
牢记上面说的规则，每次交换都要把改变了的那个节点所在的树重新判定一下，这里就用上了，4和9交换了，变动了的那棵子树就必须重新调整，一直调整到符合大根堆的规则为截。
此时，我们就将一个无序序列构造成了一个大顶堆。
2.3 堆顶元素与末尾元素进行交换，并调整堆
将堆顶元素与末尾元素进行交换，使末尾元素最大。然后继续调整堆，再将堆顶元素与末尾元素交换，得到第二大元素。如此反复进行交换、重建、交换。
a.将堆顶元素9和末尾元素4进行交换
这里，必须说明一下，所谓的交换，实际上就是把最大值从树里面拿掉了，剩下参与到排序的树，其实只有总结点的个数减去拿掉的节点个数了。所以图中用的是虚线。
b.重新调整结构，使其继续满足堆定义
c.再将堆顶元素8与末尾元素5进行交换，得到第二大元素8.
后续过程，继续进行调整，交换，如此反复进行，最终使得整个序列有序
3 动图演示
3.1 新建堆
3.2 排序
4 动图↓
动图↓
C代码：
附代码：
#include <stdio.h>
#include <stdlib.h>
// 分类 -------------- 内部比较排序
// 数据结构 ---------- 数组
// 最差时间复杂度 ---- O(nlogn)
// 最优时间复杂度 ---- O(nlogn)
// 平均时间复杂度 ---- O(nlogn)
// 所需辅助空间 ------ O(1)
// 稳定性 ------------ 不稳定
void Swap(int A[], int i, int j)
{
int temp = A[i];
A[i] = A[j];
A[j] = temp;
}
void Heapify(int A[], int i, int size) // 从A[i]向下进行堆调整
{
int left_child = 2 * i + 1; // 左孩子索引
int right_child = 2 * i + 2; // 右孩子索引
int max = i; // 选出当前结点与其左右孩子三者之中的最大值
if (left_child < size && A[left_child] > A[max])
max = left_child;
if (right_child < size && A[right_child] > A[max])
max = right_child;
if (max != i)
{
Swap(A, i, max); // 把当前结点和它的最大(直接)子节点进行交换
Heapify(A, max, size);
// 递归调用，继续从当前结点向下进行堆调整
}
}
int BuildHeap(int A[], int n) // 建堆，时间复杂度O(n)
{
int heap_size = n;
for (int i = heap_size / 2 - 1; i >= 0; i--) // 从每一个非叶结点开始向下进行堆调整
Heapify(A, i, heap_size);
return heap_size;
}
void HeapSort(int A[], int n)
{
int heap_size = BuildHeap(A, n); // 建立一个最大堆
while (heap_size > 1)
// 堆（无序区）元素个数大于1，未完成排序
{
// 将堆顶元素与堆的最后一个元素互换，并从堆中去掉最后一个元素
//此处交换操作很有可能把后面元素的稳定性打乱，
//所以堆排序是不稳定的排序算法
Swap(A, 0, --heap_size);
Heapify(A, 0, heap_size); // 从新的堆顶元素开始向下进行堆调整，时间复杂度O(logn)
}
}
int main()
{
int A[] = { 5, 2, 9, 4, 7, 6, 1, 3, 8 };// 从小到大堆排序
int n = sizeof(A) / sizeof(int);
HeapSort(A, n);
printf("堆排序结果：");
for (int i = 0; i < n; i++)
{
printf("%d ", A[i]);
}
printf("\n");
system("pause");
return 0;
}
－End－