数据结构第10章内部排序

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,*,数据结构课程的内容,1,10.1,概述,10.2,插入排序,10.3,交换排序,10.4,选择排序,10.5,归并排序,10.6,基数排序,第10章 内部排序,2,10.1 概述,1. 什么是排序？,将一组杂乱无章的,数据,按一定的,规律,顺次排列起来。,2. 排序的目的是什么？,存放在数据表中,按关键字排序,3.排序算法的好坏如何衡量？,时间效率,排序速度,(,即排序所花费的全部比较次数,),空间效率,占内存辅助空间的大小,稳定性,若两个记录,A,和,B,的关键字值相等，但排序后,A,、,B,的先后次序保持不变，则称这种排序算法是稳定的。,便于查找！,3,4. 什么叫内部排序？什么叫外部排序？,若待排序记录都在内存中，称为内部排序；,若待排序记录一部分在内存，一部分在外存，则称为外部排序。,注：,外部排序时，要将数据分批调入内存来排序，中间结果还要及时放入外存，显然外部排序要复杂得多。,5.待排序记录在内存中怎样存储和处理？,顺序,排序排序时直接移动记录；,链表,排序排序时只移动指针；,地址,排序排序时先移动地址，最后再移动记录。,注：,地址排序,中可以增设一维数组来专门存放记录的地址。,4,注：,大多数排序算法都是针对顺序表结构的(便于直接移动元素),6. 顺序存储（顺序表）的抽象数据类型如何表示？,Typedef struct ,/定义每个记录（数据元素）的结构,KeyType key ;,/关键字,InfoType otherinfo;,/其它数据项,RecordType ;,# define MAXSIZE 20,/设记录不超过20个,typedef int KeyType ;,/设关键字为整型量（int型）,Typedef struct ,/定义顺序表的结构,RecordType r MAXSIZE +1 ;,/存储顺序表的向量，r0一般作哨兵或缓冲区,int length ;,/顺序表的长度,SqList ;,5,7. 内部排序的算法有哪些？,按排序的规则不同，可分为5类：,插入排序,交换排序（重点是快速排序）,选择排序,归并排序,基数排序,d关键字的位数(长度),按排序算法的时间复杂度不同，可分为3类：,简单的排序算法：时间效率低，,O(n,2,),先进的排序算法,:,时间效率高，,O( nlog,2,n ),基数排序算算法：时间效率高，,O( dn),6,10.2 插入排序,插入排序的基本思想是：,每步将一个待排序的对象，按其关键字大小，,插入到前面,已经排好序的一组对象,的,适当位置,上,，直到对象全部插入为止。,插入排序的基本操作：,将记录Ri插入到有序子序列R1.i-1中，使记录的有序序列从R1.i-1变为R1.i。,显然，完成这个“插入”需分三步进行：,1查找Ri的插入位置j+1；,2将Rj+1,.i-1,中的记录后移一个位置；,3将Ri复制到Rj+1的位置上。,7,10.2 插入排序,插入排序有多种具体实现算法：,1),直接插入排序,2),折半插入排序,3),表插入排序,4),希尔排序,简言之，边插入边排序，保证子序列中随时都是排好序的。,8,1) 直接插入排序,新元素插入到哪里？,例1：,关键字序列T=(13，6，3，31，9，27，5，11)，请写出直接插入排序的中间过程序列。,【,13,】, 6, 3, 31, 9, 27, 5, 11,【,6, 13,】, 3, 31, 9, 27, 5, 11,【,3, 6, 13,】, 31, 9, 27, 5, 11,【,3, 6, 13，31,】, 9, 27, 5, 11,【,3, 6, 9, 13，31,】, 27, 5, 11,【,3, 6, 9, 13，27, 31,】, 5, 11,【,3, 5, 6, 9, 13，27, 31,】, 11,【,3, 5, 6, 9, 11，13，27, 31,】,在已形成的,有序表中,线性查找,，并在适当位置插入，把原来位置上的元素向后,顺移,。,最简单的排序法！,9,例2：,关键字序列T= （21，25，49，25,*,，16，08），请写出直接插入排序的具体实现过程。,*,表示后一个25,i,=1,21,25,49,25*,16,08,0 1 2 3 4 5 6,暂,存,21,i,=2,i,=3,i,=5,i,=4,i,=6,25,25,25,49,49,49,25*,25*,49,16,16,25*,08,08,49,解：,假设该序列已存入一维数组V7中，将V0作为缓冲或暂存单元（Temp）。则程序执行过程为：,21,25,49,25*,21,初态：,16,49,25*,25,21,16,08,完成!,时间效率：,O(n,2,),因为在最坏情况下，所有元素的比较次数总和为（01n-1)O(n,2,)。其他情况下还要加上移动元素的次数。,空间效率：,O（1）,因为仅占用1个缓冲单元,算法的稳定性：,稳定,因为25*排序后仍然在25的后面。,10,直接插入排序算法的三个要点：,1从Ri-1起向前顺序查找，监视哨设置在R0,R0 = Ri; / 设置“哨兵”,for,(j=i-1; R0.keyRj.key; -j) ; /,从后往前找,return,j+1; /,返回Ri的插入位置为j+1,2,对于在查找过程中找到的关键字不小于Ri.key的记录，在查找的同时实现记录向后移动；,for,(j=i-1; R0.keyRj.key; -j),Rj+1 = Rj,3,i = 2，3，, n, 实现整个序列的排序。,11,直接插入排序算法描述如下:,void InserSort ( SqList &L),/ 对顺序表L作直接插入排序。,for ( i=2; i=L.length; +i ),if (LT(L.ri.key ,L.ri-1.key), L.r0 = L.ri;,/ 复制为监视哨,for ( j=i-1; LT(L.ri.key ,L.ri-1.key) ; -j ),L.rj+1 = L.rj;,/ 记录后移,L.rj+1 = L.r0;,/ 插入到正确位置, / InsertSort,12,若设待排序的对象个数为,n,，,则算法需要进行,n,-1,次插入。,最好情况下，排序前对象已经按关键字大小从小到大有序，每趟只需与前面的有序对象序列的,最后一个对象,的关键字比较,1,次。因此，总的关键字比较次数为,n,-1,。,直接插入排序的算法分析,13,最坏情况下，第,i,趟插入时，第,i,个对象必须与前面,i-1,个对象都做关键字比较，并且每做,1,次比较就要做,1,次数据移动。则总的关键字比较次数,KCN,和对象移动次数,RMN,分别为,14,若待排序对象序列中出现各种可能排列的概率相同，则可取上述最好情况和最坏情况的平均情况。在平均情况下的关键字比较次数和对象移动次数约为,n,2,/4,。,因此，直接插入排序的时间复杂度为,o(,n,2,),。,直接插入排序是一种稳定的排序方法。,15,2） 折半插入排序,优点：,比较的次数大大减少，全部元素比较次数仅为,O(nlog,2,n),。,时间效率：,虽然比较次数大大减少，可惜移动次数并未减少，所以排序效率仍为O(n,2,) 。,空间效率：,O（1）,稳定性：,稳定,当待排序记录的数量n很小时，直接插入排序是一种简便的方法；但当记录数量n很大时，则不宜采用直接插入排序。,由于插入排序的基本操作是在有序表R1.i-1中进行查找和插入的；则可以利用,折半查找实现“在R1.i-1中查找Ri的插入位置”,，,并在适当位置插入，把原来位置上的元素向后,顺移,。,如此实现的插入排序为,折半插入排序,。,16,折半插入排序算法描述如下:,void BInserSort ( SqList &L),/ 对顺序表L作折半插入排序。,for ( i=2; i=L.length; +i ), L.r0 = L.ri;,while(low=high+1; - -j ),L.rj+1 = L.rj;,/ 记录后移,L.rj+1 = L.r0;,/ 插入,/for, / BInsertSort,17,讨论：,若记录是链表结构，用直接插入排序行否？折半插入排序呢？,答：,直接插入不仅可行，而且还无需移动元素，时间效率更高！,折半插入排序的改进2-路插入排序见教材P267。,但链表无法“折半”！,18,折半插入排序的算法分析,折半查找比顺序查找快，所以折半插入排序就平均性能来说比直接插入排序要快。,在插入第,i,个对象时，需要经过,log,2,i,+1,次关键字比较，才能确定它应插入的位置。因此，将,n,个对象用折半插入排序所进行的关键字比较次数为：,n*log,2,n,折半插入排序是一个稳定的排序方法。,19,3）表插入排序,基本思想,：在顺序存储结构中，给每个记录增开一个指针分量，在排序过程中将指针内容逐个修改为已经整理（排序）过的后继记录地址。,优点：,在排序过程中不移动元素，只修改指针。,回忆：, 链表排序排序时只移动指针；, 地址排序排序时先移动地址，最后再移动记录。,此方法具有链表排序和地址排序的特点。,20,1,例：,关键字序列 T=(21，25，49，25,*,，16，08)， 请写出表插入排序的具体实现过程。,解：,假设该序列（结构类型)已存入有序链表SL7中，将SL0作为表头结点。则,算法执行过程,为：,i,关键字 SL,i.key,指针 SL,i.next,0,MaxInt,1,21,2,25,3,49,4,25*,5,16,6,08,指向第1个元素,指向头结点,初态,i=1,i=2,i=3,i=4,i=5,i=6,0,3,4,5,6,5,0,3,1,0,2,*,表示后一个25,静态链表,21,表插入排序算法分析：, 无需移动记录，只需修改2n次指针值。但由于比较次数没有减少，故,时间效率仍为O(n,2,),。,空间效率肯定低,，因为增开了指针分量（但在运算过程中没有用到更多的辅助单元）。, 稳定性：25和25*排序前后次序未变，,稳定,。,讨论：,此算法得到的只是一个有序链表，查找记录时只能满足顺序查找方式。,改进：,可以根据表中指针线索，很快对所有记录重排，形成,真正的有序表（顺序存储方式），从而能满足折半查找方式。,具体实现见教材P269。,22,4）希尔（shell）排序,（又称缩小增量排序,）,基本思想,：,先将整个待排记录序列分割成若干子序列,分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行一次直接插入排序。,技巧：,子序列的构成不是简单地“逐段分割”，而是将相隔某个增量dk的记录组成一个子序列,让增量dk逐趟缩短（例如依次取5,3,1），直到dk1为止。,优点：,让关键字值小的元素能很快前移，且序列若基本有序时，再用直接插入排序处理，时间效率会高很多。,23,38,例：,关键字序列 T=(49，38，65，97, 76, 13, 27, 49,*,，55, 04），请写出希尔排序的具体实现过程。,0,1,2,3,4,5,6,7,8,9,10,49,38,65,97,76,13,27,49,*,55,04,初态：,第1趟 (dk=5),第2趟 (dk=3),第3趟 (dk=1),49,13,13,49,38,27,65,49,*,97,55,76,04,27,38,65,49*,97,55,13,55,76,04,55,13,27,04,27,04,49,49*,49,49*,76,38,76,65,65,97,97,55,13,27,04,49,49*,38,76,65,97,13,27,04,49*,76,97,算法分析：,开始时,dk,的值较大，子序列中的对象较少，排序速度较快；随着排序进展，,dk,值逐渐变小，子序列中对象个数逐渐变多，由于前面工作的基础，大多数对象已基本有序，所以排序速度仍然很快。,ri,问题,：第三趟(dk=1)的排序过程与在初态序列上直接进行dk=1排序是否相同？,24,void ShellSort(SqList &L，int dlta ，int,t,),/按增量序列dlta0,t-1,对顺序表L作Shell排序,for(k=0；k,t,；+k),ShellInsert(L，dltak)；,/增量为dltak的一趟插入排序,/ ShellSort,时间效率：,空间效率：,O（1,）,因为仅占用1个缓冲单元,算法的稳定性：,不稳定,因为49,*,排序后却到了49的前面,希尔排序算法,（主程序）,参见教材P272,O(,n,1.3,）,经验公式,dk值依次装在dlta,t,中,25,void ShellInsert(SqList &L，,int,dk,),for,(i=dk+1;i=L.length; + i),if(L.ri.key,0&(L,.r0.key,L,.rj.key); j=j-dk),L. rj+dk=L.rj；,L,.rj+dk=L.r0；,希尔排序算法,（其中某一趟的排序操作）,参见教材P272,/对顺序表L进行一趟增量为,dk,的Shell排序，,dk,为步长因子,/开始将ri 插入有序增量子表,/暂存在r0,/关键字较大的记录在子表中后移,/在本趟结束时将ri插入到正确位置,26,课堂练习：,1.,欲将序列（Q, H, C, Y, P, A, M, S, R, D, F, X）中的关键字按字母升序重排，则初始步长为4的希尔排序一趟的结果是？,答：,原始序列：,Q,H,C,Y,P,A,M,S,R,D,F,X,shell一趟后：,P,Q,R,A,D,H,C,F,M,S,X ,Y,27,2.,以关键字序列（256，301，751，129，937，863，742，694，076，438）为例，分别写出执行以下算法的,各趟,排序结束时，关键字序列的状态，并说明这些排序方法中，哪些易于在链表（包括各种单、双、循环链表）上实现？, 直接插入排序 希尔排序（取dk=5,3,1）,答：,显然，直接插入排序方法易于在链表上实现；但希尔排序方法因为是按增量选择记录，不易于在链表上实现。,两种排序方法的中间状态分别描述如后：,28,原始序列：,256，301，751，129，937，863，742，694，076，438,256，301,，751，129，937，863，742，694，076，438,256，301，751,，129，937，863，742，694，076，438,129,，256，301，751,，937，863，742，694，076，438,129，,256，301，751，937,，863，742，694，076，438,129，,256，301，751，,863，,937,，742，694，076，438,129，,256，301，,742，,751，,863，,937,，694，076，438,129，,256，301，,694，742，,751，,863，,937,，076，438,076，129，,256，301，,694，742，,751，,863，,937,，438,076，129，,256，301，,438，694，742，,751，,863，,937,直接插入排序,第1趟,第2趟,第3趟,第4趟,第5趟,第6趟,第7趟,第8趟,第9趟,29,原始序列：,256，301，751，129，937，863，742，694，076，438,希尔排序,(取dk=5,3,1),256，,301，751，129，937，,863，,742，694，076，438,256，301，,751，129，937，,863，742，,694，076，438,256，301，,694，,129，937，,863，742，,751，,076，438,256，301，,694，076，,937，,863，742，,751，129，,438,256，301，,694，076，438，,863，742，,751，129，937,第1趟,dk=5,第2趟,dk=3,第3趟,dk=1,256，301，694，076，438，863，742，751，129，937,256，,301，694，,076，,438，863，,742，,751，129，,937,076，,301，694，,256，,438，863，,742，,751，129，,937,076，,301，,694，,256，,438，,863，,742，,751，,129，,937,076，,301，,694，,256，,438，,863，,742，751，,129，,937,076，,301，,129，,256，,438，,694，,742，751，,863，,937,076，301，129，256，438，694，742，751，863，937,076，301，129，256，438，694，742，751，863，937,076，,129，,256，,301，,438，694，742，751，863，937,30,10.3 快速排序,两两比较待排序记录的关键字，如果发生逆序（即排列顺序与排序后的次序正好相反），则交换之，直到所有记录都排好序为止。,快速排序的主要算法有：,1),冒泡排序,2),快速排序,快速排序的基本思想是：,31,1),冒泡排序,基本思路：,每趟不断将记录两两比较，并按“前小后大”（或“前大后小”）规则交换。,优点：,每趟结束时，不仅能挤出一个最大值到最后面位置，还能同时部分理顺其他元素；一旦下趟没有交换发生，还可以提前结束排序。,前提：,顺序存储结构,例：,关键字序列 T=(21，25，49，25,*,，16，08），请写出冒泡排序的具体实现过程。(假设“,前小后大,”),21，25，49， 25,*,，16， 08,21，25，,25*，16， 08 ，,49,21，25，,16， 08 ，,25*，49,21，,16， 08 ，,25，,25*，49,16，08 ，,21，,25，,25*，49,08，,16，,21，,25，,25*，49,初态：,第1趟,第2趟,第3趟,第4趟,第5趟,32,冒泡排序的算法分析,时间效率：,O（n,2,),因为要考虑最坏情况,空间效率：,O（1）,只在交换时用到一个缓冲单元,稳 定 性：,稳定,25和25,*,在排序前后的次序未改变,详细分析：,最好情况：,初始排列已经有序，只执行一趟起泡，做,n,-,1,次关键字比较，不移动对象。,最坏情形：,初始排列逆序，,算法要执行,n,-,1,趟起泡，第,i,趟,(1,i,n,),做了,n- i,次关键字比较，执行了,n-i,次对象交换。此时的比较总次数,KCN,和记录移动次数,RMN,为：,33,2） 快速排序,从待排序列中任取一个元素 (例如取第一个) 作为中心，所有比它小的元素一律前放，所有比它大的元素一律后放，形成左右两个子表；然后再对各子表重新选择中心元素并依此规则调整，直到每个子表的元素只剩一个。此时便为有序序列了。,基本思想：,优点：,因为每趟可以确定不止一个元素的位置，而且呈指数增加，所以特别快！,前提：,顺序存储结构,34,( ),，,设以首元素为枢轴中心,例1：,关键字序列 T=(21，25，49，25,*,，16，08），请写出快速排序的算法步骤。,21,， 25， 49， 25,*,，16， 08,初态：,第1趟：,第2趟：,第3趟：,讨论：,1. 这种不断划分子表的过程，计算机如何自动实现？,2. “快速排序”是否真的比任何排序算法都快？,08，,16，,21，,25，,25*，,(,49,),21,16，08,，,( ),25，25*，49,(,08,),，,16，,21，,25，,(,25*，49,),35,1.这种不断划分子表的过程，计算机如何自动实现？,编程时：,每一趟的子表的形成是采用从两头向中间交替式逼近法;,由于每趟中对各子表的操作都相似，主程序可采用递归算法。,见教材P275,int,Partition,(SqList &L,int low,int high,),/交换顺序表 L.rlowhigh的记录，使枢轴记录到位，并返回其位置。返回时，在枢轴之前的记录均不大于它，枢轴之后的记录均不小于它。,pivotkey=L.,rlow.key,;,/取枢轴的关键字存入pivotkey变量,（续下页）,一趟快速排序算法,（针对一个子表的操作）,36,while(low high),/从表的两端交替地向中间扫描,while(,low=pivotkey,),- -high;,L.rlow,L.rhigh;,/将比枢轴小的记录交换到低端,while(,lowhigh,& L.,rlow.key=pivotkey,),+ +low;,L.rhigh,L.rlow;,/将比枢轴大的记录交换到高端,return low;,/返回枢轴记录所在位置。,/,Partition,37,Low=high=,3,，,本趟停止，将支点定位并返回位置信息,例2：,关键字序列 T=(21，25，49，25,*,，16，08），请写出快速排序算法的一趟实现过程。,ri,0,1,2,3,4,5,6,初态,21,25,49,25,*,16,08,第1趟,high,low,21,08,25,16,49,25,*,3,21,pivotkey=,21,08,25,16,49,( 08,，16 ）,21,（ 25,*,， 49， 25 ）,25,*,跑到了前面，,不稳定,！,38,j从高端,扫描,寻找小于pivot的元素,i从低端,扫描,寻找大于pivot的元素,i=low; j=high;r0=rlow; pivot=rlow.key;,i j,i =pivot,-j;,ri = rj;,i j,&,ri.key=pivot,-i;,rj = ri;,ri = r0;,return ok,;,Y,Y,Y,N,N,N,一趟快速排序算法流程图,39,void,QSort,(,SqList,&L,int,low, int,high,) ,if (,low,1,/对顺序表L中的子序列r,low,high,作快速排序,/QSort,void,Q,uick,Sort,(,SqList,&L) ,QSort,(L,1, L.length,);,对顺序表L进行快速排序的操作函数为：,40,例3：,以关键字序列（256，301，751，129，937，863，742，694，076，438）为例，写出执行快速算法的,各趟,排序结束时，关键字序列的状态。,原始序列：,256，301，751，129，937，863，742，694，076，438,快速排序,第1趟,第2趟,第3趟,第4趟,256，301，751，129，937，863，742，694，076，438,076,，,129,，,256,，,751,，937，863，742，694，301，438,要求模拟算法实现步骤,256,076,301,129,751,256,076,，,129,，,256,，,438,，,301,，,694,，742，694，,863,，,937,751,076,，,129,，,256,，,438,，301，694，742，,751,，,863,，937,076,，,129,，,256,，,301,，301，694，742，,751,，,863,，937,438,076,，,129,，,256,，,301,，,438,，,694,，742，,751,，,863,，,937,时间效率：,O(nlog,2,n),因为每趟确定的元素呈指数增加,空间效率：,O（,log,2,n,）,因为算法的递归性，要用到栈空间,稳 定 性：,不稳定,因为可选任一元素为枢轴。,41,快速排序算法详细分析：,快速排序是递归的，需要有一个栈存放每层递归调用时的指针和参数,（新的,low,和,high,）,。,可以证明，函数,quicksort,的平均计算时间也是,O(,n,log,2,n,),。,实验结果表明：就平均计算时间而言，快速排序是我们所讨论的所有内排序方法中最好的一个,。,最大递归调用层次数与递归树的深度一致，理想情况为,log,2,(,n,+1),。,因此，要求存储开销为,o(log,2,n,),。,42,如果每次划分对一个对象定位后，该对象的左侧子序列与右侧子序列的长度相同，则下一步将是对两个长度减半的子序列进行排序，这是最理想的情况。此时，快速排序的趟数最少。,43,在最坏的情况，即待排序对象序列已经按其关键字从小到大排好序的情况下，,其递归树成为单支树,，每次划分只得到一个比上一次少一个对象的子序列。这样，必须经过,n,-1,趟才能把所有对象定位，而且第,i,趟需要经过,n,-,i,次关键字比较才能找到第,i,个对象的安放位置，总的关键字比较次数将达到,n,2,/2,快速排序是一个,不稳定,的排序方法,44,讨论2. “快速排序”是否真的比任何排序算法都快？,设每个子表的支点都在中间（比较均衡），则：,第1趟比较，可以确定,1,个元素的位置；,第2趟比较（2个子表），可以再确定,2,个元素的位置；,第3趟比较（4个子表），可以再确定,4,个元素的位置；,第4趟比较（8个子表），可以再确定,8,个元素的位置；,只需,log,2,n,1,趟便可排好序。,基本上是！因为每趟可以确定的数据元素是呈,指数增加的！,45,而且，每趟需要比较和移动的元素也呈指数下降，加上编程时使用了交替逼近技巧，更进一步减少了移动次数，所以速度特别快。,教材P276有证明：快速排序的平均排序效率为O(nlog,2,n)；,但最坏情况(例如已经有序)下仍为O(n,2,),改进措施见P277,。,46,选择排序的基本思想是：每一趟 (例如第,i,趟，,i,= 1, ,n,-,1) 在后面的,n,-,i+1,个待排序对象中选出关键字最小的对象, 作为有序对象序列的第,i,个对象。待到第,n,-,1 趟作完，待排序对象只剩下1个，就不用再选了。,10.4选择排序,(Selection Sort),10.4.1,简单选,择排序,10.4.2,树形选择排序,10.4.3,堆排序,47,10.4.1 简单选,择排序,Simple Selection Sort,基本步骤为：i从1开始，直到n-1，进行n-1趟排序，第i 趟的排序过程为： 在一组对象rirn (i=1,2,n-1)中选择具有最小关键字的对象；并和第 i 个对象进行交换；,48,简单选择排序的算法,void SelectSort(SqList &L), for (int i=1; iL.length;+i),j=SelectMinKey(L,i);,/在L.ri.L.length中选择key最小的记录,if (i!=j),L.ri,L.rj;/与第i个记录交换,49,21,25,49,25*,16,08,0 1 2 3 4 5,21,25*,i,= 1,49,25,16,25,16,08,49,08,25*,49,21,i,= 2,i,= 3,08,16,25*,25,21,初始,最小者,08,交换,21,08,最小者,16,交换25,16,最小者,21,交换49,21,50,49,25*,0 1 2 3 4 5,25*,i,= 5,25,16,08,49,25*,49,21,结果,i,= 4,08,16,25,21,最小者,25*,无交换,最小者,25,无交换,25,21,16,08,各趟排序后的结果,51,算法分析,直接选择排序的关键字比较次数,KCN,与对象的初始排列无关。第,i,趟选择具有最小关键字对象所需的比较次数总是,n,-,i,-,1 次，此处假定整个待排序对象序列有,n,个对象。因此，总的关键字比较次数为,时间复杂度？,O（n,2,）,52,对象的移动次数与对象序列的初始排列有关。当这组对象的初始状态是按其关键字从小到大有序的时候，对象的移动次数,RMN,= 0，达到最少。,最坏情况是每一趟都要进行交换，总的对象移动次数为,RMN,= 3(,n,-,1)。,直接选择排序是一种,不稳定,的排序方法。,53,10.4.2 树形选择排序(锦标赛排序 ),它的思想与体育比赛时的淘汰赛类似。首先取得,n,个对象的关键字，进行两两比较，得到,n,/2,个比较的优胜者(关键字小者)，作为第一步比较的结果保留下来。然后对这,n,/2,个对象再进行关键字的两两比较，如此重复，直到选出一个关键字最小的对象为止。,在图例中，最下面是对象排列的初始状态，相当于一棵满二叉树的叶结点，它存放的是所有参加排序的对象的关键字。,54,08,Winner,21,08,08,63,25*,21,21,25,49,25*,16,08,63,55,胜者树的概念,每次两两比较的结果是把关键字小者作为优胜者上升到双亲结点，称这种比赛树为胜者树。,胜者树最顶层是树的根，表示最后选择出来的具有最小关键字的对象。,56,08,Winner,(,胜者),21,08,08,63,25*,21,21,25,49,25*,16,08,63,形成初始胜者树（最小关键字上升到根）,a,0,关键字比较次数 : 6,57,16,Winner,(,胜者),21,16,16,63,25*,21,21,25,49,25*,16,63,输出冠军并调整胜者树后树的状态,a,1,关键字比较次数 : 2,58,21,Winner,(,胜者),21,63,63,25*,21,21,25,49,25*,63,输出亚军并调整胜者树后树的状态,a,2,关键字比较次数 : 2,59,25,Winner,(,胜者),25,63,63,25*,25,25,49,25*,63,输出第三名并调整胜者树后树的状态,a,3,关键字比较次数 : 2,60,25*,Winner,(,胜者),25*,63,63,25*,49,25*,63,输出第四名并调整胜者树后树的状态,a,4,关键字比较次数 : 2,61,63,Winner,(,胜者),63,63,63,全部比赛结果输出时树的状态,a,6,关键字比较次数 : 2,62,算法分析,锦标赛排序构成的树是满的完全二叉树，其深度为,log,2,(,n,+1),，其中,n,为待排序元素个数。,除第一次选择具有最小关键字的对象需要进行,n,-1 次关键字比较外，重构胜者树选择具有次小、再次小关键字对象所需的关键字比较次数均为 O(log,2,n,)。总关键字比较次数为O(,n,log,2,n,)。,对象的移动次数不超过关键字的比较次数，所以锦标赛排序总的时间复杂度为O(,n,log,2,n,)。,这种排序方法虽然减少了许多排序时间，但是使用了较多的附加存储。,锦标赛排序是一个稳定的排序方法。,63,10.4.3 堆排序,(Heap Sort),利用堆及其运算，可以很容易地实现选择排序的思路。堆排序分为两个步骤：第一步，根据初始输入数据，利用堆的调整算法,HeapAdjust,( ),形成初始堆，第二步，通过一系列的对象交换和重新调整堆进行排序。,给定一组关键字，初始态存储时是一个完全二叉树,堆的建立,对堆的筛选与建立的重复交替,64,堆排序,(Heap Sort),给定一组关键字，初始态存储时是一个完全二叉树,小顶堆的建立：,对 n/2 1,的元素依次进行筛选：,若k,i,=k,2i,且k,i,k,2i,(k,2i+1,)且k,i,k,2i,且k,i,k,2i+1,，则k,i,与较小的哪个交换,若(k,2i,=k,2i+1,) k,i,则k,i,与k,2i,交换,（大顶堆刚好相反）,对堆的筛选与建立的重复交替,65,建立初始的最大堆,21,25,25*,49,16,08,1,2,3,4,5,6,i,21,25,25*,16,49,08,1,3,6,5,4,2,i,21 25 49 25* 16 08,初始关键字集合,21 25 49 25* 16 08,i,= 3 时的局部调整,66,21,25,25*,49,16,08,1,2,3,4,5,6,i,49,25,25*,16,21,08,1,3,6,5,4,2,21 25 49 25* 16 08,49 25 21 25* 16 08,i,= 1 时的局部调整,形成大顶堆,i,= 2 时的局部调整,67,最大堆的向下调整算法,void HeapAdjust(HeapType &H,int s,int m), ElemType rc=H.rs;,for (int j=2*s;j=m;j*=2),if (j0; -i),HeapAdjust(H,i,H.length);,for (i=H.length; i1; -i),temp=H.r1;,H.r1=H.ri;,H.ri=temp;,HeapAdjust(H,1,i-1);,75,算法分析,若设堆中有,n,个结点，且 2,k,-,1,n,2,k,，则对应的完全二叉树有,k,层。在第,i,层上的结点数,2,i-1,(,i,= 1, ,k,)。在第一个形成初始堆的for循环中对每一个非叶结点调用了一次堆调整算法,HeapAdjust,( )，因此该循环所用的计算时间为：,其中，,i,是层序号，2,i-1,是第,i,层的最大结点数，(,k,-,i,-,1)是第,i,层结点能够移动的最大距离。,76,在第二个for循环中，调用了,n,-,1次,HeapAdjust,( ),算法，该循环的计算时间为O(,n,log,2,n,)。因此，堆排序的时间复杂性为O(,n,log,2,n,)。,该算法的附加存储主要是在第二个for循环中用来执行对象交换时所用的一个临时对象。因此，该算法的空间复杂性为O(1)。,堆排序是一个不稳定的排序方法。,77,10.5 归并排序,基本思想：将一个具有n个待排序记录的序列看成是n个长度为1的有序列，然后进行两两归并，得到n/2,个长度为2的有序序列，再进行两两归并，得到n/4,个长度为4的有序序列，如此重复，直至得到一个长度为n的有序序列为止,78,归并排序示例,二趟归并排序后,：,33 51 62 96, 1,7 28 87,初始关键字序列,：,51,33,62,96,87,17,28,一趟归并排序后,：,33 51,62 96,1,7 87, ,28,三趟归并排序后,：,17 28 33 51 62,87 96,79,归并排序示例,80,算法分析,在归并排序算法中，对象关键字的比较次数为O(,n,log,2,n,)。算法总的时间复杂度为,O(,n,log,2,n,),。,归并排序占用附加存储较多，需要另外一个与原待排序对象数组同样大小的辅助数组。这是这个算法的缺点。,归并排序是一个稳定的排序方法。,81,10.6 基数排序 (Radix Sort),基数排序是采用“,分配,”与“,收集,”的办法，用对多关键字进行排序的思想实现对单关键字进行排序的方法。,10.6.1 多关键字排序,以扑克牌排序为例。每张扑克牌有两个“关键字”：花色和面值。其有序关系为：,花色：,面值：,2 3 4 5 6 7 8 9 10 J Q K A,如果我们把所有扑克牌排成以下次序：,2, ,A,2, ,A,2, ,A,2, ,A,82,这就是,多关键字排序,。排序后形成的有序序列叫做词典有序序列。,对于上例两关键字的排序，可以先按花色排序，之后再按面值排序；也可以先按面值排序，再按花色排序。,一般情况下，假定有一个,n,个对象的序列 ,V,0,V,1, ,V,n,-1,，且每个对象,V,i,中含有,d,个关键字,如果对于序列中任意两个对象,V,i,和,V,j,( 0,i,j,n-,1 ) 都满足：,83,则称序列对关键字,(,K,1,K,2, ,K,d,),有序。其中，,K,1,称为最高位关键字，,K,d,称为最低位关键字。,如果关键字是由多个数据项组成的数据项组，则依据它进行排序时就需要利用多关键字排序。,实现多关键字排序有两种常用的方法,最高位优先,MSD,(,Most Significant Digit first,),最低位优先,LSD,(,Least Significant Digit first,),最高位优先法,通常是一个递归的过程：,先根据,最高位关键字,K,1,排序,得到若干对象组，对象组中每个对象都有相同,关键字,K,1,。,84,再分别对每组中对象根据,关键字,K,2,进行排序，按,K,2,值的不同，再分成若干个更小的子组，每个子组中的对象具有相同的,K,1,和,K,2,值。,依此重复，直到对,关键字,K,d,完成排序为止。,最后，把所有子组中的对象依次连接起来，就得到一个有序的对象序列。,85,最低位优先法,首先依据,最低位关键字,Kd,对所有对象进行一趟排序，再依据,次低位关键字,Kd,-1,对上一趟排序的结果再排序，依次重复，直到依据,关键字,K,1,最后一趟排序完成，就可以得到一个有序的序列。使用这种排序方法对每一个关键字进行排序时，不需要再分组，而是整个对象组都参加排序。,86,LSD和MSD方法也可应用于对一个关键字进行的排序。此时可将,单关键字,K,i,看作是一个子关键字组,：,87,基数排序是典型的LSD排序方法，利用“,分配,”和“,收集,”两种运算对单关键字进行排序。在这种方法中，把,单关键字,K,i,看成是一个,d,元组,：,其中的每一个分量,( 1,j,d,),也可看成是一个关键字。,10.6.2 链式基数排序,88,分量 (1,j,d,) 有,radix,种取值,，则称,radix,为,基数,。例如，关键字984可以看成是一个3元组(9, 8, 4)，每一位有0, 1, , 9等10种取值，基数,radix,= 10,。关键字data,可以看成是一个4元组(d, a, t, a)，每一位有a, b, , z等26种取值，,radix,= 26,。,针对,d,元组中的每一位分量，把对象序列中的所有对象, 按 的取值，先“,分配,”到,rd,个队列中去。然后再按各队列的顺序，依次把对象从队列中“,收集,”起来，这样所有对象按取值 排序完成。,89,如果对于所有对象的关键字,K,0,K,1, ,K,n,-1,，依次对各位的分量，让,j,=,d,d,-,1, , 1,，分别用这种“,分配,”、“收集”的运算逐趟进行排序，在最后一趟“分配”、“,收集,” 完成后，所有对象就按其关键字的值从小到大排好序了。,各队列采用链式队列结构，分配到同一队列的关键字用链接指针链接起来。每一队列设置两 个队列指针：,int,front,radix,指示队头，,int,rear,radix,指向队尾。,90,为了有效地存储和重排,n,个待排序对象，以,静态链表,作为它们的存储结构。在对象重排时不必移动对象，只需修改各对象的链接指针即可。,91,例1,初始状态：,278,109,063,930,589,184,505,269,008,083,109,589,269,278,063,930,083,184,505,008,e0,e1,e2,e3,e4,e5,e6,e7,e8,e9,f0,f1,f2,f3,f4,f5,f6,f7,f8,f9,一趟分配,930,063,083,184,505,278,008,109,589,269,一趟收集：,静态链表,基数排序的“分配”与“收集”过程 第一趟,92,505,008,109,930,063,269,278,083,184,589,二趟收集：,083,184,589,063,505,269,930,e0,e1,e2,e3,e4,e5,e6,e7,e8,e9,f0,f1,f2,f3,f4,f5,f6,f7,f8,f