堆排序
它是不稳定的排序方法。（排序的稳定性是指如果在排序的序列中，存在前后相同的两个元素的话，排序前 和排序后他们的相对位置不发生变化）
前提理解：
大根堆和小根堆：都是完全二叉树，根结点（亦称为堆顶）的关键字是堆里所有结点关键字中最小者的堆称为小根堆，又称最小堆。 根结点（亦称为堆顶）的关键字是堆里所有结点关键字中最大者，称为大根堆，又称最大堆。 大根堆的要求是每个节点的值都不大于其父节点的值，即A[PARENT[i]] >= A[i] 注意：①堆中任一子树亦是堆。②以上讨论的堆实际上是二叉堆（Binary Heap），类似地可定义k叉堆。完全二叉树：一棵二叉树至多只有最下面的一层上的结点的度数可以小于2，并且最下层上的结点都集中在该层最左边的若干位置上
满二叉树：除最后一层无任何子节点外，每一层上的所有结点都有两个子结点二叉树。
用大根堆排序的基本思想 ① 先将初始文件R[1..n]建成一个大根堆，此堆为初始的无序区 ② 再将关键字最大的记录R[1]（即堆顶）和无序区的最后一个记录R[n]交换，由此得到新的无序区R[1..n-1]和有序区R[n]，且满足R[1..n-1].keys≤R[n].key ③由于交换后新的根R[1]可能违反堆性质，故应将当前无序区R[1..n-1]调整为堆。然后再次将R[1..n-1]中关键字最大的记录R[1]和该区间的最后一个记录R[n-1]交换，由此得到新的无序区R[1..n-2]和有序区R[n-1..n]，且仍满足关系R[1..n-2].keys≤R[n-1..n].keys，同样要将R[1..n-2]调整为堆。 …… 直到无序区只有一个元素为止。
下面举例说明：
给定一个整形数组a[]={16,7,3,20,17,8}，对其进行堆排序。
首先根据该数组元素构建一个完全二叉树，得到
1）建堆
2）交换以及调整为堆
3）重复步骤
代码：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 //堆排序 //整理节点time:O(lgn) template <typenameT> void MinHeapify(T*arry, int size, int element) { int lchild=element*2+1,rchild=lchild+1; //左右子树 while (rchild<size) //子树均在范围内 { if (arry[element]<=arry[lchild]&&arry[element]<=arry[rchild]) //如果比左右子树都小，完成整理 { return ; } if (arry[lchild]<=arry[rchild]) //如果左边最小 { swap(arry[element],arry[lchild]); //把左面的提到上面 element=lchild; //循环时整理子树 } else //否则右面最小 { swap(arry[element],arry[rchild]); //同理 element=rchild; } lchild=element*2+1; rchild=lchild+1; //重新计算子树位置 } if (lchild<size&&arry[lchild]<arry[element]) //只有左子树且子树小于自己 { swap(arry[lchild],arry[element]); } return ; } //堆排序time:O(nlgn) template <typenameT> void HeapSort(T*arry, int size) { int i; for (i=size-1;i>=0;i--) //从子树开始整理树 { MinHeapify(arry,size,i); } while (size>0) //拆除树 { swap(arry[size-1],arry[0]); //将根（最小）与数组最末交换 size--; //树大小减小 MinHeapify(arry,size,0); //整理树 } return ; } void BuildMaxHeap(ElemType A[];int len)//建堆 { for(int i=len/2;i>0;i--) AdjustDown(A,i,len); } void AdjustDown(ElemType A[],int k,int len)//向下调整的算法 { A[0]=A[k]; for(i=2*k;i<=len;i*=2) { if(i<len&&A[i]<A[i+1]) i++; //挑选出key较大的子结点的下标 if(A[0]>=A[i])break;//筛选结束 else { A[k]=A[i]; k=i; } } A[k]=A[0]; } 向下调整的时间与树高有关，在元素个数为n的序列建堆，时间复杂度为O(n)
堆排序算法
void HeapSort(ElemType A[],int len) { BuildMaxHeap(A,len); for(i=len;i>1;i--) { Swap(A[i],A[1]); AdjustDown(A,1,i-1); } } void AdjustUp(ElemType A[],int k) { A[0]=A[k]; int i=k/2; while(i>0&&A[i]<A[0]) { A[k]=A[i]; k=i; i=k/2; } A[k]=A[0]; } 堆排序的时间，主要由建立初始堆和反复重建堆这两部分的时间开销构成堆排序的运行时间是O(nlog2n)2为底
空间效率：仅使用常数个辅助单元，空间复杂度为O(1)
稳定性：不稳定
（本文整合网上资料，方便学习）
