if(k!
=i)
{temp=r[i];r[i]=r[k];r[k]=temp;}
}
}
8.2.2堆排序
堆排序是在直接选择排序法的基础上借助于完全二叉树结构而形成的一种排序方法。
堆的定义如下:
设有n个元素组成的序列{a1,a2,…,an},若它满足条件:
①这些元素是一棵完全二叉树中的结点,且对于i=1、2、…、n,ai是该完全二叉树中编号为i的结点;②若2i≤n,有a2i≥ai;③2i+1≤n,有a2i+1≥ai;则称该序列为堆。
根据堆的定义,可以推知堆有下面的两个性质:
(1)堆的根结点是堆中值最小的元素,称之为堆顶元素。
(2)从根结点到每个叶结点的路径上,元素组成的序列都是非递减有序的。
由于顺序存储结构可以方便地存储一棵完全二叉树,因此可以把n个元素组成的序列存储在一维数组r[n]中,如果该序列是一个堆,则r[0]就是堆顶元素(完全二叉树的根结点)。
将待排序的数据序列建成一个堆,并借助于堆的性质进行排序的方法叫做堆排序。
堆排序的基本思想是:
将原始记录序列建成一个堆,称之为初始堆,并输出堆顶元素;然后把剩余的记录序列调整成堆,再输出堆顶元素;如此反复进行,当堆中只有一个元素时,整个序列的排序结束,输出的序列便是原始序列的递增有序序列。
【实例8-4】堆排序。
编写一个程序,用堆排序方法将随机生成的100个整数按从小到大的顺序排列输出。
(1)问题分析。
实现堆排序需要解决两个问题:
一是如何由一个无序序列建成一个堆;二是如何在输出堆顶元素之后,调整剩余元素成为一个新的堆。
先研究第一个问题,基本方法是将大的元素下沉,小的元素上浮,即所谓的筛选法。
对某一结点进行筛选的具体方法是:
比较该结点左、右孩子的值,若该结点的值大于其中较小的值,则交换该结点和该结点的值较小孩子结点的位置,然后该结点继续和新的孩子结点相比较交换,…,当该结点下移到某一位置时,它的左、右孩子结点的值都大于它的值或者它已成为叶结点,则对该结点的筛选工作完成。
若将待排序序列看成是一个完全二叉树,则最后一个非终端结点是第n/2个元素。
从第n/2个元素开始,至完全二叉树的根结点(即编号为1的结点)止,依次对每个非终端结点进行筛选运算后,就可以得到初始堆。
图8-4初始堆的建立过程
例如,图8-4(a)中的完全二叉树表示一个有5个元素的无序序列{89,39,15,56,14},筛选从第2个元素39开始。
由于39>14,则交换之,交换后的序列如图8-4(b)所示。
第1个元素(即根)89>14,则沿左筛下,与14交换,再与39交换,最后建成的初始堆如图8-4(c)所示。
现在考虑第二个问题。
当输出堆顶元素后,就以堆中最后一个元素替代之。
此时,根结点的左、右子树均为堆,只需将根结点的新元素筛选到适当的位置,就完成了重建堆的工作。
此时堆中的元素已减少一个。
上面介绍的是建小顶堆的方法。
若要将数据元素按递减顺序排列,可以建大顶堆,即堆顶元素为最大值,每个结点的值均不小于其左右子结点的值。
另外,数组元素下标从0开始,而完全二叉树按层序编号时第1个结点(根结点)从1开始。
因此,要注意数组下标与结点编号之间的转换。
(2)主要函数程序代码。
voidHeapAdjust(int*h,ints,intm)//用筛选法对h[s]进行筛选,使h[s]~h[m]成为一个堆
{
inttmp,j;
tmp=h[s];
for(j=2*s+1;j<=m;j=2*j+1)
{//沿元素值较大的孩子结点向下筛选
if(j++j;//j为值较大的元素的下标
if(tmp>=h[j])
break;//tmp应插入在位置s上
h[s]=h[j];s=j;
}
h[s]=tmp;//插入
}
voidHeapSort(int*h,intn)//对数组h进行堆排序。
{
intt,i;
for(i=(n+1)/2-1;i>=0;--i)//把h[0..n-1]建成大顶堆
HeapAdjust(h,i,N-1);
for(i=n-1;i>0;--i)
{
t=h[0];h[0]=h[i];h[i]=t;
HeapAdjust(h,0,i-1);//将h[0..i-1]重新调整为大顶堆
}
}
(3)算法分析。
在上面算法中,为方便起见,堆顶元素并没有直接输出,而是和当前堆中最后一个元素互换位置,所以,当排序结束时,各记录按照其关键字非递减顺序存储在数组h中,如果需要按照关键字非递增顺序输出各记录,则倒序输出h中各元素值即可。
对记录数较少的文件不提倡采用堆排序,但对记录数较多的文件堆排序却是十分有效的。
因为其运行时间主要耗费在建初始堆和调整建新堆时进行的反复“筛选”上。
在最坏的情况下,其时间复杂度为О(nlog2n)。
此外,堆排序仅需一个记录大小的辅助存储空间,以供交换记录时使用。
堆排序是不稳定的。
(4)源程序。
#include
#include
#include
usingnamespacestd;
#defineN100
voidHeapAdjust(int*h,ints,intm);//用筛选法进行堆的调整
voidHeapSort(int*h,intn);//对数组h进行堆排序。
intmain()
{
inta[N],i;
srand(time(0));
for(i=0;ia[i]=rand()%1000;
cout<<"初始序列为:
"<for(i=0;icout<cout<HeapSort(a,N);
cout<<"非递减排序后,序列为:
"<for(i=0;icout<cout<return0;
}
voidHeapAdjust(int*h,ints,intm)//用筛选法进行堆的调整
{
inttmp,j;
tmp=h[s];
for(j=2*s+1;j<=m;j=2*j+1)
{//沿元素值较大的孩子结点向下筛选
if(j++j;//j为值较大的元素的下标
if(tmp>=h[j])
break;//tmp应插入在位置s上
h[s]=h[j];s=j;
}
h[s]=tmp;//插入
}
voidHeapSort(int*h,intn)//对数组h进行堆排序。
{
intt;
inti;
for(i=(n+1)/2-1;i>=0;--i)//把h[0..n-1]建成大顶堆
HeapAdjust(h,i,N-1);
for(i=n-1;i>0;--i)
{
t=h[0];h[0]=h[i];h[i]=t;
HeapAdjust(h,0,i-1);//将h[0..i-1]重新调整为大顶堆
}
}
8.3交换排序
交换排序的基本思想是两两比较待排序记录的关键字值,并交换不满足顺序要求的那些记录对,直到全部记录满足关键字值排序要求为止。
8.3.1冒泡排序
冒泡排序又称起泡排序,它也是一种简单常用的排序方法。
其基本思想是通过相邻记录之间关键字的比较和交换,使关键字值较小的记录逐渐从底部移向顶部,即从下标较大的单元移向下标较小的单元,就像水底下的气泡一样逐渐向上冒;而关键字较大的记录就像石块往下沉一样,每一趟有一块“最大”的石头沉到水底。
冒泡排序的排序过程为:
先将第1个记录和第2个记录进行比较,若为逆序,则交换之;接着比较第2个记录和第3个记录;依次类推,直至第n-1个记录和第n个记录进行比较、交换为止,我们称这样的过程为一趟冒泡排序。
如此经过一趟排序,关键字最大的记录被安置到最后一个记录的位置上。
然后,对前n-1个记录进行同样的操作,使具有次大关键字的记录被安置到第n-1个记录的位置上。
重复以上过程,直到没有记录需要交换为止。
冒泡排序的排序过程如图8-5所示。
【实例8-5】冒泡排序。
编写一个程序,用冒泡排序方法将随机生成的100个整数按从小到大的顺序排列输出。
(1)问题分析。
冒泡排序的过程是一个二重循环,外循环(i)控制排序趟数(0~n-2),内循环(j)将序列a[0]~a[n-1-i]中每个元素依次与其后面的一个元素比较,如果前面的元素a[j]比其后的元素a[j+1]大,将二者交换。
图8-5冒泡排序的排序过程示例
(2)函数程序代码。
voidBubbleSort(intr[],intn)//对数组r进行冒泡排序
{
inti,j,temp;
boolflag=true;
for(i=0;i{
flag=false;
for(j=0;jif(r[j]>r[j+1])
{
flag=true;
temp=r[j];
r[j]=r[j+1];
r[j+1]=temp;
}
}
}
(3)算法分析。
上面的算法中使用了一个布尔变量flag,用于标记在每一趟执行时是否有记录交换。
如果有一趟冒泡排序“空跑”,表示此时已经有序,应结束排序过程。
从冒泡排序算法可以看出,冒泡排序算法的执行时间与序列的原始状态有很大的关系。
若初始序列为“正序”序列,则只需进行一趟排序,在排序过程中进行n-1次关键字间的比较,且不移动记录;反之,若初始序列为“逆序”序列,则需进行n-1趟排序,共需进行(n-1)+(n-2)+…+2+1=n*(n-1)/2次比较,总的记录移动次数为3*n*(n-1)/2。
因此,冒泡排序的时间复杂度为О(n2)。
冒泡排序是稳定的。
(4)源程序。
#include
#include
#include
usingnamespacestd;
#defineN100
voidBubbleSort(intr[],intn);//对数组r进行冒泡排序
intmain()
{
inta[N],i;
srand(time(0));
for(i=0;ia[i]=rand()%1000;
cout<<"初始序列为:
"<for(i=0;icout<cout<BubbleSort(a,N);
cout<<"非递减排序后,序列为:
"<for(i=0;icout<cout<return0;
}
voidBubbleSort(intr[],intn)//对数组r进行冒泡排序
{
inti,j,temp;
boolflag=true;
for(i=0;i{