《数据结构C语言严蔚敏清华大学出社排序.pptx》由会员分享，可在线阅读，更多相关《数据结构C语言严蔚敏清华大学出社排序.pptx（165页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、算法中使用了三个指针：其中：p指示第i个记录的当前位置i指示第i个记录应在的位置q指示第i+1个记录的当前位置如何在排序之后调整记录序列？第1页/共165页voidArrange(SLinkListType&SL)p=SL.r0.next;/p指示第一个记录的当前位置for(i=1;in;+i)while(pi)p=SL.rp.next;/第i个记录在SL中的当前位置应不小于i，找到第i个记录，/并用p指示其在SL中当前位置q=SL.rp.next;/q指示尚未调整的表尾if(p!=i)SL.rpSL.ri;/交换记录，使第i个记录到位SL.ri.next=p;/指向被移走的记录p=q;/p指
2、示尚未调整的表尾，/为找第i+1个记录作准备/Arrange第2页/共165页第3页/共165页10.1概述10.2插入排序10.3快速排序10.4选择排序10.5归并排序10.6基数排序10.7各种排序方法的比较讨论第4页/共165页10.1概述一、排序的定义二、排序的基本概念三、内部排序方法的分类第5页/共165页一、排序的定义一、排序的定义什么是排序什么是排序(Sorting)？简单地说，排序就是将一组杂乱无简单地说，排序就是将一组杂乱无章的数据按一定的规律排列起来章的数据按一定的规律排列起来（递增或递减）。（递增或递减）。排序是计算机中经常遇到的操作。排序是计算机中经常遇到的操作。第6
3、页/共165页 数据表数据表数据表数据表(Data List)(Data List)(Data List)(Data List)待排序的数据对象的有限集合。待排序的数据对象的有限集合。待排序的数据对象的有限集合。待排序的数据对象的有限集合。关键字关键字关键字关键字(Key)(Key)作为排序依据的数据对象中的属性域。作为排序依据的数据对象中的属性域。作为排序依据的数据对象中的属性域。作为排序依据的数据对象中的属性域。主关键字主关键字主关键字主关键字 不同的数据对象若不同的数据对象若不同的数据对象若不同的数据对象若关键字互不相同关键字互不相同关键字互不相同关键字互不相同，则这种关键字称为主关键字
4、。则这种关键字称为主关键字。则这种关键字称为主关键字。则这种关键字称为主关键字。排序的确切定义排序的确切定义 使一组任意排列的对象变成一组使一组任意排列的对象变成一组使一组任意排列的对象变成一组使一组任意排列的对象变成一组按关键字线按关键字线按关键字线按关键字线性有序性有序性有序性有序的对象。的对象。的对象。的对象。二、排序的基本概念第7页/共165页排序算法的稳定性排序算法的稳定性排序算法的稳定性排序算法的稳定性 判断标准：关键字相同的判断标准：关键字相同的判断标准：关键字相同的判断标准：关键字相同的数据对象在排序过程中是否保持前后次序不变。数据对象在排序过程中是否保持前后次序不变。数据对象
5、在排序过程中是否保持前后次序不变。数据对象在排序过程中是否保持前后次序不变。如如如如 2,2*,12,2*,1，排序后若为，排序后若为，排序后若为，排序后若为1,2*,2 1,2*,2 则该排序方法则该排序方法则该排序方法则该排序方法是不稳定的。是不稳定的。是不稳定的。是不稳定的。内排序内排序内排序内排序与外排序与外排序与外排序与外排序 区分标准：区分标准：区分标准：区分标准：排序过程是否全部在排序过程是否全部在排序过程是否全部在排序过程是否全部在内存内存内存内存进行。进行。进行。进行。排序的时间开销排序的时间开销排序的时间开销排序的时间开销 它是衡量算法好坏的最重要它是衡量算法好坏的最重要它
6、是衡量算法好坏的最重要它是衡量算法好坏的最重要的标志。通常用算法执行中的的标志。通常用算法执行中的的标志。通常用算法执行中的的标志。通常用算法执行中的数据比较次数数据比较次数数据比较次数数据比较次数和和和和数据移动次数数据移动次数数据移动次数数据移动次数来衡量。来衡量。来衡量。来衡量。第8页/共165页 排序的方法有很多，但简单地判断那一种算 法最好，以便能够普遍选用则是困难的。评价排序算法好坏的标准主要有两条：算法 执行所需要的时间和所需要的附加空间。另外，算法本身的复杂程度也是需要考虑 的一个因素。排序算法所需要的附加空间一般都不大，矛 盾并不突出。而排序是一种经常执行的一 种运算，往往属
7、于系统的核心部分，因此 排序的时间开销是算法好坏的最重要的标 志。第9页/共165页三、内部排序的方法内部排序的过程是一个逐步扩大记录的有序序列长度的过程。经过一趟排序有序序列区无 序 序 列 区有序序列区无 序 序 列 区第10页/共165页待排序记录在内存中怎样存储和处理？顺序排序排序时直接移动记录；链表排序排序时只移动指针；地址排序排序时先移动地址，最后再移动记录。注：地址排序中可以增设一维数组来专门存放记录的地址。内部排序的算法有哪些？按排序的规则不同，可分为5类：插入排序、交换排序、选择排序、归并排序、基数排序按排序算法的时间复杂度不同，可分为3类：v简单的排序算法：时间效率低，O(
8、n2)v先进的排序算法:时间效率高，O(nlog2n)v基数排序算法：时间效率高，O(dn)d关键字的位数(长度)第11页/共165页待排记录的数据类型:#defineMAXSIZE1000/待排顺序表最大长度typedefintKeyType;/关键字类型为整数类型typedefstructKeyTypekey;/关键字项InfoTypeotherinfo;/其它数据项RedType;/记录类型typedefstructRedTyperMAXSIZE+1;/r0闲置或用作哨兵单元intlength;/顺序表长度SqList;/顺序表类型第12页/共165页1.插入将无序子序列中的一个记录“插
9、入”到有序序列中，从而增加记录的有序子序列的长度。第13页/共165页2.交换通过“交换”无序序列中的记录从而得到其中关键字最小或最大的记录，并将它加入到有序子序列中，以此方法增加记录的有序子序列的长度。第14页/共165页3.选择从记录的无序子序列中“选择”关键字最小或最大的记录，并将它加入到有序子序列中，以此方法增加记录的有序子序列的长度。第15页/共165页4.归并通过“归并”两个或两个以上的记录有序子序列，逐步增加记录有序序列的长度。第16页/共165页5.基数不需进行记录关键字间的比较，借助多关键字排序的思想对单逻辑关键字进行排序的方法。第17页/共165页10.2插入排序第18页/
10、共165页第四十八讲数据结构主讲：刘立嘉插入排序与交换排序第19页/共165页有序序列R1.i-1Ri无序序列Ri.n有序序列R1.i无序序列Ri+1.n1、一趟插入排序的基本思想第20页/共165页实现“一趟插入排序”可分三步进行：3将Ri插入(复制)到Rj+1的位置上。2将Rj+1.i-1中的所有记录均后移一个位置；1在R1.i-1中查找Ri的插入位置，R1.j.keyRi.keyRj+1.i-1.key；第21页/共165页直接插入排序（基于顺序查找）表插入排序（基于静态链表存储）不同的具体实现方法导致不同的算法描述折半插入排序（基于折半查找）希尔排序（基于逐趟缩小增量）静态链表：用数组
11、描述的链表第22页/共165页利用“顺序查找”实现“在R1.i-1中查找Ri的插入位置”算法的实现要点：2、直接插入排序第23页/共165页从Ri-1起向前进行顺序查找，监视哨设置在R0；R0=Ri;/设置“哨兵”循环结束表明Ri的插入位置为j+1R0jRifor(j=i-1;R0.keyRj.key;-j);/从后往前找j=i-1插入位置第24页/共165页对于在查找过程中找到的那些关键字不小于Ri.key的记录，并在查找的同时实现记录向后移动；for(j=i-1;R0.keyRj.key;-j);Rj+1=RjR0jRij=i-1上述循环结束后可以直接进行“插入”插入位置第25页/共165
12、页令i=2，3，,n,实现整个序列的排序。for(i=2;i=n;+i)if(Ri.keyRi-1.key)在R1.i-1中查找Ri的插入位置;插入Ri;第26页/共165页voidInsertSort(SqList&L)/对顺序表L作直接插入排序。for(i=2;i=L.length;+i)if(L.ri.keyL.ri-1.key)/InsertSortL.r0=L.ri;/复制为哨兵L.ri=L.ri-1;for(j=i-2;L.r0.keyL.rj.key;-j)L.rj+1=L.rj;/记录后移L.rj+1=L.r0;/插入到正确位置第27页/共165页例49386597761327
13、i=238(3849)6597761327i=365(384965)97761327i=497(38496597)761327i=576(3849657697)1327i=613(133849657697)27i=1()i=7(133849657697)2727jjjjjj977665493827(13273849657697)排序结果：第28页/共165页内部排序的时间分析：实现内部排序的基本操作有两个：（2）“移动”记录。（1）“比较”序列中两个关键字的大小；第29页/共165页n算法评价n时间复杂度n若待排序记录按关键字从小到大排列(正序)Y关键字比较次数：Y记录移动次数：0n若待排序记
14、录按关键字从大到小排列(逆序)Y关键字比较次数：Y记录移动次数：n若待排序记录是随机的，取平均值Y关键字比较次数：Y记录移动次数：T(n)=O(n)n空间复杂度：S(n)=O(1)第30页/共165页直接插入排序的稳定性直接插入排序的稳定性直接插入排序是一种稳定的排序方直接插入排序是一种稳定的排序方法。法。原理：关键字相同的两个对象，在原理：关键字相同的两个对象，在整个排序过程中，不会通过比较而整个排序过程中，不会通过比较而相互交换。相互交换。第31页/共165页因为R1.i-1是一个按关键字有序的有序序列，则可以利用折半查找实现“在R1.i-1中查找Ri的插入位置”，如此实现的插入排序为折半
15、插入排序。3、折半插入排序第32页/共165页voidBInsertSort(SqList&L)/BInsertSort/在L.r1.i-1中折半查找插入位置；for(i=2;i=high+1;-j)L.rj+1=L.rj;/记录后移L.rhigh+1=L.r0;/插入第33页/共165页low=1;high=i-1;while(low=high)m=(low+high)/2;/折半if(L.r0.keyL.rm.key)high=m-1;/插入点在低半区elselow=m+1;/插入点在高半区第34页/共165页例算法评价时间复杂度：T(n)=O(n)空间复杂度：S(n)=O(1)i=1(3
16、0)1370853942620i=213(1330)70853942620i=76(6133039427085)20.i=820(6133039427085)20sjmi=820(6133039427085)20sjmi=820(6133039427085)20sjmi=820(6133039427085)20sji=820(613203039427085)第35页/共165页基本思想：对待排记录序列先作“宏观”调整，再作“微观”调整。所谓“宏观”调整，指的是，“跳跃式”的插入排序。具体做法为：将记录序列分成若干子序列，分别对每个子序列进行插入排序。4、希尔排序（缩小增量排序）第36页/共16
17、5页其中，d称为增量，它的值在排序过程中从大到小逐渐缩小，直至最后一趟排序减为1。例如：将n个记录分成d个子序列：R1，R1+d，R1+2d，R1+kdR2，R2+d，R2+2d，R2+kdRd，R2d，R3d，Rkd，R(k+1)d第37页/共165页例如：162512304711233691831第一趟希尔排序，设增量d=5112312918162536304731第二趟希尔排序，设增量d=3918121123162531304736第三趟希尔排序，设增量d=1911121618232530313647第38页/共165页voidShellInsert(SqList&L,intdk)for
18、(i=dk+1;i=n;+i)if(L.ri.key0&(L.r0.keyL.rj.key);j-=dk)L.rj+dk=L.rj;/记录后移，查找插入位置L.rj+dk=L.r0;/插入/if/ShellInsert第39页/共165页voidShellSort(SqList&L,intdlta,intt)/按增量序列dlta0.t-1对顺序表L作希尔排序for(k=0;kr2.key，则交换；然后比较第二个记录与第三个记录；依次类推，直至第n-1个记录和第n个记录比较为止第一趟冒泡排序，结果关键字最大的记录被安置在最后一个记录上对前n-1个记录进行第二趟冒泡排序，结果使关键字次大的记录被安
19、置在第n-1个记录位置重复上述过程，直到“在一趟排序过程中没有进行过交换记录的操作”为止第45页/共165页起泡排序示例起泡排序示例i (0)(1)(2)(3)(4)(5)i (0)(1)(2)(3)(4)(5)21 25 49 25*16 08 21 25 49 25*16 08 1 1 0808 21 25 49 25*16 21 25 49 25*16 2 2 08 1608 16 21 25 49 25*21 25 49 25*3 3 08 16 21 08 16 21 25 25*49 25 25*49 4 4 08 16 21 25 25*4908 16 21 25 25*49第4
20、6页/共165页起泡排序算法BUBBLESORT(rectype R)int i,j,noswap;rectype temp;for(i=0;i=i;j+)if(Rj+1.keyRj.key)tempRj+1;Rj+1=Rj;Rjtemp;noswapFALSE;if(noswap)break;第47页/共165页起泡排序的时间复杂度起泡排序的时间复杂度考虑关键字的比较次数和对象移动次数考虑关键字的比较次数和对象移动次数1 1、在最好情况下，初始状态是递增有序的，一趟扫描就、在最好情况下，初始状态是递增有序的，一趟扫描就可完成排序，关键字的比较次数为可完成排序，关键字的比较次数为n-1n-1，
21、没有记录移动。，没有记录移动。2 2、若初始状态是反序的，则需要进行、若初始状态是反序的，则需要进行n-1n-1趟扫描，每趟扫趟扫描，每趟扫描要进行描要进行n-in-i次关键字的比较，且每次需要移动记录三次关键字的比较，且每次需要移动记录三次，因此，最大比较次数和移动次数分别为：次，因此，最大比较次数和移动次数分别为：起泡排序方法是稳定的。起泡排序方法是稳定的。空间复杂度：S(n)=O(1)第48页/共165页本节结束第49页/共165页第四十九讲数据结构主讲：刘立嘉快速排序与归并排序第50页/共165页基本思想：通过一趟排序，将待排序记录分割成独立的两部分，其中一部分记录的关键字均比另一部分
22、记录的关键字小，则可分别对这两部分记录进行排序，以达到整个序列有序排序过程：对rst中记录进行一趟快速排序，附设两个指针i和j，设枢轴记录rp=rs，x=rp.key初始时令i=s,j=t首先从j所指位置向前搜索第一个关键字小于x的记录，并和rp交换再从i所指位置起向后搜索，找到第一个关键字大于x的记录，和rp交换重复上述两步，直至i=j为止再分别对两个子序列进行快速排序，直到每个子序列只含有一个记录为止1、快速排序第51页/共165页一、一趟快速排序（一次划分）目标：找一个记录，以它的关键字作为“枢轴”，凡其关键字小于枢轴的记录均移动至该记录之前，反之，凡关键字大于枢轴的记录均移动至该记录之
23、后。致使一趟排序之后，记录的无序序列Rs.t将分割成两部分：Rs.i-1和Ri+1.t，且Rj.keyRi.keyRj.key(sji-1)枢轴(i+1jt)。第52页/共165页stlowhigh设Rs=52为枢轴将Rhigh.key和枢轴的关键字进行比较，要求Rhigh.key枢轴的关键字将Rlow.key和枢轴的关键字进行比较，要求Rlow.key枢轴的关键字high23low80high14low52例如R052lowhighhighhighlow第53页/共165页可见，经过“一次划分”，将关键字序列52,49,80,36,14,58,61,97,23,75调整为:23,49,14,
24、36,(52)58,61,97,80,75在调整过程中，设立了两个指针：low和high，它们的初值分别为：s和t，之后逐渐减小high，增加low，并保证Rhigh.key52，和Rlow.key52,否则进行记录的“交换”。第54页/共165页intPartition(SqList&L,intlow,inthigh)pivotkey=L.rlow.key;while(lowhigh)while(low=pivotkey)-high;L.rlowL.rhigh;/将比枢轴记录小的记录交换到低端while(lowhigh&L.rlow.key=pivotkey)+low;L.rlowL.rhi
25、gh;/将比枢轴记录大的记录交换到高端returnlow;/返回枢轴所在位置/Partition第55页/共165页intPartition(SqList&L,intlow,inthigh)/PartitionL.r0=L.rlow;pivotkey=L.rlow.key;/枢轴while(lowhigh)while(low=pivotkey)-high;/从右向左搜索L.rlow=L.rhigh;/将比枢轴记录小的记录移动到低端while(lowhigh&L.rlow.key=pivotkey)+low;/从左向右搜索L.rhigh=L.rlow;/将比枢轴记录大的记录移动到高端L.rlow
26、=L.r0;returnlow;第56页/共165页二、快速排序首先对无序的记录序列进行“一次划分”，之后分别对分割所得两个子序列“递归”进行快速排序。无序的记录序列无序记录子序列(1)无序子序列(2)枢轴一次划分分别进行快速排序第57页/共165页voidQSort(SqList&L,intlow,inthigh)/对记录序列L.rlow.high进行快速排序if(lowhigh)/QSortpivotloc=Partition(L,low,high);/对L.rlow.high进行一次划分QSort(L,low,pivotloc-1);/对低子序列递归排序，pivotloc是枢轴位置QSo
27、rt(L,pivotloc+1,high);/对高子序列递归排序第58页/共165页voidQuickSort(SqList&L)/对顺序表进行快速排序QSort(L,1,L.length);/QuickSort第一次调用函数Qsort时，待排序记录序列的上、下界分别为1和L.length。第59页/共165页2 2、最好情况是每次所取的基准都是当前无序区的、最好情况是每次所取的基准都是当前无序区的“中值中值”记录，划分的结果是基记录，划分的结果是基准的左右两个无序子区的长度大致相等。准的左右两个无序子区的长度大致相等。考虑关键字的比较次数和对象移动次数考虑关键字的比较次数和对象移动次数1 1
28、、最坏情况是每次划分选取的基准都是当前无序区中关键字最小（或最大）的、最坏情况是每次划分选取的基准都是当前无序区中关键字最小（或最大）的记录，划分的结果是基准的左边（或右边）为空，划分前后无序区的元素个数减记录，划分的结果是基准的左边（或右边）为空，划分前后无序区的元素个数减少一个，因此，排序必须做少一个，因此，排序必须做n-1n-1趟，每一趟中需做趟，每一趟中需做n-in-i次比较，所以最大比较次数次比较，所以最大比较次数为为三、快速排序的时间分析第60页/共165页 设设C(n)C(n)表示对长度为表示对长度为n n的序列进行快速排序所需的比较次数，显然，它应的序列进行快速排序所需的比较次
29、数，显然，它应该等于对长度为该等于对长度为n n的无序区进行划分所需的比较次数的无序区进行划分所需的比较次数n-1n-1，加上递归地对划分所，加上递归地对划分所得的左右两个无序子区进行快速排序所需的比较次数。假设文件长度得的左右两个无序子区进行快速排序所需的比较次数。假设文件长度n=2n=2k k ，k=logk=log2 2n n，因此有：，因此有：第61页/共165页 快速排序的记录移动次数不会大于比较次数，所以，快速排序的最坏时间复杂度为O(n2)；最好时间复杂度为O(nlog2n)。可以证明，快速排序的平均时间复杂度也是O(nlog2n)。快速排序是不稳定的排序方法。空间复杂度：需栈空
30、间以实现递归最坏情况：S(n)=O(n)一般情况：S(n)=O(log2n)第62页/共165页若待排记录的初始状态为按关键字有序时，快速排序将蜕化为起泡排序，其时间复杂度为O(n2)。为避免出现这种情况，需在进行一次划分之前，进行“予处理”，即：先对R(s).key,R(t).key和R(s+t)/2.key，进行相互比较，然后取关键字为“三者之中”的记录为枢轴记录。第63页/共165页归并排序的过程基于下列基本思想进行：将两个或两个以上的有序子序列“归并”为一个有序序列。2、归并排序第64页/共165页在内部排序中，通常采用的是2-路归并排序。即：将两个位置相邻的记录有序子序列归并为一个记
31、录的有序序列。有序序列Rl.n有序子序列Rl.m有序子序列Rm+1.n这个操作对顺序表而言，是轻而易举的。第65页/共165页voidMerge(RcdTypeSR,RcdType&TR,inti,intm,intn)/将有序的记录序列SRi.m和SRm+1.n/归并为有序的记录序列TRi.nfor(j=m+1,k=i;i=m&j=n;+k)/将SR中记录由小到大地并入TRif(LQ(SRi.key,SRj.key)TRk=SRi+;elseTRk=SRj+;第66页/共165页if(i=m)TRk.n=SRi.m;/将剩余的SRi.m复制到TRif(j=n)TRk.n=SRj.n;/将剩余的
32、SRj.n复制到TR/Merge第67页/共165页归并排序的算法如果记录无序序列Rs.t的两部分Rs.(s+t)/2和R(s+t)/2+1.t分别按关键字有序，则利用上述归并算法很容易将它们归并成整个记录序列是一个有序序列。由此，应该先分别对这两部分进行2-路归并排序。第68页/共165页例如：52,23,80,36,68,14(s=1,t=6)52,23,8036,68,1452,23805223,5223,52,8036,6814366836,6814,36,6814,23,36,52,68,8023第69页/共165页voidMsort(RcdTypeSR,RcdType&TR1,in
33、ts,intt)/将SRs.t归并排序为TR1s.tif(s=t)TR1s=SRs;elsem=(s+t)/2;/将SRs.t平分为SRs.m和SRm+1.t Msort(SR,TR2,s,m);/递归地将SRs.m归并为有序的TR2s.m Msort(SR,TR2,m+1,t);/递归地SRm+1.t归并为有序的TR2m+1.t Merge(TR2,TR1,s,m,t);/将TR2s.m和TR2m+1.t归并到TR1s.t/Msort第70页/共165页voidMergeSort(SqList&L)/对顺序表L作2-路归并排序MSort(L.r,L.r,1,L.length);/MergeS
34、ort以上是递归的算法，下面介绍递推过程的算法第71页/共165页归并算法MERGE(rectypr R,rectype R1,int low,int mid,int high)int i,j,k;i=low;j=mid+1;k=low;while(i=mid)&(j=high)if(Ri.key=Rj.key)R1k+=Ri+;else R1k+=Rj+;while(j=mid)R1k+=Ri+;while(j=high)R1k+=Rj+;第72页/共165页 归并排序就是利用上述归并操作实现排序的。其基本思想是：将待排序列R0到Rn-1看成n个长度为1的有序子序列，把这些子序列两两归并，便
35、得到high(n/2)个有序的子序列。然后再把这high(n/2)个有序的子序列两两归并，如此反复，直到最后得到一个长度为n的有序序列。上述每次的归并操作，都是将两个子序列归并为一个子序列，这就是“二路归并”，类似地还可以有“三路归并”或“多路归并”。第73页/共165页归并过程示例(25)(57)(48)(37)(12)(92)(86)(25 57)(37 48)(12 92)(86)(25 37 48 57)(12 86 92)(12 25 37 48 57 86 92)第74页/共165页一趟归并算法MERGEPASS(rectype R,rectype R1,int length)in
36、t i,j;i=0;while(i+2*length-1n)MERGE(R,R1,i,i+length-1,i+2*length-1);i=i+2*length;if(i+length-1n-1)MERGE(R,R1,i,i+length-1,n-1);else for(j=i;jn;j+)R1j=Rj;第75页/共165页归并排序算法MERGESORT(rectype R)int length=1;while(lengthn)MERGEPASS(R,R1,length);length=2*length;MERGEPASS(R1,R,length);length=2*length;第76页/共
37、165页算法复杂性分析算法复杂性分析 归并排序是稳定的排序方法。归并排序是稳定的排序方法。归并排序是稳定的排序方法。归并排序是稳定的排序方法。归并排序在第i 趟归并后，有序子文件长度为2i，因此，因此，对于具有n个记录的序列来说，必须做high(log2n)趟归并，每趟归并所花的时间为O(n)。所以，二路归并排序算法的时间复杂度为O(nlog2n)，辅助数组所需的空间为O(n)。第77页/共165页本节结束第78页/共165页第五十讲数据结构主讲：刘立嘉选择排序第79页/共165页假设排序过程中，待排记录序列的状态为：有序序列R1.i-1无序序列Ri.n第i趟简单选择排序从中选出关键字最小的记
38、录有序序列R1.i无序序列Ri+1.n1、简单选择排序/直接选择排序第80页/共165页简单选择排序的算法描述如下：voidSelectSort(SqList&L)/对记录序列作简单选择排序。for(i=1;i=low(n/2)的结点都是叶子，因此以这些结点为根的子树都已是堆。这样，我们只需依次将序号为low(n/2)，low(n/2)-1，.，1的结点作为根的子树都调整为堆即可。我们以大根堆为例进行说明第89页/共165页 若已知结点Ri的左右子树已是堆，如何将以Ri为根的完全二叉树也调整为堆？解决这一问题可采用“筛选法”，其基本思想是：因为Ri的左右子树已是堆，这两棵子树的根分别是各自子树
39、中关键字最大的结点，所以我们必须在Ri和它的左右孩子中选取关键字最大的结点放到Ri的位置上。若Ri的关键字已是三者中的最大者，则无须做任何调整，以Ri为根的子树已构成堆，否则必须将Ri和具有最大关键字的左孩子R2i或右孩子R2i+1进行交换。假定R2i的关键字最大，将Ri和R2i交换位置，交换之后有可能导致R2i为根的子树不再是堆，但由于R2i的左右子树仍然是堆，于是可以重复上述过程，将以R2i为根的子树调整为堆，.，如此逐层递推下去，最多可能调整到树叶。第90页/共165页例子：关键字序列为 42，13，91，23，24，16，05，88，n=8，故从第四个结点开始调整42139123241
40、605884213912324160588第91页/共165页42139188241605234213918824160523不调整第92页/共165页42139188241605234213918824160523第93页/共165页42889123241605134288912324160513第94页/共165页91884223241605139188422324160513建成的堆第95页/共165页筛选算法SIFT(rectype R,int i;int m)int j;rectype temp;temp=Ri;j=2*i;while(j=m)if(jm)&(Rj.keyRj+1.k
41、ey)j+;if(temp.key=1;i-)SIFT(R,i,n)由于建堆的结果把关键字最大的记录选到了堆顶的位置，而排序的结果应是升序，所以，应该将R1和Rn交换，这就得到了第一趟排序的结果。第二趟排序的操作首先是将无序区R1到Rn-1调整为堆。这时对于当前堆来说，它的左右子树仍然是堆，所以，可以调用SIFT函数将R1到Rn-1调整为大根堆，选出最大关键字放入堆顶，然后将堆顶与当前无序区的最后一个记录Rn-1交换，如此反复进行下去。第97页/共165页91884223241605139188422324160513（a）初始堆R1到R8第98页/共165页13884223241605911
42、388422324160591（b）第一趟排序之后第99页/共165页（c）重建的堆R1到R788244223131605918824422313160591第100页/共165页05244223131688910524422313168891（d）第二趟排序之后第101页/共165页（e）重建的堆R1到R642241623130588914224162313058891第102页/共165页（f）第三趟排序之后05241623134288910524162313428891第103页/共165页（g）重建的堆R1到R524231605134288912423160513428891第104页
43、/共165页（h）第四趟排序之后13231605244288911323160524428891第105页/共165页（i）重建的堆R1到R423131605244288912313160524428891第106页/共165页（j）第五趟排序之后05131623244288910513162324428891第107页/共165页（k）重建的堆R1到R316130523244288911613052324428891第108页/共165页（l）第六趟排序之后05131623244288910513162324428891第109页/共165页（m）重建的堆R1到R21305162324428
44、8911305162324428891第110页/共165页（n）第七趟排序之后05131623244288910513162324428891第111页/共165页堆排序算法HEAPSORT(rectype R)int i;rectype temp;for(i=n/2;i=1;i-)SIFT(R,i,n);for(i=n;i=1;i-)temp=R1;R1=Ri;Ri=temp;SIFT(R,1,i-1);第112页/共165页堆排序的时间复杂度分析：1.对深度为k的堆，“筛选”所需进行的关键字比较的次数至多为2(k-1)；3.调整“堆顶”n-1次，总共进行的关键字比较的次数不超过2(log
45、2(n-1)+log2(n-2)+log22)2n(log2n)因此，堆排序的时间复杂度为O(nlogn)。2.对 n个关键字，建成深度为h(=log2n+1)的堆，所需进行的关键字比较的次数至多4n；第113页/共165页堆排序的空间复杂性为堆排序的空间复杂性为堆排序的空间复杂性为堆排序的空间复杂性为 O(1)O(1)堆排序是不稳定的排序方法。堆排序是不稳定的排序方法。堆排序是不稳定的排序方法。堆排序是不稳定的排序方法。优点：对小文件效果不明显，但对大文件有效。第114页/共165页本节结束第115页/共165页第五十一讲数据结构主讲：刘立嘉基数排序第116页/共165页基数排序采用“分配”
46、和“收集”的办法，是一种借助“多关键字排序”的思想来实现“单关键字排序”的内部排序算法。u多关键字的排序u链式基数排序1、基数排序第117页/共165页一、多关键字的排序多关键字排序方法示例 如对扑克牌的排序 每张扑克牌有两个“关键字”：花色和面值它们之间有次序的优先。对以上排序，可以先对花色排序，或先对面值排序。第118页/共165页多关键字有序的概念多关键字有序的概念 考虑对象序列考虑对象序列考虑对象序列考虑对象序列VV0 0,V,V1 1,.,V,.,Vn-1n-1，每个对象，每个对象，每个对象，每个对象V Vi i含含含含d d个关键字个关键字个关键字个关键字(K(Ki i1 1,K,
47、Ki i2 2,.,K,.,Ki id d)。若对序列中的任意两个对象若对序列中的任意两个对象若对序列中的任意两个对象若对序列中的任意两个对象ViVi和和和和VjVj都有都有都有都有 (K(Ki i1 1,K,Ki i2 2,.,K,.,Ki id d)(K)=0;j-)for(i=0;im;i+)Bi.f=-1;Bi.e=-1;while(p!=-1)k=Rp.keyj;if(Bk.f=-1)Bk.f=p;else RBk.e.next=p;Bk.e=p;p=Rp.next;i=0;while(Bi.f=-1)i+;t=Bi.e;p=Bi.f;while(im-1)i+;if(Bi.f!=-
48、1)Rt.next=Bi.f;t=Bi.e;Rt.next=-1;return p;int RADIXSORT (rectype R)int i,j,k,t,p;for(i=0;in-1;i+)Ri.next=i+1;Rn-1.next=-1;p=0;第133页/共165页注意：“分配”和“收集”的实际操作仅为修改链表中的指针和设置队列的头、尾指针；为查找使用，该链表尚需应用算法Arrange将它调整为有序表。第134页/共165页n算法评价n特点：不用比较和移动，改用分配和收集，时间效率高！n时间复杂度：n分配：T(n)=O(n)n收集：T(n)=O(rd)T(n)=O(d(n+rd)其中：
49、n记录数d关键字数rd关键字取值范围n空间复杂度：S(n)=2rd个队列指针+n个指针域空间n稳定性：稳定。(一直前后有序)。第135页/共165页一、时间性能1.平均的时间性能基数排序时间复杂度为O(nlogn)：快速排序、堆排序和归并排序时间复杂度为 O(n2)：直接插入排序、起泡排序和简单选择排序时间复杂度为O(n):2、各种排序方法的综合比较第136页/共165页2.当待排记录序列按关键字顺序有序时3.简单选择排序、堆排序和归并排序的时间性能不随记录序列中关键字的分布而改变。直接插入排序和起泡排序能达到O(n)的时间复杂度，快速排序的时间性能蜕化为O(n2)。第137页/共165页二、
50、空间性能指的是排序过程中所需的辅助空间大小1.所有的简单排序方法(包括：直接插入、起泡和简单选择)和堆排序的空间复杂度为O(1)；2.快速排序为O(logn)，为递归程序执行过程中，栈所需的辅助空间；第138页/共165页3.归并排序所需辅助空间最多，其空间复杂度为O(n);4.链式基数排序需附设队列首尾指针，则空间复杂度为O(rd)。第139页/共165页三、排序方法的稳定性能1.稳定的排序方法指的是，对于两个关键字相等的记录，它们在序列中的相对位置，在排序之前和经过排序之后，没有改变。2.当对多关键字的记录序列进行LSD方法排序时，必须采用稳定的排序方法。排序之前:Ri(K)Rj(K)排序