堆排序
堆排序是简单选择排序的改进，改进点为如何让减少在选择的过程中比较的次数。
1.堆的定义
堆是具有以下性质的完全二叉树：每个结点的值都大于（小于）等于其孩子节点的值，称为大根堆（小根堆）。
例：
由堆的定义得知堆顶元素一定为最大（大根堆）或者最小值（小根堆）。
2.调整算法。
首先将根节点与左右孩子节点相比较，如果符合根节点最大（大根堆的定义）不调整，如果孩子比根节点大，选择孩子节点中最大的与根节点交换。经过交换，破坏了被交换子树的堆结构，须再对被交换子树进行堆排序直到i为叶子节点。注意：堆的调整算法不是一次调整就将无序的数据调成堆。是在根节点的左右子树均是堆时，进行一次调整才时堆。
| 算法：Sift(int k,int last,int a[])//构建大根堆的调整算法 |
| 输入：待调整数组a[k]~a[last],且a[k+1]~a[last]满足堆的条件 |
| 输出：无
令i=j,j=j=2i+1（该操作是向下一层调整）,循环步骤2 |
例：第一次调整破坏左子树，需要向下继续调整。如果·第一次比较符合堆定义则结束。注该函数为堆的调整函数，不是直接初始化堆（堆的初始化可能需要多次堆的调整）。
3.堆排序
是基于对的特性进行排序。
3.1基本思想
3.1.1将待排序列调整为堆,此时根节点为最大元素从最下层出度不为0的最后一个节点开始调整sift（i=ceil(length/2)-1,last）循环i--（i是完全二叉树最下层出度不为0的最后一个节点）。
3.1.2将堆顶元素（将树的最后一个节点与根节点交换（排序过的节点不在树中），此时根节点的左右子树仍是 大根堆）移走将剩余记录再调成堆。重复该操作。
3.2堆排序实现
代码在Dev-C++5.11编程环境下调试。
#include<iostream>
using namespace std;
void Shit(int k,int last,int a[])//如果是降序排列只需要建立小根堆
{
int i,j,temp;
i=k,j=2*i+1;
while(j<=last)
{
if(j<last&&a[j]<a[j+1])j++;
if(a[i]>a[j]) break;//已经是堆
else{
temp=a[i];
a[i]=a[j];
a[j]=temp;
i=j;j=2*i+1;
}
}
}
void HeapSort(int a[],int length)
{
int i,temp;
for(int i=length/2-1;i>=0;i--)//初始化大根堆 从完全二叉树最后一层最后一个出度不为0的·分支节点开始调整，直至到根结点
{
Shit(i,length-1,a);
}
for(i=1;i<length;i++)//依次选取最大的元素到
{
temp=a[0];
a[0]=a[length-i];
a[length-i]=temp;//堆顶和堆中最后一个元素位置交换
Shit(0,length-1-i,a);//交换后堆的调整
}
}
int main()
{
int a[]={4,5,989,7,9756,464,77,645,46,54,89,7645};
HeapSort(a,12);
for(int q=0;q<12;q++)
{
cout<<a[q]<<"\t";
}
}