从排序开始（五） 堆排序
堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。通常所说的堆是一个近似完全二叉树的结构，并同时满足堆的性质：即最大堆子结点的关键字总是小于（如果是最小堆那就是大于）它的父节点。
通常堆是通过一维数组来实现的。在起始数组为 0 的情形中：
父节点 i 的左子节点在位置 (2*i+1);
父节点 i 的右子节点在位置 (2*i+2);
子节点 i 的父节点在位置 (i-1) / 2;
堆排序：
1、用大根堆排序的基本思想
（1）、 先将初始序列 R[0..n-1] 建成一个大根堆，此堆为初始的无序区
（2）、此时R[0]为序列中最大的数，将关键字最大的记录R[0]（即堆顶）和无序区的最后一个记录R[n-1]交换，由此得到新的无序区R[0..n-2]和有序区R[n-1]
（3）、由于交换后新的根 R[1] 可能违反堆性质，故应将当前无序区R[0..n-2]调整为堆。然后再次将R[0..n-2]中关键字最大的记录R[0]和该区间的最后一个记录R[n-2]交换，由此得到新的无序区R[0..n-3]和有序区R[n-2..n-1]，同样要将R[0..n-3]调整为堆。……直到无序区只有一个元素为止。
2、大根堆排序算法的基本操作：
（1）、 初始化操作：将R[0..n-1]构造为初始堆；
（2）、 每一趟排序的基本操作：将当前无序区的堆顶记录R[1]和该区间的最后一个记录交换，然后将新的无序区调整为堆（亦称重建堆）。
注意：
（1）、只需做n-1趟排序，选出较大的n-1个关键字即可以使得文件递增有序。
（2）、用小根堆排序与利用大根堆类似，只不过其排序结果是递减有序的。堆排序和直接选择排序相反：在任何时刻堆排序中无序区总是在有序区之前，且有序区是在原向量的尾部由后往前逐步扩大至整个向量为止
最差时间复杂度： O(n logn)
最优时间复杂度： O(n logn)
平均时间复杂度： O(n logn)
最差空间复杂度： O(1)
稳定性：不稳定
实现：
#include <iostream>using namespace std;//从i节点开始维护堆，n为节点总数，从0开始计算，i节点的孩子节点为 2*i+1, 2*i+2void maxHeapAdjust(int num[], int i, int n){ int j, tmp;tmp = num[i];j = 2 * i + 1;while (j < n){//在左右孩子中找最大的if (j + 1 < n && num[j + 1] > num[j])j++;if (num[j] <= tmp)break;//把较小的子结点往上移动,替换它的父结点num[i] = num[j];i = j;j = 2 * i + 1;}num[i] = tmp;}//建立最大堆，叶子视为建好的最大堆 void makeMaxHeap(int num[], int n){for (int i = n / 2 - 1; i >= 0; i--)maxHeapAdjust(num, i, n);}//对 n 个数进行堆排序，升序void maxHeapSort(int num[], int n){for (int i = n - 1; i >= 1; i--){//交换，把最大的元素放后面 int t = num[i];num[i] = num[0];num[0] = t;//交换后要重新调整成最大堆maxHeapAdjust(num, 0, i);}}int main() { int n; while(cin>>n,n) { int *p = new int[n]; for( int i = 0;i<n;++i) p[i] = rand()%2000; makeMaxHeap(p,n); maxHeapSort(p,n); for(int i=0;i<n;++i)cout<<p[i]<<' '; cout<<endl; delete []p; } return 0; }