堆排序算法
对堆排序算法的理解
1991年计算机先驱奖获得者、斯坦福大学计算机科学系教授罗伯特?弗洛伊德(Robert W(Floyd)和威廉姆斯(J(Williams)在1964年共同发明了著名的堆排序算法( Heap Sort ) 。
一、堆排序的概念
堆排序利用了大根堆(或小根堆)堆顶记录的关键字最大(或最小)这一特征～使得在当前无序区中选取最大(或最小)关键字的记录变得简单。
1、用大根堆排序的基本思想
? 先将初始文件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]调整为堆。直到无序区只有一个元素为止。 2、大根堆排序算法的基本操作:
? 初始化操作:将R[1..n]构造为初始堆,
? 每一趟排序的基本操作:将当前无序区的堆顶记录R[1]和该区间的最后一个记录交换～然后将新的无序区调整为堆(亦称重建堆)。
注意:
?只需做n-1趟排序～选出较大的n-1个关键字即可以使得文件递增有序。
?用小根堆排序与利用大根堆类似～只不过其排序结果是递减有序的。堆排序和直接选择排序相反:在任何时刻堆排序中无序区总是在有序区之前～且有序区是在原向量的尾部由后往前逐步扩大至整个向量为止 。
二、堆排序的特点及与直接选择排序的区别
1、堆排序(HeapSort)是一树形选择排序。堆排序的特点是:在排序过程中～将R[l..n]看成是一棵完全二叉树的顺序存储结构～利用完全二叉树中双亲结点和孩子结点之间的内在关系(参见二叉树的顺序存储结构)～在当前无序区中选择关键字最大(或最小)的记录。 2、堆排序与直接选择排序的区别
直接选择排序中～为了从R[1..n]中选出关键字最小的记录～必须进行n-1次比较～然后在R[2..n]中选出关键字最小的记录～又需要做n-2次比较。事实上～后面的n-2次比较中～有许多比较可能在前面的n-1次比较中已经做过～但由于前一趟排序时未保留这些比较结果～所以后一趟排序时又重复执行了这些比较操作。堆排序可通过树形结构保存部分比较结果～可减少比较次数。
堆排序在最坏的情况下～其时间复杂度也能达到O,nlogn,。相对于快速排序来说～这是它最大的优点～此外～堆排序仅需要一个记录大小供交换用的辅助存储空间。
堆排序的数据结构是二叉堆～二叉堆的特点有两个～一个是它是一棵完全二叉树～另一个是它的根结点小于孩子结点～所以我们很容易找到它的最小结点----根结点,当然～如果你想找到最大结点的话～那就要扫描所有的叶子结点～这是很费时间的～如果你想找的是最大结点的话～你最好把它弄成一个大顶堆～即一棵根结点大于孩子结点的完全二叉树。
二叉堆通常用数组来实现～它舍弃下标0～从下标1开始置数～则很容易满足～对于数组中任意位置i上的元素～其左儿子的位置在2i上～右儿子的位置在2i+1上～双亲的位置则在i/2上。
堆排序的算法之一是把数组构建成二叉堆----这只要增添一个长度为n+1的辅助空间～然后把原数组的元素依次插入到二叉堆即可。然后删除二叉堆的根～把它作为排序后的数组的第一个元素,然后使二叉堆的长度减1～并通过上移使得新得到的序列仍为二叉堆～ 再提取新二叉堆的第一个元素到新数组。依此类推～直到提取最后一个元素～新得到的数组就是排序后的数组。
template
void Insert(T a[], int len, T x)//把x插入到原长度为len的二叉堆～注意保证新二叉堆不越界
{
int i;
for (i=len; i/2>0 && a[i/2]>x; i/=2)
a[i] = a[i/2];
a[i] = x;
}
template
T DeleteMin(T a[], int len)//删除二叉堆的根～并通过上移使得新得到的序列仍为二叉堆
{
if (len == 0)
exit(1);
T min = a[1];//二叉堆的根
T last = a[len--];//二叉堆的最后一个元素
int c;
int i;
for (i=1; i*2<=len; i=c)//把二叉堆的某些元素往前移～使得新得到的序列仍为二叉堆
{
c = i * 2;//i的左儿子
if (c != len && a[c+1] < a[c])//若i有右儿子～且右儿子小于左儿子～c指向右儿子
c++;
if (last > a[c])//若i的小儿子小于二叉堆的最后一个元素～把其移到i的位置
a[i] = a[c];
else
break;
}
a[i] = last; //把二叉堆的最后一个元素放到适当的空位～此时得到的序列仍为二叉堆
return min;
}
template
void HeapSort(T a[], int len) {
T *ca = new T[len+1]; //复制原数组到二叉堆
ca[0] = 0;
for (int i=0; i
void HeapSort(T a[], int len) {
T *ca = new T[len+1];
ca[0] = 0;
for (int i=0; i0; i--) //建立初始堆
HeapAdjust(ca, len, i);
for (int i=len; i>1; i--)//进行len-1次循环～完成堆排序
{
Swap(ca[1], ca[i]); //新大顶堆的第一个元素与最后一个元素交换
HeapAdjust(ca, i-1, 1);//筛a[1]元素～得到i-1个元素的堆
}
for (int i=0; i
void HeapAdjust(T a[], int len, int left) //将i与其小儿子交换位置
{
if (len == 0)
exit(1);
T x = a[left];
int i = left;
int c = 2 * i;
while (c <= len)
{
if (c < len && a[c+1] > a[c])//若i有右儿子～且右儿子大于左儿子～c指向右儿子
c++;
if (last < a[c])//若i的大儿子大于二叉堆的最后一个元素～把其移到i的位置
{
a[i] = a[c];
i = c;
c = 2 * i;
}
else
break;
}
a[i] = x; //把原二叉堆的第一个元素放到适当的空位 }
template
void Swap(T & a, T & b) {
T t = a;
a = b;
b = t;
}
还有一种方法是每次都要重新调整大顶堆～使得父亲比儿子大～这样调整的函数较简单～但因为每次都要遍历一半的元素～时间复杂度较大。
算法如下:
template
void HeapSort(T a[], int len) {
T *ca = new T[len+1];
ca[0] = 0;
for (int i=0; i0; i--) //把原数组构建成一个大顶堆
HeapAdjust(ca, len, i);
Swap(ca[1], ca[len]); //把大顶堆的第一个元素与最后一个元素交换
for (int i=len-1; i>0; i--)
{
for (int j=i/2; j>0; j--)//遍历长度为i的堆～得到新的大顶堆
HeapAdjust(ca, i, j);
Swap(ca[1], ca[i]);
}
for (int i=0; i
void HeapAdjust(T a[], int len, int i) //将i与其小儿子交换
位置
{
int c = 2 * i;
if (c < len)
{
T & max = (a[c] > a[c+1])? a[c] : a[c+1];
if (a[i] < max)
Swap(a[i], max);
}
else
{
if (a[i] < a[c])
Swap(a[i], a[c]);
}
}
template void Swap(T & a, T & b) {
T t = a;
a = b;
b = t;
}
模仿构造大顶堆的方法～我们可以调用HeapAdjust()构造一个二叉堆～并提取二叉堆的根到新数组～然后把原二叉堆的最后一个元素放到根的位置～再调用HeapAdjust()构造一个新二叉堆～依此类推。 算法如下:
template
void HeapSort(T a[], int len) {
T *ca = new T[len+1];
ca[0] = 0;
for (int i=0; i0; i--) //把原数组构建成一个大顶堆
HeapAdjust(ca, len, i);
a[0] = ca[1];
ca[1] = ca[len]; //把二叉堆的最后一个元素放到根的位置
for (int i=len-1; i>0; i--)
{
for (int j=i/2; j>0; j--)
HeapAdjust(ca, i, j);
a[len-i] = ca[1];
ca[1] = ca[i]; //把二叉堆的最后一个元素放到根的位置
}
delete []ca;
}
template void HeapAdjust(T a[], int len, int i)
{
int c = 2 * i;
if (c < len)
{
T & min = (a[c] < a[c+1])? a[c] : a[c+1];
if (a[i] > min)
Swap(a[i], min);
}
else
{
if (a[i] > a[c])
Swap(a[i], a[c]);
}
}
template void Swap(T & a, T & b) {
T t = a;
a = b;
b = t; }
本文档为【堆排序算法】，请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑，
图片更改请在作品中右键图片并更换，文字修改请直接点击文字进行修改，也可以新增和删除文档中的内容。
该文档来自用户分享，如有侵权行为请发邮件ishare@vip.sina.com联系网站客服，我们会及时删除。
[版权声明] 本站所有资料为用户分享产生，若发现您的权利被侵害，请联系客服邮件isharekefu@iask.cn，我们尽快处理。
本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权，请谨慎使用。
网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传，仅限个人学习分享使用，禁止用于任何广告和商用目的。
浙公网安备 33021202002483