数据结构 排序 查找 PPT.ppt

2002005 5 -2 2-1 1华中科技大学华中科技大学计算机学院计算机学院(1212)数据结构数据结构10.4 归并归并排序排序 基本思想 把k(k2)个有序子文件合并在一起，形成一个新的有序文件。同时归并k个有序子文件的排序过程称为k-路归并排序。2-2-路归并排序路归并排序-归并2个有序子文件的排序。例.将有序文件A和B归并为有序文件C。A A(2,10,15,18,21,30)B B(5,20,35,40)按从小至大的次序从A或B中依次取出2,5,10,15,.,40,顺序归并到C中,得:C C(2,5,10,15,18,20,21,30,35,40)一般地，2-2-路归并路归并过程为：假定文件rlow.high中的相邻子文件(子表)(rlow,rlow+1,.,rmid)rlow,rlow+1,.,rmid)和(rmid+1,.,rhighrmid+1,.,rhigh)为有序子文件,其中:lowmidhigh。将这两个相邻有序子文件归并为有序文件ylow.high,即：(ylow,ylow+1,.,yhigh)ylow,ylow+1,.,yhigh)06060808151540400707090920202222r9.16 91011121314151606060707080809091515202022224040y9.16 9101112131415162-路归并有序文件有序文件(表表)ijk例有序有序子表子表有序有序子表子表将两个有序子文件归并为有一个有序文件的算法两个有序子文件归并为有一个有序文件的算法void merge(r,y,low,mid,high)RecType r,y；int low,mid,high；int k=i=low,j=mid+1；while(i=mid&j=high)if(ri.key=rj.key)yk=ri；i+；/归并前一个子文件的记录归并前一个子文件的记录 else yk=rj；j+；/归并后一个子文件的记录归并后一个子文件的记录 k+；while(j=high)/归并后一个子文件余下的记录归并后一个子文件余下的记录 yk=rj；j+；k+；while(i=mid)/归并前一个子文件余下的记录归并前一个子文件余下的记录 yk=ri；i+；k+；/merge2-2-路路归并排序排序 假定文件(r1,r2,.,rn)中记录是随机排列的,进行2-路归并排序，首先把它划分为长度均为1的n个有序子文件，然后对它们逐步进行2路归并排序。其步骤如下：第第1 1趟趟：从r1.n中的第1个和第2个有序子文件开始,调用算法merge,每次归并两个相邻子文件,归并结果放到y1.n中。在y中形成 n/2 个长度为2的有序子文件。若n为奇数,则y中最后一个子文件的长度为1。第第2 2趟趟：把y1.n看作输入文件,将 n/2 个有序子文件两两归并,归并结果回送到r1.n中,在r中形成 n/2/2个长度为4的有序子文件。若y中有奇数个子文件，则r中最后一个子文件的长度为2。.共计经过 loglog2 2n n 趟归并,最后得到n个记录的有序文件。例1.对8个记录作2路归并排序,共进行loglog2 28 83 3 趟归并。06 06 44 44 20 20 10 10 02 02 20 20 08 08 07 07r1.06 06 44 44 10 10 20 20 02 02 20 20 07 07 08 08y1.06 06 10 10 20 20 44 44 02 02 07 07 08 08 20 20r1.02 02 06 06 07 07 08 08 10 10 20 20 20 20 44 44y1.第1趟第3趟第2趟例2.对11个记录作2-路归并排序,进行loglog2 211114 4趟归并。06 06 44 44 20 20 10 10 02 02 20 20 08 08 07 07 05 05 32 32 14 14 1 2 3 4 5 6 7 8 91011r1.06 06 44 44 10 10 20 20 02 02 20 20 07 07 08 08 05 05 32 32 14 14y1.06 06 10 10 20 20 44 44 02 02 07 07 08 08 20 20 05 05 14 14 32 32r1.02 02 06 06 07 07 08 08 10 10 20 20 20 20 44 44 05 05 14 14 32 32y1.1 2 3 4 5 6 7 8 91011 1 2 3 4 5 6 7 8 91011 1 2 3 4 5 6 7 8 91011 02 02 05 05 06 06 07 07 08 08 10 10 14 14 20 20 20 20 32 32 44 44r1.1 2 3 4 5 6 7 8 91011第1趟第3趟第2趟第4趟一趟归并排序算法一趟归并排序算法：void mergepass(r,y,s)/s s为子文件的长度为子文件的长度 RecType r,y；int s；/将将r r中的子文件归并到中的子文件归并到y y中中 int i=1；while(i+2*s-1=)/两两归并长度均为两两归并长度均为s s的子文件的子文件 merge(r,y,i,i+s-1,i+2*s-1)；i=i+2*s；if(i+s-1n)/最后两个子长度为最后两个子长度为s s和长度不足和长度不足s s的文件的文件 merge(r,y,i,i+s-1,n)；else while(i=n)/复制最后一个子文件复制最后一个子文件,长度长度s s yi=ri；i+；调用算法mergepass，对文件对文件r r1.1.nn归并排序的算法归并排序的算法 void mergesort(RecType r,int n)RecType yn+1；int s=1；/子文件初始长度为子文件初始长度为1 1 while(sri+1.key，则交换记录ri和ri+1的位置；否则,不交换。(i=1,2,.n-1)第1趟之后,n个关键字中最大的记录移到了rn的位置上。第第2 2趟趟：从r1开始,依次比较两个相邻记录的关键字ri.key和ri+1.key,若ri.keyri+1.key，则交换记录ri和ri+1的位置；否则,不交换。(i=1,2,.n-2)第2趟之后,前n-1个关键字中最大的记录移到了rn-1的位置上。.作完作完n-1n-1趟趟,或者不需再交换记录时为止。例：第1趟 第2趟 第3趟 第4趟 k1=43 21 21 21 21 21 21 21 21 15 15 1515k2=21 43 43 43 43 43 43 15 15 21 21 2121k3=89 89 89 15 15 15 15 28 28 28 28 28 28 k4=15 15 15 89 28 28 28 43 43 4343 43 4343 43k5=28 28 28 28 89 43 43 4343 43 43 43 4343 43 43 43k6=43 43 43 43 43 8989 89 8989 89 89 89 89 8989 89 89 89 比较次数=543214 交换记录的次数=3+2+1=6，移动记录次数=3*6=18 算法分析 最好情况最好情况:待排序的文件已是有序文件，只需要进行1趟 排序,共计比较关键字的次数为 n n1 1 不交换记录不交换记录。最坏情况最坏情况:要经过n-1趟排序，所需总的比较关键字的次 数为 (n-1)+(n-2)+.+1n(n-1)/2 交换记录的次数最多为 (n-1)+(n-2)+.+1n(n-1)/2 移动记录次数最多为 3 3n(n-1)/2n(n-1)/2。只需要少量中间变量作为辅助空间。算法是稳定稳定的。冒泡排序算法冒泡排序算法/对n个整数按递增次序作冒泡排序 Void bubble1(int a,int n)int i,j,temp；for(i=0；in-1；i+)/作n-1趟排序 for(j=0；jaj+1)temp=aj；/交换记录 aj=aj+1；aj+1=temp；for(i=0；in；i+)printf(%d,ai)；/输出排序后的元素 改进的冒泡排序算法改进的冒泡排序算法void bubblesort(RecType r,int n)int i,j,swap；RecType temp；j=1；/置比较的趟数为1 do swap=0swap=0；/置交换标志为0 for(i=1；iri+1.key)temp=ri；/交换记录 ri=ri+1；ri+1=temp；swap=1swap=1；/置交换标志为1 j+；/作下一趟排序 while(jn&swapjn&swap)；/未作完n-1趟,且标志为110.5.2 快速快速排序排序 基本思想：首先在r1.n中，确定一个ri，经过比较和移动，将ri放到中间某个位置上，使得ri左边所有记录的关键字小于等于ri.key，ri右边所有记录的关键字大于等于ri.key。以以riri为界为界,将文件划分为左、右两个子文件将文件划分为左、右两个子文件。用同样的方法分别对这两个子文件进行划分,得到4个更小的子文件。继续进行下去,使得每个子文件只有一个记录为止,便得到原文件的有序文件。例.给定文件(20,05,37,08,63,12,59,15,44,08)，选用第1个元素20进行划分:2005370863 1259154408 20 xij例0805370863 1259154408 20 x0805370863 1259154408 20 xijij0805370863 1259154437 20 xij0805150863 1259154437 20 xij0805150863 1259154437 20 xij0805150863 1259634437 20 xij0805150812 125963443720 xi j0805150812 205963443720 xi j左子文件右子文件例 快速快速排序排序void quksort(r,low,high)RecType r；int low,high；RecType x；int i,j；if(lowhigh)/有两个以上记录 i=low；j=high；x=ri；/保存记录到变量x中 do while(ix.key)j-；/j向左端扫描 if(ij)/i,j未相遇 ri=rj；i+；while(ij&ri.keyx.key)i+；/i向右端扫描 if(ij)rj=ri；j-；while(i!=j)；/i,j未相遇 ri=x；/划分结束 quksort(r,low,i-1)；/递归处理左子文件 quksort(r,i+1,high)；/递归处理右子文件 对文件r1.n快速排序 void quicksort(RecType r,int n)quksort(r,1,n)；算法分析 就平均速度而言，快速排序是已知内部排序方法中最好的一种排序方法,其时间复杂度为O(nlog(n)。但是，在最坏情况下，快速排序所需的比较次数和冒泡排序的比较次数相同,其时间复杂度为O(n2)。快速排序需要一个栈作辅助空间，用来实现递归处理左、右子文件。在最坏情况下,递归深度为n，因此所需栈的空间大小为O(n)数量级。快速排序是不稳定的。10.6 10.6 基数排序基数排序基数排序的一般过程：基数排序的一般过程：将任一关键字将任一关键字K K看做一个看做一个d d元组：元组：K=(K1,K2,K=(K1,K2,，KdKd)其中：其中：K1K1是是最高位，最高位，KdKd是是最低位最低位K K，按组成关键字关键按组成关键字关键字的每一位的值进行排序。字的每一位的值进行排序。排序过程（以十进制正整数为例）：排序过程（以十进制正整数为例）：设文件有设文件有n n个记录（个记录（R1,R2,R1,R2,，RnRn），），记录记录RiRi的的关键字为关键字为KiKi,且且KiKi是不超是不超d d位的非负位的非负整数。整数。：建立十个队列，编号分别为建立十个队列，编号分别为0,1,2,0,1,2,9,9 ：重复执行：重复执行d d遍遍 分配：若分配：若KiKi【d d】=j j，则则RiRi放入第放入第j j号队列号队列（j=0,1,j=0,1,9,9）收集：按收集：按0,1,0,1,9,9的次序将各队列中的记录收的次序将各队列中的记录收集和排列起来。集和排列起来。d=d-1d=d-1 例：设有例：设有关键字序列：关键字序列：27736705464215511382121 队列队列0 701 21,11,21212 0234 54,645 556 367 778 389分配分配 7021112121025464553677380 021 112 21,21213 36,3845 54,556 647 70,7789队列队列 队列队列0 701 21,11,21212 0234 54,645 556 367 778 389收集收集分配分配 0211212121363854556470770 021 112 21,21213 36,3845 54,556 647 70,7789队列队列收收 集集问题：各问题：各队列的长度队列的长度如何确定？如何确定？例例2：已知：已知 n=12,d=2,r=10（12个个2位的十进制整数，低位位的十进制整数，低位优先优先）012345678910 1191 01 72 23 84 05 25 27 97 17 67 28A 01234567890211120410COUNT 0.9各各队列中队列中的记录个的记录个数数023457711 12 12分配分配012345678910 1127 91 01 97 17 23 84 28 72 05 67 25B 收集收集 910172238405252797176728 0 1 2 3 4 5 6 7 8 9 10 11a 2377778910 12count0.9214000111201 01 72 23 25 27 28 67 72 84 91 97 0 1 2 3 4 5 6 7 8 9 10 11收集收集分配分配b 参考程序如下：参考程序如下：for(i=0,d=1;ik;i+,d*=r)for(j=0;jr;j+)countj=0;/初始化初始化 for(j=0;jn;j+)count aj/d%r+;/统计各统计各队列中的记录个数队列中的记录个数 for(j=1;j=0;j-)b-countaj/d%r=aj;/收收集集 for(j=0;jn;j+)aj=bj;注：注：d 1为个位，为个位，10为十位，为十位，k 整数的最大位数整数的最大位数；r 数值的基数数值的基数（如八如八进制数，十进制数等）；进制数，十进制数等）；n 关键字个数。关键字个数。内排序小结内内排序方法排序方法 插入排序：直接插入排序；选择排序：简单选择/选择排序；堆排序 归并排序 2-路归并排序 k-路归并排序 交换排序 冒泡排序：快速排序 基数排序 最低位优先法 .什么是排序排序,什么是排序的稳定性排序的稳定性排序算法分析排序算法分析(1)时间复杂度时间复杂度 对n个记录排序，所需比较关键字的次数比较关键字的次数；最好情况；最坏情况；平均情况 对n个记录排序，所需移动记录的次数移动记录的次数；最好情况；最坏情况；平均情况(2)空间复杂度空间复杂度 排序过程中，除文件中的记录所占的空间外，所需的辅助存储空间辅助存储空间的大小。第第11章章 外部排序外部排序外部排序思想外部排序思想 设磁盘有设磁盘有4500个记录的文件，磁盘的读个记录的文件，磁盘的读写单位是写单位是250个个记录的数据块，内存只能提供记录的数据块，内存只能提供1500个记录的空间，试个记录的空间，试对此文件进行排序。对此文件进行排序。解：解：从磁盘文件输入三个数据块，计从磁盘文件输入三个数据块，计750个记录至内个记录至内存，排序后再写入磁盘；存，排序后再写入磁盘；按按同样的方法得如下同样的方法得如下归并段：归并段：R1 R2 R3 R4 R5 R6 1 750 7511500 1501 2250 2251 3000 3001 3750 3751 4500 归并归并R1,R2R1,R2 R1 R2BF1BF2BF3内存区内存区3块计块计750个记录个记录R12磁盘（磁盘（1500个记录）个记录）部分有序部分有序磁盘（磁盘（1500个记录）个记录）整体有序整体有序 按同样得方法得：R34,R56,R1234,R123456R1 R2 R3 R4 R5 R6R56R12R34R1234R12345615001500150030004500个记录整体有序个记录整体有序1遍2/3遍1遍 建立初始归并段要把全部记录（建立初始归并段要把全部记录（45004500）读写成）读写成遍，完成全部记录的归并要把（遍，完成全部记录的归并要把（45004500）个记录）个记录读写读写8/38/3遍。下面分析三路归并的情况：遍。下面分析三路归并的情况：R1 R2 R3 R4 R5 R69块块9块块完成全部记录的归并要把（完成全部记录的归并要把（45004500）个记录读写）个记录读写2 2遍。遍。结论结论：M个初始归并段进行初始归并段进行K K路归并时，归并的路归并时，归并的趟数为：趟数为：S=log(K(M)S=log(K(M)证明：设证明：设M M为为K K的整幂次，即的整幂次，即M=KM=K*s s （s s为整数）为整数）第一趟归并得第一趟归并得 k*(s-1)k*(s-1)个为归并段个为归并段;第二趟归并得第二趟归并得 k*(s-2)k*(s-2)个为归并段个为归并段;第第s s趟归并得趟归并得 k*s-s=1k*s-s=1个归并段个归并段;由由m=k*s m=k*s，有有loglog（k k（m m）=s=s 当当m m不是不是k k的整幂次时，归并趟数是的整幂次时，归并趟数是 log log（k k（m m）的上界函数的上界函数log(K(M)log(K(M)证毕证毕 上式说明：要上式说明：要s s，只有只有K K 或或m m 最佳归并树最佳归并树 设有设有8 8个初始归并段，其长度（以个初始归并段，其长度（以外存物理块为单位外存物理块为单位）分别为分别为2 2，3 3，6 6，9 9，1212，1717，1818，2424，求其，求其3 3路最佳归路最佳归并树，并求其并树，并求其WPLWPL和对和对外存的访问次数。外存的访问次数。解解1：312622418179115932910WPL=(2+3+6)*3+(9+12)*2+(17+18+24)*2=193读写次数WPL*2 =386权权值值愈愈小小的的结结点点，离离根根愈愈近近？解2：k-（m-1)mod(k-1)-1=3-(8-1)mod(3-1)-1=1 虚设一个虚设一个长度为长度为“0 0”的归并段。的归并段。18171296532091472420WPL=(0+2+3)*3+(6+9+12+17+18)*2+24*1=163读写次数WPL*2=326权权值值愈愈小小的的结结点点，离离根根愈愈远远！如何判定虚设如何判定虚设段的个数？段的个数？令令 M M 初始归并段的个数初始归并段的个数 K K 归并的路数归并的路数若（若（M-1)MOD(K-1)=0M-1)MOD(K-1)=0，则不加则不加虚设虚设段；段；否则需加否则需加 P P个个虚设虚设段。段。P=K-(M-1)MOD(K-1)P=K-(M-1)MOD(K-1)1 1