数据结构实例精讲排序.docx
《数据结构实例精讲排序.docx》由会员分享，可在线阅读，更多相关《数据结构实例精讲排序.docx（42页珍藏版）》请在冰点文库上搜索。
数据结构实例精讲排序
数据结构实例精讲：
排序
排序是计算机程序设计中的一种重要操作，它的功能是将一个数据元素或记录的任意序列，重新排列成一个以关键字递增（或递减）排列的有序序列。
由于在讨论排序算法时，人们主要关心作为排序依据的关键字，因此大多数教材在讨论算法实现时，均认为各记录的数据类型为如下的elemtype类型，待排序的各个记录顺序存储在一维数组r中。
typedefstruct{
KeyTypekey；//关键字项
InfoTypeotherinfo；//其他数据项
}Elemtype；
ElemTyper[n]；
在本章中，我们再进行简化，在讨论算法实现时，以一维整型数组的非递减有序排列作为实例。
8.1插入排序
插入排序的基本思想是顺序将一个待排序的记录按其关键字值的大小插入到一个有序的序列中，插入后该序列仍然是有序的。
8.1.1直接插入排序
直接插入排序是一种最简单的排序方法。
它的排序过程为：
先将待排序序列中第1个记录看成是一个有序的子序列，然后从第2个记录起依次逐个地插入到这个有序的子序列中去，如图8-1所示。
图中方括号[]中为已排好序的记录关键字的子序列，下划线的关键字表示它对应的记录后移了一个位置。
这很像玩扑克牌时一边抓牌一边理牌的过程，抓一张牌就插入到其应有的位置上去。
图8-1直接插入排序的排序过程示例
【实例8-1】直接插入排序。
编写一个程序，用直接插入排序方法将随机生成的100个整数按从小到大的顺序排列输出。
（1）问题分析。
将整个数组（n个元素）看成是由有序的（a[0]，…，a[i-1]）和无序的（a[i]，…，a[n-1]）两个部分组成；初始时i等于1，每趟排序时将无序部分中的第一个元素a[i]插入到有序部分中的恰当位置，共需进行n-1趟，最终使整个数组有序。
排序操作是一个二重循环，外循环控制排序趟数（1~n-1），内循环在有序部分中寻找当前元素a[i]的插入位置。
（2）源程序。
#include
#include
#include
usingnamespacestd;
#defineN100
voidInsertSort（inta[],intn）//直接插入排序
{
inti,j,t;
for（i=1;i{
t=a[i];
j=i-1;
while（j>=0&&t{
a[j+1]=a[j];
j--;
}
a[j+1]=t;
}
}
intmain（）
{
inta[N],i;
srand（time（0））;
for（i=0;ia[i]=rand（）%1000;
cout<<"初始序列为：
"<for（i=0;icout<cout<InsertSort（a,N）;
cout<<"非递减排序后，序列为：
"<for（i=0;icout<cout<return0;
}
（3）算法分析。
由算法可见，整个排序过程中只包含关键字的比较和移动两种运算。
为了正确地插入第i个元素，最少比较1次（此时原始序列中各数据元素已经按关键字递增的顺序排列），移动2次（t=a[i]和a[i]=t）；最多要比较i次（此时原始序列中各记录按关键字递减的顺序排列），移动i+1次。
所以排序过程所做的平均比较次数和平均移动次数分别为
平均比较次数
平均移动次数
由此，直接插入排序的时间复杂度为О（n2）。
并且直接插入排序方法是稳定的，因为它不会改变原序列中具有相同关键字记录的相对次序。
8.1.2希尔排序
希尔排序又称缩小增量排序，它对直接插入排序作了较大的改进。
在直接插入排序中，只比较相邻的两个记录，一次比较最多把记录移动一个位置。
如果对相隔较大距离的记录进行比较，就能使记录在比较后移动较大的距离，这样能使较小的记录尽快往前移，较大的记录尽快往后移，从而提高排序的速度。
希尔排序就是基于这样的思路。
其方法是：
（1）先取一个整数d1凡是距离为d1倍数的记录，均放在一个子序列内，并在各自的子序列内进行直接插入排序。
（2）然后取d2（3）依次取每一个di图8-2所示为希尔排序的一个例子。
初始关键字序列为{34，18，23，89，39，15，56，14，48，24}，首先取增量d1=5，将该序列分成五个子序列{R1，R6}，{R2，R7}，…，{R5，R10}，分别对每个子序列进行直接插入排序，得到新的排序结果如图8-2（a）所示（这一过程称为一趟希尔排序）。
然后进行第二趟希尔排序，此时取增量d2=3，即分别对三个子序列{R1，R4，R7，R10}，{R2，R5，R8}和{R3，R6，R9}进行第二趟直接插入排序，得到新的排序结果如图8-2（b）所示。
最后对整个序列进行一趟直接插入排序（即取增量d3=1），得到最终的排序结果如图8-2（c）所示。
至此，希尔排序结束。
【实例8-2】希尔排序。
编写一个程序，用希尔排序方法将随机生成的100个整数按从小到大的顺序排列输出。
（1）源程序。
#include
#include
#include
usingnamespacestd;
#defineN100
voidShellSort（intr[],intn,intd[],intnum）
//按增量序列d[num]对r[0]~r[n-1]进行希尔排序
{
inti,j,k,t;
for（k=0;k{
for（i=d[k];iif（r[i]{
t=r[i];
j=i-d[k];
while（j>=0&&t{
r[j+d[k]]=r[j];
j=j-d[k];
}
r[j+d[k]]=t;
}
}
}
图8-2希尔排序的排序过程示例
intmain（）
{
inta[N],i;
intd[5]={11,7,5,3,1};//定义增量序列
srand（time（0））;
for（i=0;ia[i]=rand（）%1000;
cout<<"初始序列为：
"<for（i=0;icout<cout<ShellSort（a,N,d,5）;
cout<<"非递减排序后，序列为：
"<for（i=0;icout<cout<return0;
}
（2）算法分析。
希尔排序的效率要比直接插入排序高，但具体分析颇为困难，因为它与增量序列的选取有关。
大量研究证明，若增量序列取值比较合理，希尔排序的平均比较次数和平均移动次数接近于O（n（log2n）2）。
增量序列有各种不同的取法，通常可取d1=[n/2]、d2=[d1/2]、…、dn=1，最好都取奇数，且互质，最后一个增量值必须等于1。
希尔排序是不稳定的。
8.2选择排序
选择排序的基本思想是在待排序的n个记录中用某种方法选出关键字最小（或最大）的记录，然后再从其余n-1个记录中选出关键字最小（或最大）的记录；依次类推，直至选出n个记录。
8.2.1直接选择排序
直接选择排序是一种比较简单的排序方法，它的排序过程为：
先从待排序的所有记录中选出关键字最小的记录，把它与原始序列中的第一个记录交换位置；然后再从去掉了关键字最小的记录的剩余记录中选出关键字最小的记录，把它与原始序列中第二个记录交换位置；依次类推，直至所有的记录成为有序序列。
直接选择排序的排序过程如图8-3所示。
图中方括号[]中为已排好序的记录关键字的子序列，下划线的关键字表示它对应的记录对需要交换位置。
图8-3直接选择排序的排序过程示例
【实例8-3】直接选择排序。
编写一个程序，用直接选择排序方法将随机生成的100个整数按从小到大的顺序排列输出。
（1）问题分析。
直接选择排序的过程是一个二重循环，外循环（i）控制排序趟数（0~n-2），内循环（j）寻找序列a[i]~a[n-1]中的最小者。
寻找一个序列最小值的方法是：
先假定序列的第一个元素是最小值，然后将序列的第2个元素至最后一个元素依次与这个最小值比较，如果某个元素比最小值要小，则最小值就是这个元素。
（2）函数程序代码。
voidSelectSort（intr[],intn）//简单选择排序
{
inti,j,k,temp;
for（i=0;i{
k=i;
for（j=i+1;jif（r[j]if（k!
=i）
{temp=r[i];r[i]=r[k];r[k]=temp;}
}
}
（3）算法分析。
从上述过程可见，在n个关键字中进行直接选择排序，共需要进行n-1次选择和交换，每次选择需要比较n-i次（1≤i≤n-1），每次交换最多需移动3次记录，总的比较次数为（n-1）+（n-2）+…+1=（n-1）*n/2，总的记录移动次数为3*（n-1），故直接选择排序的时间复杂度为О（n2）。
由于在直接选择排序中，存在着不相邻元素之间的互换，因而可能会改变具有相同关键字记录的前后位置，所以此方法是不稳定的。
（4）源程序。
#include
#include
#include
usingnamespacestd;
#defineN100
voidSelectSort（intr[],intn）;//简单选择排序
intmain（）
{
inta[N],i;
srand（time（0））;
for（i=0;ia[i]=rand（）%1000;
cout<<"初始序列为：
"<for（i=0;icout<cout<SelectSort（a,N）;
cout<<"非递减排序后，序列为：
"<for（i=0;icout<cout<return0;
}
voidSelectSort（intr[],intn）//简单选择排序
{
inti,j,k,temp;
for（i=0;i{
k=i;
for（j=i+1;jif（r[j]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{
升级会员 