数据结构-基于C语言的描述第2版课件 第9章 排序_第1页
数据结构-基于C语言的描述第2版课件 第9章 排序_第2页
数据结构-基于C语言的描述第2版课件 第9章 排序_第3页
数据结构-基于C语言的描述第2版课件 第9章 排序_第4页
数据结构-基于C语言的描述第2版课件 第9章 排序_第5页
已阅读5页,还剩77页未读, 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

DATASTRUCTUREDATASTRUCTUREDataStructureBYPENGBO

排序是程序设计中一种重要运算,其功能是将一组记录从任意序列排列成一个按关键字有序(升序或降序)的序列。排序是提高计算机对数据处理的工作效率的必要手段。第9章主要内容排序第章9《数据结构–基于C语言的描述》(第2版)-清华大学出版社DATASTRUCTUREDATASTRUCTUREDataStructureBYPENGBO第9章主要内容9.1

排序的基本概念9.2

插入排序9.3

交换排序排序第章99.4选择排序9.5归并排序9.6基数排序9.7排序方法比较《数据结构–基于C语言的描述》(第2版)-清华大学出版社9.1排序的基本概念

在有序表上进行折半查找的时间复杂度为O(log2n),在无序表上进行顺序查找的时间复杂度为O(n)。因此,排序是提高查找效率的关键。9.1排序的基本概念

●

排序:将一个记录的任意序列重新排列成一个按关键字有序序列。

●

趟:在排序过程中,将待排序的记录序列扫描一遍。

●排序方法稳定性:假定在待排序记录序列中,存在多个相同关键字的记录,如果经过排序,这些记录相对次序保持不变,则称该排序算法是稳定的;否则是不稳定的。

按排序是否建立在关键字比较的基础上来区分,可以将排序方法分为基于比较的排序和不基于比较的排序。

按排序过程中依据的不同原则来区分:可以将排序方法大致分为插入排序、交换排序、选择排序、归并排序和基数排序。

按排序过程中所需要的工作量来区分:可以将排序方法分为简单排序法、先进排序法、基数排序法。

●

排序方法分类:9.1排序的基本概念

●排序的基本操作:其一是比较,即记录的关键字之间的比较;其二是移动,即记录从一个位置移动到另一个位置。

●

待排序记录序列的存储方式:

以顺序表存储待排序记录序列;

以静态链表存储待排序记录序列,该存储方式下排序称链表排序;

以顺序表存储待排序记录序列,并另设一个指示各个记录存储位置的地址向量,该存储方式下排序称地址排序。

●

排序算法性能评价:

时间复杂度:算法执行时间随待排序记录数量变化而变化的度量;

空间复杂度:算法所需辅助空间随待排序记录数量变化而变化的度量。

9.1排序的基本概念

●待排序纪录的数据类型:

为了方便,在本章讨论的大部分算法中待排序记录采用顺序表结构,其类型定义如下:typedefstruct{RedType *r; //基址,建表时按实际值分配,r[0]空

int length; //表长}SqList;

9.2插入排序

插入排序是一类借助“插入”进行排序的方法。基本思想:每次将一个待排记录按其关键字大小插入到一个排好序的有序子序列中,直到全部记录排好序。方法主要包括直接插入排序和希尔排序。

9.2插入排序9.2.1直接插入排序

基本思想:将待排序记录序列划分成有序区和无序区;逐个处理无序区中记录,将其与有序区中记录关键字比较,确定要插入的位置,并将记录插入到有序区中,直至所有纪录插入有序区。

关键问题:其一,如何构造初始有序区序列?其二,如何查找待插记录的插入位置,并完成排序?直接插入排序基本思想设计9.2插入排序9.2.1直接插入排序例9-1对关键字序列{49,38,65,97,76,13,27,49}直接插入排序。

解决1:初始时有序区为待排序记录序列中的第一个记录,无序区包括所有剩余待排序的记录。

解决2:依次将无序区中的记录与有序区中记录关键字比较,确定插入位置并插入记录;重复该过程,直到无序区中没有记录。

voidInsertSort(SqList&L){//对顺序表L作直接插入排序;L.r[0]为哨兵for(i=2;i<=L.length;++i)if(L.r[i].key<L.r[i-1].key){

L.r[0]=L.r[i]; //复制为哨兵for(j=i-1;L.r[0].key<L.r[j].key;--j)L.r[j+1]=L.r[j];L.r[j+1]=L.r[0]; //插入到正确位置

}}//InsertSort监视哨或哨兵L.r[0]的作用:●在查找循环前保存L.r[i]的副本,使不致于因记录后移而丢失其内容;●在查找循环中“监视”下标变量j是否越界(主要作用)。9.2插入排序9.2.1直接插入排序算法9-1

最好情况:待排序记录正序,每趟关键字比较次数1,记录移动次数0;总关键字比较次数n-1,总记录移动次数0,时间复杂度O(n)。

最坏情况:待排序记录反序,第i个记录关键字与前i-1个记录关键字和监视哨中的关键字比较,并将i-1个记录向后移动,总关键字比较(n+2)(n-1)/2次,总记录移动(n-1)(n+4)/2次,时间复杂度O(n2)。

