玩转排序技巧:C语言实现的堆排序详解
堆排序(Heapsort)是指利用堆积树(堆)这种数据结构所设计的一种排序算法,它是选择排序的一种。
算法分析
在学习堆排序之前我们要先了解堆这种数据结构。
堆的定义如下:n个元素的序列{k1,k2,···,kn}当且满足以下关系时,称之为堆。
若将此序列所存储的向量R[1..n]看做是一棵完全二叉树的存储结构,则堆实质上是满足如下性质的完全二叉树:
树中任一非叶子结点的关键字均不大于(或不小于)其左右孩子(若存在)结点的关键字。
对于一个小顶堆,若在输出堆顶的最小值之后, 使剩余n-1个元素的序列再次筛选形成一个堆,再输出次小值,由此反复进行,便能得到一个有序的序列,这个过程就称之为堆排序。
从上面对于堆排序的叙述我们知道,进行一次堆排序,我们要解决两个问题:
1、如何初始化一个堆
2、 如何在输出堆顶元素之后,调整堆内元素,使其再次形成一个堆。
下面我们先来研究第二个问题(为何这样看了下面的内容你就会明白),以小顶堆为例:
(1)在输出堆顶元素之后以堆中最后一个元素代替之
。
(2)此时根节点的左右子树都是堆,由于右子树根节点的值小于左子树根节点的值且小于根节点的值,则将9与2互换,互换之后我们发现右子树的堆结构被破坏了,这时我们将调整后的9作为根节点继续进行跟上面相同的调整,直到堆结构恢复。
通过上述的调整,我们得到了一个新堆。这也是一次筛选的过程。
其实,初始堆的过程也就是一个反复筛选的过程,若将此序列看成是一个完全二叉树,则最后一个非终端节点是(N/2)这也是我们筛选的开始点,从下至上进行筛选过程,最后得到有序序列也就是堆排序。(这一步比较难理解建议自己画图看着算法揣摩揣摩)。
代码实现
#include <stdio.h>
#include <malloc.h>
void HeapAdjust(int a[],int s,int m)//一次筛选的过程
{
int rc,j;
rc=a[s];
for(j=2*s;j<=m;j=j*2)//通过循环沿较大的孩子结点向下筛选
{
if(j<m&&a[j]<a[j+1]) j++;//j为较大的记录的下标
if(rc>a[j]) break;
a[s]=a[j];s=j;
}
a[s]=rc;//插入
}
void HeapSort(int a[],int n)
{
int temp,i,j;
for(i=n/2;i>0;i--)//通过循环初始化顶堆
{
HeapAdjust(a,i,n);
}
for(i=n;i>0;i--)
{
temp=a[1];
a[1]=a[i];
a[i]=temp;//将堆顶记录与未排序的最后一个记录交换
HeapAdjust(a,1,i-1);//重新调整为顶堆
}
}
int main()
{
int n,i;
scanf("%d",&n);
int a[n+1];
for(i=1;i<=n;i++)
{
scanf("%d",&a[i]);
}
HeapSort(a,n);
}
复杂度分析
堆排序方法对记录较少的文件并不值得提倡,但对n较大的文件还是很有效的。
堆排序在最坏情况下,其时间复杂度也为O(nlogn)。