偶看新闻防火安全口号:算法四：堆排序（O(nlogn)）
来源：百度文库 编辑：偶看新闻 时间：2024/04/29 23:52:27
1. 堆排序
堆的介绍: N个元素的序列K1,K2,K3,...,Kn.称为堆，当且仅当该序列满足特性：
是一个完全树，也就是说，除了最底层之外，树的美一层都是满的，且最底层中的节点处于左边
它满足堆次序属性：每个节点中的数据项都大>= (或者<=)左右子女的数据项。
堆实质上是满足如下性质的完全二叉树：树中任一非叶子结点的关键字均大于等于其孩子结点的关键字。例如序列10,15,56,25,30,70就是一个堆，它对应的完全二叉树如上图所示。这种堆中根结点（称为堆顶）的关键字最小，我们把它称为小根堆。反之，若完全二叉树中任一非叶子结点的关键字均大于等于其孩子的关键字，则称之为大根堆。
思想（大根堆）：
① 先将初始文件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]调整为堆。直到无序区只有一个元素为止。
适用范围：由于建初始堆所需的比较次数较多，所以堆排序不适宜于记录数较少的文件。
算法：
（1）用大根堆排序的基本思想
（2）大根堆排序算法的基本操作：
① 初始化操作：将R[1..n]构造为初始堆；
② 每一趟排序的基本操作：将当前无序区的堆顶记录R[1]和该区间的最后一个记录交换，然后将新的无序区调整为堆(亦称重建堆)。
注意：
①只需做n-1趟排序，选出较大的n-1个关键字即可以使得文件递增有序。
②用小根堆排序与利用大根堆类似，只不过其排序结果是递减有序的。堆排序和直接选择排序相反：在任何时刻堆排序中无序区总是在有序区之前，且有序区是在原向量的尾部由后往前逐步扩大至整个向量为止
示例：对关键字序列42，13，91，23，24，16，05，88建堆
复杂度：堆排序的时间，主要由建立初始堆和反复重建堆这两部分的时间开销构成。
平均：
最坏：O(nlogn)
稳定性：不稳定
步骤：
1 用temp把root的值保存
2 取大的子女节点，用a[child]表示。
3 如果根比叶子节点小，就把较大的子女节点节点放到根的位置。
4 判断叶子节点是否为叶子节点，不是就令root=child，然后跳到2，是就跳出循环
程序：
template
void AdjustDown(T A[],int r,int j) //构建堆得向下调整算法
{
int child=2*r+1; //2*x+1=x的左下子树
T temp=A[r];
while(child<=j)
{
if(child
{
child++;
}
if(temp>A[child])
{
break;
}
A[(child-1)/2]=A[child]; //(x-1)/2=x的父节点
child=2*child+1;
}
A[(child-1)/2]=temp;
}
template
void HeapSort(T A[],int n)
{
T temp;
for(int i=(n-2)/2;i>-1;--i) //构建最大堆，(n-2)/2为第一个有子节点的节点
{
AdjustDown(A,i,n-1);
}
for(int j=n-1;j>0;--j)
{
temp=A[0];
A[0]=A[j];
A[j]=temp; //堆顶与堆底元素交换
AdjustDown(A,0,j-1); //调整A[0]再构建最大堆
}
}