基本思想:将待排序记录序列划分成有序区和无序区;逐个处理无序区中记录,将其与有序区中记录关键字比较,确定要插入的位置,并将记录插入到有序区中,直至所有纪录插入有序区。

关键问题:其一,如何构造初始有序区序列?其二,如何查找待插记录的插入位置?

算法分析:

●空间复杂度S(n)=O(1)(称为就地排序)

●

时间复杂度T(n)=O(n2)9.2插入排序9.2.1直接插入排序

●

算法稳定。适于待排记录序列基本有序或待排记录数目较少的场合。9.2插入排序●

直接插入排序算法简单,在纪录个数少且记录基本有序时效率较高。但如果待排序记录按关键字基本无序,或待排序纪录个数多时,则其效率很低。●

希尔排序从这两点分析出发对待排序纪录分组,对直接插入排序改进得到另一种插入方法,又称“缩小增量排序”,可提高整个排序效率。

基本思想:先将整个待排序记录序列分割成若干个子序列,在子序列内分别进行直接插入排序,待整个序列基本有序时,再对全体记录进行一次直接插入排序。

关键问题:其一,如何分割待排序记录,才能保证整个序列逐步向基本有序发展?

其二,子序列内如何进行直接插入排序?

9.2插入排序9.2.2希尔排序例9-2对关键字序列{25,38,65,97,76,27,13,25}

进行希尔排序

。

设计9.2插入排序9.2.2希尔排序

解决1:取一个正整数d1<n,把L.r[1..n]按此间隔值从第1个记录Lr[1]起分组,所有距离为d1

倍数记录放在一组中,在各组内进行直接插入排序;后来增量逐步缩小,直到1。希尔提出:d1=

n/2

,di+1=

di/2

。

解决2:在每个子序列中,待插入记录和同一子序列中的前一个记录比较,在插入记录L.r[i]时,自L.r[i-d]起往前跳跃式(跳跃幅度为d)查找待插入位置,在查找过程中,记录后移也是跳跃d个位置。

算法9-2voidShellSort(SqList&L){//对顺序表L作希尔排序

dk=L.length/2;while(dk!=1){

ShellInsert(L,dk);dk=dk/2;}}//ShellSort9.2插入排序9.2.2希尔排序voidShellInsert(SqList&L,intd){//对顺序表L作一趟希尔插入排序,前后增量是d;L.r[0]只作为暂存单元for(i=d+1;i<=L.length;++i)if(L.r[i].key<L.r[i-d].key){

L.r[0]=L.r[i]; //暂存在L.r[0]for(j=i-d;(j>0)&&(L.r[0].key<L.r[j].key);j-=d)L.r[j+d]=L.r[j];L.r[j+d]=L.r[0]; //插入到正确位置}}//ShellInsert希尔排序的每组插入与一趟直接插入排序相比,作了两处修改:●前后记录位置的增量为dk,而不为1;●

L.r[0]只作暂存单元而不作哨兵,当j<=0时,插入位置已找到。

如果按照希尔的提法:dk1=n/2,dki+1=

dki/2

,每次后一个增量是前一个增量的1/2,则经过t=log2n次分组后,dkt=1。希尔排序算法的执行次数为log2n,一趟希尔插入算法的执行次数为n。

基本思想:先将整个待排序记录序列分割成若干个子序列,在子序列内分别进行直接插入排序,待整个序列基本有序时,再对全体记录进行一次直接插入排序。

关键问题:其一,如何分割待排序记录,才能保证整个序列逐步向基本有序发展?

其二,子序列内如何进行直接插入排序?

算法分析:

●空间复杂度S(n)=O(1)(就地排序)

●

算法不稳定。其性能在待排记录数目较多时更能得到充分发挥。

●

时间复杂度T(n)=O(nlog2n)9.2插入排序9.2.2希尔排序

交换排序是一类借助“交换”进行排序的方法。基本思想:在待排序序列中选择两个记录,将其关键字进行比较,如果反序则交换其位置。方法主要包括冒泡排序和快速排序。

9.3交换排序9.3交换排序9.3.1冒泡排序

基本思想:将待排序记录序列划分成有序区和无序区;对无序区从后向前依次比较相邻记录关键字,如果反序则交换,从而使得关键字小的记录前移,关键字大的记录后移;重复该过程,直到无序区中没有反序记录为止。

关键问题:其一,如何确定待排序记录的范围,使得已经位于最终位置的记录不参与下一趟排序?其二,如何判别冒泡排序结束?

冒泡排序基本思想例9-3对关键字序列{13,49,38,65,97,76,27,49}

进行冒泡排序

。

设计9.3交换排序9.3.1冒泡排序不交换不交换不交换不交换不交换不交换不交换不交换不交换不交换不交换不交换

解决1:初始时有序区为空,无序区包括所有待排记录。设有序区右边界为最后一个记录的位置,下一个位置的记录为无序区的第一个记录。

解决2:对无序区从后向前依次比较相邻记录关键字,反序则交换;

重复执行直到无序区中没反序记录。为提高排序效率,设标志:0为在一趟排序中交换过记录;1为在一趟排序中没交换过记录,纪录已有序,排序提前结束。

在第4趟排序过程中没有进行交换记录的操作,则说明此时n个记录已有序,所以冒泡排序应该提前结束。voidBubbleSort(SqList&L){//对顺序表L作冒泡排序tag=0; //设置标志tagfor(bound=0;tag==0;++bound){

tag=1;for(i=n-1;i>bound;--i) //一趟冒泡排序if(L.r[i+1].key<L.r[i].key){L.r[0]=L.r[i+1];L.r[i+1]=L.r[i];L.r[i]=L.r[0];

tag=0;}}}//BubbleSort9.3交换排序9.3.1冒泡排序

最好情况:待排序记录正序,只需要进行一趟排序,总关键字比较次数为n-1,且不移动记录,时间复杂度O(n);

最坏情况:待排序记录反序,需要进行n-1趟排序,总关键字比较次数为n(n-1)/2,且作等量级的记录移动。时间复杂度O(n2)。算法9-39.3交换排序9.3.1冒泡排序

基本思想:将待排序记录序列划分成有序区和无序区;对无序区从后向前依次比较相邻记录关键字,如果反序则交换,从而使得关键字小的记录前移,关键字大的记录后移;重复该过程,直到无序区中没有反序记录为止。

关键问题:其一,如何确定待排序记录的范围,使得已经位于最终位置的记录不参与下一趟排序?其二,如何判别冒泡排序结束?

算法分析:

●空间复杂度S(n)=O(1)(就地排序)

●

算法稳定。适于待排记录序列基本有序或待排记录数目较少场合。

●

时间复杂度T(n)=O(n2)9.3交换排序●

冒泡排序

记录关键字的比较和纪录移动是在相邻位置进行的,记录每一次交换只能前移或后移一个位置,因而总的比较和移动次数比较多,造成排序效率较低。

●

快速排序

考虑记录关键字的比较和纪录移动从两端向中间进行,记录每一次移动的距离比较远,从而减少了总的比较和移动次数,可以得到较高的排序效率。9.3交换排序

基本思想:选一个轴值(即比较基准),将待排序记录序列分割成独立的两部分,左侧记录关键字均小于或等于轴值,右侧记录关键字均大于或等于轴值,然后分别对这两部分重复上述过程,直到整个序列有序为止。

关键问题:其一,如何选择轴值?其二,在待排序记录序列中如何进行分区(也称一次划分)?其三,如何处理分区得到的两个待排序记录子序列以及如何判别快速排序的结束?

9.3.2快速排序快速排序基本思想解决2:①初始化:设置两个参数low和high,分别用来指示将要与轴记录进行比较的左侧记录位置和右侧记录位置,也就是本次划分的区间。

解决2:③左扫描:将轴值与low指向关键字比较,若正序则low后移一个记录位置;重复左侧扫描,直到反序,如果low<high,则将轴记录与low指向的记录进行交换。

解决2:②右扫描:将轴值与high指向关键字比较,若正序则high前移一个记录位置;重复右侧扫描,直到反序,如果low<high,则将轴记录与high指向的记录进行交换。

解决1:通常选取待排序记录序列中第一个记录作为轴值。

9.3交换排序9.3.2快速排序例9-4对关键字序列{38,13,27,76,65,49,49,97}

进行快速排序

。

lowhigh

38lowhigh一趟快速排序过程设计解决2:④重复右、左扫描,直到low与high指向同一位置,即为轴记录最终位置;此时将待排序记录序列以轴记录为基准分成左、右两个子区间。

例9-4对关键字序列{38,13,27,76,65,49,49,97}

进行快速排序

。

769.3交换排序9.3.2快速排序解决3:对待排序序列进行一次划分之后,再分别对左右两个子序列进行递归快速排序,以此类推,直到每个分区都只有一个记录为止。

设计Qsort(L,low,pivotpos-1); //对左区间递归快速排序

Qsort(L,pivotpos+1,high); //对右区间递归快速排序}}//QSort算法9-49.3交换排序9.3.2快速排序voidQuickSort(SqList&L){//对顺序表L作快速排序

Qsort(L,1,L.length); //排序整个文件记录}//QuickSortvoidQsort(SqList&L,intlow,inthigh){//对顺序表L中的子序列L.r[low..hgh]作快速排序。pivotpos是轴记录位置if(low<high){ //仅当区间长度大于1时才排序pivotpos=Partition(L,low,high); //对L.r[low..high]做划分intPartition(SqList&L,intlow,inthigh){//交换顺序表L中子表L.r[low..high]的记录,轴记录到位并返回其所在位置

L.r[0]=L.r[low];pivotkey=L.r[low].key;while(low<high){ //从区间两端交替地向中间扫描 while((low<high)&&(L.r[high].key>=pivotkey))--high; L.r[low]=L.r[high]; while((low<high)&&(L.r[low].key<=pivotkey))++low; L.r[high]=L.r[low];}L.r[low]=L.r[0];returnlow; //轴记录到位,且返回轴位置}//Partition

实现方法:只有在一趟排序后,即low=high位置才是轴记录最后位置。所以可先将轴记录暂存在L.r[0]中,排序中只作L.r[low]或L.r[high]单向移动,直至一趟排序结束后再将轴记录移至正确位置上。voidQuickSort(SqList&L){//对顺序表L作快速排序

Qsort(L,1,L.length); //排序整个文件记录}//QuickSortvoidQsort(SqList&L,intlow,inthigh){//对顺序表L中的子序列L.r[low..hgh]作快速排序。pivotpos是轴记录位置if(low<high){ //仅当区间长度大于1时才排序pivotpos=Partition(L,low,high); //对L.r[low..high]做划分

Qsort(L,low,pivotpos-1); //对左区间递归快速排序

Qsort(L,pivotpos+1,high); //对右区间递归快速排序}}//QSort9.3交换排序9.3.2快速排序算法9-4

最坏情况:待排序记录正序时,需要做n-1次划分,第i次划分开始时右区间长度为n-i+1,需要的比较次数为n-i(1≤i≤n-1),总的比较次数达到n(n-1)/2,蜕化为冒泡排序。

最好情况:每次划分所取的轴都是当前待排序记录序列“中值”记录,划分的左、右两个子区间长度大致相等,则有: T(n)≤2T(n/2)+n ≤2(2T(n/4)+n/2)+n=4T(n/4)+2n ≤4(2T(n/8)+n/4)+2n=8T(n/8)+3n ……… ≤nT(1)+nlog2n=O(nlog2n)因此总的比较次数为nlog2n。

平均情况:设轴记录的关键字为k个(1≤k≤n),且k取1至n之间任何一值的概率相等,则有:可以用归纳法证明,其数量级也为O(nlog2n)。9.3交换排序9.3.2快速排序

关键问题:其一,如何选择轴值?其二,在待排序记录序列中如何进行分区(也称一次划分)?其三,如何处理分区得到的两个待排序记录子序列以及如何判别快速排序的结束?

算法分析:

●

时间复杂度T(n)=O(nlog2n)

●

平均空间复杂度S(n)=O(log2n),最坏空间复杂度S(n)=O(n)

●

算法不稳定。不适用于待排记录基本有序的场合,其性能在待排记录序列无序且数目较多时更能得到充分发挥。

基本思想:选一个轴值(即比较基准),将待排序记录序列分割成独立的两部分,左侧记录关键字均小于或等于轴值,右侧记录关键字均大于或等于轴值,然后分别对这两部分重复上述过程,直到整个序列有序为止。

快速排序在系统内部需要一个栈来实现递归。如果每次划分较为均匀,则其递归深度为O(log2n);最坏的情况下,递归深度为O(n)。9.4选择排序

选择排序是一类借助“选择”进行排序的方法。基本思想:每趟排序在当前待排序列中选出关键字最小记录添加到有序序列中。其特点是记录移动次数较少。方法主要包括简单选择排序和堆排序。9.4选择排序9.4.1简单选择排序

基本思想:将待排序记录序列划分成有序区和无序区;从无序区中选出关键字最小的记录,添加到有序序列中;重复该过程,直到所有纪录全部添加到有序区为止。

关键问题:其一,如何在待排序纪录序列中选出关键字最小的记录?其二,如何确定待排序纪录序列中关键字最小的记录在有序序列中的位置,并完成排序?简单选择排序基本思想9.4选择排序9.4.1简单选择排序例9-5

对关键字序列{49,38,65,49,76,13,27,52}

简单选择排序

。

设计

解决1:将待排记录序列{r1,r2,…,rn}划分为有序区和无序区,初始状态有序区为空,无序区为L.r[1..n]。第i趟通过n-i次关键字的比较,在无序区的n-i+1(1≤i≤n-1)个记录中选取关键字最小记录。

解决2:将选出的关键字最小记录与无序区中第1个记录交换,在第i趟排序中,关键字最小的记录和第i个记录交换作为有序序列的第i个记录。不断重复该过程,直到无序区只剩下一个记录为止。

最好情况:待排序记录正序,第i趟选择最小关键字次数n-i,记录移动次数0;总比较次数n(n-1)/2,总记录移动次数0,时间复杂度O(n2)。voidSelectSort(SqList&L){//对顺序表L作简单选择排序for(i=1;i<L.length;++i){ //选择第i个小关键字记录并交换到位k=i;

for(j=i+1;j<=L.length;++j) //每趟扫描选择key最小记录,记为kif(L.r[j].key<L.r[k].key)k=j;if(i!=k){L.r[0]=L.r[i];L.r[i]=L.r[k];L.r[k]=L.r[0];}}}//SelectSort

最坏情况:待排序记录反序,第i趟选择最小关键字次数n-i,记录移动次数3;总比较次数n(n-1)/2,总记录移动次数3(n-1),时间复杂度O(n2)。9.4选择排序9.4.1简单选择排序算法9-5

●

空间复杂度S(n)=O(1)(就地排序)

●

算法不稳定。适于待排记录数目较少的场合。

9.4选择排序9.4.1简单选择排序

基本思想:将待排序记录序列划分成有序区和无序区;从无序区中选出关键字最小的记录,添加到有序序列中;重复该过程,直到所有纪录全部添加到有序区为止。

关键问题:其一,如何在待排序纪录序列中选出关键字最小的记录?其二,如何确定待排序纪录序列中关键字最小的记录在有序序列中的位置?

算法分析:

●

时间复杂度T(n)=O(n2)说明:简单选择排序在标准实现中是不稳定的,但可通过一些技巧实现稳定的版本。思考:如何改变“交换记录”策略,实现稳定排序。9.4选择排序●

简单选择排序

没有保留前一趟的比较结果,在后一趟选择最小关键字纪录时,把前一趟已做过的比较又重复做一遍,因而造成比较次数较多。

●

堆排序利用树形结构保存每趟比较后的结果,不做重复比较,减少了在后面选择最小关键字中比较次数,从而提高了整个排序的效率。9.4选择排序●树形选择排序

基本思想:

(1)把n个记录的关键字值两两比较,将其中关键字值较小的n/2个记录取出,然后将这n/2个关键字进行两两比较,继续选择具有较小关键字值的记录,直至选出一个最小关键字值;

(2)对余下的n-1个记录的关键字值进行第二趟两两比较,再选出一个次小的关键字;如此反复,直至排序结束为止。

这种两两比较的过程可以用一棵有n个叶子结点的树来描述。上面一层分支结点两两比较得到较小的关键字。依次类推,树根表示最后选出来的最小关键字值,已经选出来的关键字的叶子结点用∞表示。9.4.2堆排序9.4选择排序9.4.2堆排序●树形选择排序

例如:对线性表{33,25,46,13,58,95,18,63}进行树型选择排序。第一趟选择最小关键字过程第二趟选择次小关键字过程9.4选择排序9.4.2堆排序●树形选择排序

例如:对线性表{33,25,46,13,58,95,18,63}进行树型选择排序。第三趟选择下一个次小关键字过程第四趟选择再下一个次小关键字过程第八趟选择再下一个次小关键字过程9.4选择排序9.4.2堆排序●树形选择排序

例如:对线性表{33,25,46,13,58,95,18,63}进行树型选择排序。

由于含有n个叶子结点的完全二叉树的深度为

log2n

+1,则在树形选择排序中,除了最小关键字之外,每选择一个次小关键字仅需要进行

log2n

次比较,因此,它的时间复杂度为O(nlog2n)。

这种排序方法的缺点是占用辅助存储空间较多,和“∞”进行多余的比较等。为了弥补,威洛姆斯在1964年提出了对树型选择排序的改进方法

堆排序。9.4选择排序9.4.2堆排序●堆排序n个元素的序列{k1,k2,…,kn}当且仅当满足下式关系时,称为堆。

一个完全二叉树如果是堆,则根结点(称为堆顶)一定是当前堆中所有结点的最大者(大根堆)或最小者(小根堆)。

以结点编号作为下标,采用顺序存储结构存储堆。

堆的定义9.4选择排序9.4.2堆排序●堆排序

堆排序的方法

基本思想:先将待排序的记录序列构造成一个堆(假设大根堆),选出堆中所有记录关键字最大者,即堆顶记录;再将堆顶记录和堆中最后一个记录交换,并将其再调整成新堆,即找出了关键字次大记录,即堆顶记录。以此类推,直到堆中只有一个记录为止。

关键问题:其一,如何将一个无序序列构造成一个堆,即初始建堆?其二,在输出堆顶记录之后如何调整剩余记录成为一个新堆,即重新建堆?堆排序基本思想先解决关键问题二9.4选择排序9.4.2堆排序●堆排序

堆排序的方法解决2:6个元素的大根堆35和12交换结果12和32交换结果20和12交换,新堆

由于初始建堆并完成第一次交换后,新堆顶可能违反堆性质,因此应该将当前无序区L.r[1..n-1]重新调整为堆。

对第i趟排序,在n-i+1个记录对应的完全二叉树中,只需筛选根结点,即可重新建堆。称为“筛选”。设计9.4选择排序9.4.2堆排序●堆排序

堆排序的方法解决1:在完全二叉树中,所有序号为i>

n/2

的结点都是叶子(已是堆),因此只需要从最后一个分支结点

n/2

开始筛选,直到根。从一个无序序列构造堆的过程就是反复“筛选”的过程。

例如:对关键字序列{12,20,18,32,19,35}

建立大根堆

。

设计9.4选择排序9.4.2堆排序●堆排序

堆排序的方法例9-6对关键字序列{49,38,65,97,40,13,27,49}

进行堆排序

。

(a)无序序列构成完全二叉树(b)筛选L.r[2]后状态(c)筛选L.r[1]后状态,大根堆初始建堆过程设计9.4选择排序9.4.2堆排序●堆排序

堆排序的方法例9-6对关键字序列{49,38,65,97,40,13,27,49}

进行堆排序

。

(a)大根堆(b)

L.r[1]和L.r[8]交换后的状态(c)调整后的新堆输出堆顶元素并调整建新堆过程设计9.4选择排序9.4.2堆排序●堆排序

堆排序的方法例9-6对关键字序列{49,38,65,97,40,13,27,49}

进行堆排序

。

(d)L.r[1]和L.r[7]交换后的状态(e)调整后的新堆(f)L.r[1]和L.r[6]交换后的状态输出堆顶元素并调整建新堆过程设计9.4选择排序9.4.2堆排序●堆排序

堆排序的方法例9-6对关键字序列{49,38,65,97,40,13,27,49}

进行堆排序

。

(g)调整后的新堆(h)

L.r[1]和L.r[5]交换后的状态(i)调整后的新堆输出堆顶元素并调整建新堆过程设计9.4选择排序9.4.2堆排序●堆排序

堆排序的方法例9-6对关键字序列{49,38,65,97,40,13,27,49}

进行堆排序

。

(j)L.r[1]和L.r[4]交换后的状态(k)调整后的新堆(l)L.r[1]和L.r[3]交换后的状态输出堆顶元素并调整建新堆过程设计9.4选择排序9.4.2堆排序●堆排序

堆排序的方法例9-6对关键字序列{49,38,65,97,40,13,27,49}

进行堆排序

。

(m)调整后的新堆(n)L.r[1]和L.r[2]交换后的状态输出堆顶元素并调整建新堆过程设计●堆排序

堆排序的方法voidHeapSort(SqList&L){//对顺序表L进行堆排序for(i=L.length/2;i>0;--i)

HeapAdjust(L,i,L.length); //初始建堆(大根堆)9.4选择排序9.4.2堆排序算法9-6

for(high=L.length;high>1;--high){L.r[0]=L.r[1]; //堆顶记录和最后一个记录交换L.r[1]=L.r[high];L.r[high]=L.r[0];

HeapAdjust(L,1,high-1); //重新建堆}}HeapSortvoidHeapAdjust(SqList&L,intlow,inthigh){//调整L.r[low].key,重建大根堆L.r[0]=L.r[low];for(j=2*low;j<=high;j*=2){ //沿着关键字较大的孩子结点向下筛选if((j<high)&&(L.r[j].key<L.r[j+1].key))++j;if(!(L.r[0].key<L.r[j].key))break;L.r[low]=L.r[j];low=j;}L.r[low]=L.r[0]; //插入在位置low上}//HeapAdjust

对n个待排序记录L.r[1..n]排序的时间主要耗费在初始建堆和调整建新堆的反复“筛选”上。取堆顶记录之后,调整建新堆的最坏时间复杂度为O(log2n),且需要取n-1次堆顶记录。

●空间复杂度S(n)=O(1)(就地排序)

●

时间复杂度T(n)=O(nlog2n)

●

算法不稳定。其性能在待排记录数目较多时更能得到充分发挥。算法只需要一个记录的辅助空间,用来作为记录交换的暂存单元。9.4选择排序9.4.2堆排序●堆排序

堆排序的方法

基本思想:先将待排序的记录序列构造成一个堆(假设大根堆),选出堆中所有记录关键字最大者,即堆顶记录;再将堆顶记录和堆中最后一个记录交换,并将其再调整成新堆,即找出了关键字次大记录,即堆顶记录。以此类推,直到堆中只有一个记录为止。

关键问题:其一,如何将一个无序序列构造成一个堆,即初始建堆?其二,在输出堆顶记录之后如何调整剩余记录成为一个新堆,即重新建堆?

算法分析:9.5归并排序

归并排序是一类借助“归并”进行排序的方法。归并的含义是将两个或两个以上的有序序列组合成一个新的有序序列。基本思想:将若干个有序序列逐步归并,最终归并为一个有序序列。

9.5.12-路归并排序

基本思想:将若干个有序序列进行两两归并,直至所有待排序记录都在一个有序序列为止。

关键问题:其一,如何构造初始有序序列?其二,如何将两个相邻的有序序列归并成一个有序序列(称为一次归并)?

9.5归并排序解决1:初始时,将待排序记录序列L.r[1..n]构造成长度为1的n个有序子序列。

例如

对关键字序列{49,38,65,97,76,13,27,49}2-路归并排序

。

9.5.12-路归并排序9.5归并排序设计解决2:在归并过程中可能会破坏原来的有序序列,因此可以先将两个相邻的有序序列L.r[low..m]和L.r[m+1..high]合并到一个暂存数组t[low..high],待合并完成后再将其复制回L.r[low..high],完成一趟归并。

核心操作。voidMerge(RedType&L.r,intlow,intm,inthigh){//两个有序表L.r[low..m]和L.r[m+1..high]//归并成一个有序表L.r[low..high]i=low;j=m+1;p=0;t=newRedType[high-low+1]; //暂存数组tif(!t)Error("Error!");9.5.12-路归并排序9.5归并排序算法9-7

while((i<=m)&&(j<=high)) //取其小者复制到t中if(L.r[i].key<=L.r[j].key)t[p++]=L.r[i++];elset[p++]=L.r[j++];

while(i<=m)t[p++]=L.r[i++]; //将第1个有序表剩余记录复制到t中while(j<=high)t[p++]=L.r[j++]; //将第2个有序表剩余记录复制到t中

for(p=0,i=low;i<=high;p++,i++)L.r[i]=t[p];delete[]t;}//Merge

算法运行时间主要消耗在将L.r[low..m]和L.r[m+1..high]复制到暂存数组t,及再将t[low..high]复制回L.r[low..high],记录移动次数2n。

●

时间复杂度T(n)=O(n)

该算法在归并过程中需要与原始记录序列同样数量的存储空间,以便存放归并结果。

基本思想:将若干个有序序列进行两两归并,直至所有待排序记录都在一个有序序列为止。

关键问题:其一,如何构造初始有序序列?其二,如何将两个相邻的有序序列归并成一个有序序列(称为一次归并)?

算法分析:

●空间复杂度S(n)=O(n)

●

算法稳定。9.5.12-路归并排序9.5归并排序9.5.2归并排序9.5归并排序例如

对关键字序列{49,38,65,97,76,13,27,49}进行归并排序

。

设计(2)分别将这两个子序列递归调用,得到长度为1的n个子序列;(1)将n个待排序记录序列{r1,r2,…,rn}分为两个长度相等的子序列;(3)调用2-路归并排序算法Merge,将两个相邻有序子序列合并成一个含有全部记录的有序序列。voidMSort(SqList&L){//对顺序表L作归并排序。

MergeSort(L.r,1,L.length);}//MSortvoidMergeSort(RedType&L.r,intlow,inthigh){//对L.r[low..high]进行两路归并排序if(low<high){mid=(low+high)/2; //分解MergeSort(L.r,low,mid); //对L.r[low..mid]递归归并MergeSort(L.r,mid+1,high); //对L.r[mid+1..high]递归归并Merge(L.r,low,mid,high); //将两个有序子区归并为一个有序区}}//MergeSort9.5归并排序9.5.2归并排序算法9-8

该算法需要进行log2n趟2-路归并,而每趟2-路归并的时间为O(n),所以无论是在最好情况下还是在最坏情况下时间复杂度均是O(nlog2n)。

算法分析:

该算法同2-路归并排序一样,在归并过程中需要与原始记录序列同样数量的存储空间,以便存放归并结果,因此其空间复杂度为O(n)。

●空间复杂度S(n)=O(n)

●

时间复杂度T(n)=O(nlog2n)

●

算法稳定。其性能在待排记录数目较多时更能得到充分发挥。

9.5归并排序9.5.2归并排序9.6基数排序

基数排序是一类借助“多关键字”进行排序的方法。基本思想:不需要比较关键字和移动(交换)记录,而是基于多关键字排序的思路对单逻辑关键字进行排序。9.6基数排序9.6.1多关键字排序

文件中任一记录关键字k均由d个分量(k0k1…kd-1)构成。如果这d个分量中的每个分量都是一个独立的关键字,则文件是多关键字的,而关键字k称为单逻辑关键字。

假设文件有n个记录的序列{r1,r2,…,rn},且每个记录ri

中含有d个关键字(ki0ki1…kid-1)。对该记录序列排序,使得对于序列中任意两个记录ri和rj(1≤i<j≤n)都满足:其中:k0

称为最主关键字,kd-1

称为最次关键字,该序列对d个关键字(k0k1…kd-1)称为有序;该排序称为多关键字排序。实现多关键字排序方法:最高位优先法(MSD),最低位优先法(LSD)。9.6基数排序9.6.1多关键字排序●MSD

方法

●对最主关键字k0

进行排序,将序列分成若干个子序列,每个子序列中的记录都具有相同的k0

值;

●分别就每个子序列对关键字k1

进行排序,按k1

值不同再分成若干个更小子序列;依次重复,直至对kd-2

进行排序后得到的每个子序列中记录都具有相同关键字(k0k1…kd-2);●分别就每个子序列对关键字kd-1

进行排序,将所有子序列依次链接在一起成为一个有序序列。●LSD

方法

●

对最次关键字kd-1

进行排序;

●对高一位关键字kd-2

进行排序;依次重复,直至对k0

进行排序后便成为一个有序序列。9.6基数排序9.6.1多关键字排序●MSD

方法与LSD

方法的比较

按MSD进行排序,必须先将序列逐层分割成若干子序列,然后再对各子序列分别进行排序。

按LSD进行排序,不必分成若干个子序列,对每个关键字都是整个序列参加排序,但对ki(1≤i≤d-2)进行排序时要求采用稳定的排序方法。

若每个关键字ki(1≤i≤d-2)取值范围相同,则采用LSD不用通过关键字间比较,而是通过若干次“分配”和“收集”实现排序。9.6基数排序9.6.2链式基数排序

有的关键字可以看成是由若干个关键字复合而成的。

例如:如果关键字k是数值,且数值在0到999之间,则可把k看成由三个关键字(k0,k1,k2)组成,k0

是百位数,k1

是十位数,k2

是个位数,每个关键字的范围相同(0≤k0,k1,k2≤9)。

又如:如果关键字k由五个字母组成的单词,则可以把k看成由五个关键字(k0,k1,k2,k3,k4)组成,ki

是(从左至右)第i+1位上的字母,每个关键字的范围相同('A'≤k0,k1,k2,k3,k4≤'Z')。

9.6基数排序9.6.2链式基数排序●链式基数排序定义

对d个关键字,按LSD从最低位(左高右低)关键字开始,先按关键字的不同值将序列中记录“分配”到rd个子表中,再将其“收集”起来,如此重复d次。按这种方法实现的排序称为基数排序。其中“基”指的是rd的取值范围。因为在基数排序中,待排序记录的数据类型定义为静态链表,所以称为链式基数排序。9.6基数排序9.6.2链式基数排序●链式基数排序定义#difineKey_Size8 //关键字项数的最大值#defineRD10 //关键字基数,此时是十进制数基数#defineSpace_Size 10000 //最大空间,待比较记录最大个数typedefstruct{ //结点ElemType keys[Key_Size];//关键字

InfoType otherinfo; //其他数据项,InfoType依赖于具体应用

int next;}SLNode;typedefstruct{ //静态链表SLNode r[Space_Size]; //静态链表可利用空间,r[0]为头结点

int keynum; //记录的当前关键字个数

int length; //静态链表的当前长度}SLList;typedefintArrType[RD]; //指针数组类型9.6基数排序9.6.2链式基数排序

多关键字个数是4,分别为(k0,k1,k2,k3),其范围均为(0≤k0,k1,k2,k3≤9),RD=10。

例如:设待排序记录的单逻辑关键字序列k为{1183,1263,574,0092,5447,3988,6774,8478}。设计●链式基数排序方法设计9.6基数排序9.6.2链式基数排序●链式基数排序方法(1)第一趟“分配”对关键字k3(个位数)进行。按照k3

的值将记录分配至10个子表中,每个子表中记录关键字的个位数相等;(2)第一趟“收集”是改变所有非空子表尾记录的指针域,令其指向下一个非空子表头记录,将10个子表中的记录重新组成一个链表;(3)第二趟“分配”和“收集”、第三趟“分配”和“收集”、第四趟“分配”和“收集”……分别是对关键字k2

(十位数)、k1

(百位数)、k0

(千位数)……进行的,其方法同(1)和(2)。直至链式基数排序结束。(a)初始状态(b)第一趟分配之后(c)第一趟收集之后(d)第二趟分配之后(e)第二趟收集之后(f)第三趟分配之后(g)第三趟收集之后(h)第四趟分配之后(i)第四趟收集之后,有序序列算法9-9voidRadixSort(SLList&L){//对静态链表L作基数排序

for(i=0;i<L.length;++i)L.r[i].next=i+1;L.r[L.length].next=0;for(i=0;i<L.keynum;++i){ //按LSD依次对各关键字进行分配和收集Distribute(L.r,i,f,e); //第i趟分配Collect(L.r,i,f,e); //第i趟收集}}//RadixSort

9.6基数排序9.6.2链式基数排序●链式基数排序方法

for(p=r[0].next;p;p=r[p].next){j=Ord(r[p].keys[i]); //将记录第i个关键字映射到[0..RD-1]if(!f[j])f[j]=p;elser[e[j]].next=p;e[j]=p; //将p所指的结点插入到第j个子表中}}//Distribute

9.6基数排序9.6.2链式基数排序●链式基数排序方法算法9-9voidDistribute(SLNode&r,inti,ArrType&f,ArrType&e){//静态链表L的r域中记录已经按(keys[0],keys[1],…,keys[i-1])有序//按第i个关键字keys[i]建立RD个子表,使同一个子表中记录的keys[i]相同//f[0..RD-1]和e[0..RD-1]分别指向各子表中的第一个记录和最后一个记录

for(j=0;j<RD;++i)f[j]=0; //各子表初始化为空表intOrd(intKeyBit){//将记录中第i个关键字映射到[0..RD-1];若第i个关键字不合理,则给出相应信息

for(j=0;(j<RD)&&(j!=KeyBit);j++);if(j!=KeyBit)Error("记录关键字不合理!");elsereturnj;}//Ord每一趟“分配”的时间复杂度为O(n)。算法9-9voidRadixSort(SLList&L){//对静态链表L作基数排序

for(i=0;i<L.length;++i)L.r[i].next=i+1;L.r[L.length].next=0;for(i=0;i<L.keynum;++i){ //按LSD依次对各关键字进行分配和收集Distribute(L.r,i,f,e); //第i趟分配Collect(L.r,i,f,e); //第i趟收集}}//RadixSort

9.6基数排序9.6.2链式基数排序●链式基数排序方法

r[0].next=f[j]; //指向第一个非空子表中第一个结点t=e[j];9.6基数排序9.6.2链式基数排序●链式基数排序方法算法9-9voidCollect(SLNode&r,inti,ArrTypef,ArrTypee){//按key

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论