吉林大学数据结构课件 第七章 排序

排序,概述,排序：排序指按规定的顺序排列一个给定对象集合中的诸元素。文件:它是待排序数据对象的有限集合。记录：R1，R2，Rn关键词域(key):通常数据对象有多个属性域，即多个数据成员组成，其中有一个属性域可用来区分对象，作为排序依据。该域即为关键词域。每个文件用哪个属性域作为关键词，要视具体的应用需要而定。即使是同一个文件表，在解决不同问题的场合也可能取不同的域做关键码。,概述主关键词:如果在数据表中各个对象的关键码互不相同，这种关键码即主关键码。按照主关键码进行排序，排序的结果是唯一的。次关键词:数据表中有些对象的关键码可能相同，这种关键码称为次关键码。按照次关键码进行排序，排序的结果可能不唯一。,概述排序：记录按关键词域递增或递减的顺序排列n个记录相应的关键词:K1，K2，Kn在关键词域上定义一个次序关系“”，使得对于任意三个关键词的取值a、b、c，下列条件成立：在ab，a=b，ba三个可能性中，有且只有一个可能性成立（三分率）；如果ab，并且bc，则有ac（传递性）.这两个性质显示了线性次序的数学性质，也称作全序.,概述排序：记录按关键词域递增或递减的顺序排列n个记录相应的关键词:K1，K2，Kn在关键词域上定义一个次序关系“”；排序的目标就是寻找一个置换:使得诸关键词按照非递减的次序排列，即有K(1)K(2)K(n),排序的时间开销:排序的时间开销是衡量算法好坏的最重要的标志。排序的时间开销可用算法执行中关键词的比较次数与数据的移动次数来衡量。各节给出算法运行期望时间代价是对按平均情况进行估算。对于那些受对象关键词序列初始排列及对象个数影响较大的，需要按最好情况和最坏情况进行估算。算法执行时所需的附加存储空间:评价算法好坏的另一标准。,排序算法的稳定性:当K(i)=K(j)并且iKj，则称（Ki，Kj）为上述序列的一个反序对.交换排序的思想：交换文件中存在的反序对冒泡排序、分划交换排序（快速排序）,7.2.1冒泡排序冒泡排序思想：通过比较相邻记录的关键词，交换存在逆序的记录；使关键词较大的记录如气泡一般逐渐往上“飘移”直至“水面”。,09,02,16,08,05,12,123456789,13,14,07,算法BSort(R，n)BS1冒泡过程FORi=nTO2STEP1DOFORj=1TOi1DOIFKjKj+1THEN(RjRj+1)关键词的比较次数为(n-1)+(n-2)+1=(n-1)n/2,经过一趟冒泡，可以把具有最大关键词的记录移至最后（第n个位置）。第i趟冒泡，把第i大记录放在第i个位置上。做n-1趟冒泡，就可以对所有记录排序。发生一次记录交换，反序对的个数减少一个。,在扫描过程中，可能最后几趟已无任何交换发生，程序应能做到，一旦发现某趟扫描中无任何交换时就会终止,算法的改进,/改进的冒泡排序算法.算法Bubble(R，n)Bubble1终止位置初始化BOUNDnBubble2冒泡过程WHILEBOUND0DO(t0/t用来记录一趟冒泡最后记录交换的位置FORj1TOBOUND1DOIFKjKj+1THEN(RjRj+1.tj).BOUNDt)冒泡排序演示,假定记录序列R1，R2，Rn所对应的关键词序列为A=K1，K2，Kn令bj（1jn）表示A中关键词第j小的记录左边大于它的关键词的个数，则文件b1，b2，bn称为A的反序表.,经过一趟冒泡后，记录的位置发生变化，反序表也会发生变化。,经过一趟冒泡后，记录的位置发生变化，反序表也会发生变化。,经过一趟冒泡后，记录的位置发生变化，反序表也会发生变化。,经过一趟冒泡后，记录的位置发生变化，反序表也会发生变化。,经过一趟冒泡后，记录的位置发生变化，反序表也会发生变化。,经过一趟冒泡后，记录的位置发生变化，反序表也会发生变化。,经过一趟冒泡后，记录的位置发生变化，反序表也会发生变化。,经过一趟冒泡后，记录的位置发生变化，反序表也会发生变化。,after,before,经过一趟冒泡后，记录的位置发生变化，反序表也会发生变化。定理7.1设K1，K2，Kn是序列1，2，n的一个排列，b1，b2，bn是对应的反序表.如果算法Bubble的一趟冒泡把K1,K2,Kn改变为K1,K2,Kn,那么从b1,b2,bn中把每个非零元素减1,就得到了相应的反序表b1,b2,bn.,冒泡趟数：A=1+maxb1，b2，bn记录的初始排列是按关键词从小到大排好序时，此算法只执行一趟起泡，做n-1次关键词比较，不发生记录交换；这是最好的情形。最坏的情形是算法执行了n-1趟起泡，第i趟(1in)做了n-i次关键词比较，执行了n-i次记录交换。这样在最坏情形下总的关键词比较次数和记录交换次数为：(n-1)n/2,推论7.1算法Bubble的冒泡趟数A=1+maxb1，b2，bn；记录交换次数B=bi；关键词的比较次数C=Ci，其中Ci等于第i趟冒泡时的BOUND减1.,冒泡排序算法时间复杂度:O(n2)（包括最坏和平均）.稳定性：冒泡排序是稳定的排序方法。最好情况是：当被排序文件初态为正序时，算法的时间复杂度为O(n).空间复杂度：O(1).可以采用气泡上浮和下沉交替的方法。,交换任意反序对后，D=的变化?KiKjK1，Ki-1，Ki，Ki+1Kj-1，Kj，Kj+1，Knd1，di-1，di，di+1dj-1，dj，dj+1，dnd1di-1,dj+1dn没有发生变化D=D-1+?MAX（D-D）,7.2.2分划交换排序1962年Hoare提出了快速排序(QuickSort)特点：一趟分划把一个记录放在最终的位置上。原理：交换反序对，一次记录交换使得文件中的反序对的数目减少的更多。,快速排序的基本思想:不断地交换反序对。任取待排序文件中的某个记录(例如取第一个记录)作为基准，按照该记录的关键词大小，将整个文件划分为左右两个子文件：左侧子文件中所有记录的关键词都小于或等于基准记录的关键词右侧子文件中所有记录的关键词都大于基准记录的关键词,基准记录则排在这两个子文件中间(这也是该记录最终应安放的位置)。分别对两个子文件重复施行上述方法，直到所有的记录都排在相应位置上为止。,算法描述QuickSort(R)if(R的长度大于1)将文件R划分为两个子文件LeftR和RightR;QuickSort(LeftR);QuickSort(RightR);将两个子文件LeftR和RightR合并为一个文件R;,(1)(2)(3)(4)(5)(6)(7)(8)(9)7073692393181168100i(第一个大于)(第一个小于)j7068692393181173100706869231118937310070686923111893731001868692311709373100,算法QSort（R，m，n）/*对文件（Rm，Rn）进行排序.我们选择Km作为控制分划的关键词，并假定对任意的min有KiKn+1.*/QSort1递归出口IFmKDOjj1.IFijTHENRiRj)RmRj.QSort(R，m，j1).QSort(R，j+1，n)分划交换排序演示,i=1,7073692393181168MAX,1868692311709373MAX,im.jn+1.KKmWHILEiKDOjj1.IFijTHENRiRj)RmRj.,一趟快速排序过程示例:,多趟快速排序过程示例,2算法QSort（R，m，n）IFmKnTHENRm+1Rn.IFKmKnTHENRmRn.IFKm+1KmTHENRm+1Rm.Part2分划开始imjn+1KKm.Part3用Km分划文件(Rm，Rm+1，Rn)WHILEijDO(ii1WHILEKiKDOii1jj1WHILEKjKDOjj1.IFijTHENRiRj)RmRj,快速排序算法时间复杂度:O(n2)/最坏.时间复杂度:O(nlog2n)/最好和平均空间复杂度：O(log2n).稳定性：快速排序是不稳定的排序方法。快速排序方法是目前内部排序中最好、最快的排序方法。,7.3选择排序思想：对待排序的文件进行n次选择，其中第i次选择第i小（或大）的记录放在第i（或n-i+1）个位置上。直接选择排序堆排序,7.3.1直接选择排序1直接选择排序思想：选择第i大的记录在剩余的n-i+1个记录中进行一趟比较，确定出第i大记录，放在第n-i+1个位置上。例如第i趟比较（i=0,1,n-2）在前面n-i个待排序记录中选出关键码最大的记录,作为有序记录序列的第i个记录。待到第n-2趟作完，待排序记录只剩下1个时，算法结束。,算法SSort（R，n）/直接选择排序算法，该算法排序文件（R1，R2，Rn）SS1排序FORj=nTO2STEP1DO(t1.FORi2TOjDOIFKtKiTHENti/找第j小元素/的下标RjRt)/将Rt放到第j个位置上,(1)(2)(3)(4)(5)(6),it,2算法SSort（R，n）FORj=nTO2STEP-1DO(t1.FORi2TOjDOIFKtKiTHENtiRiRt),21254925*160832,21254925*160843,21254925*160853,21254925*160863,21250825*1649,21250825*1649,21254925*1608,一趟选择排序过程示例,多趟选择排序过程示例,(1)(2)(3)(4)(5)(6),i,t,121250825*16492,221160825*25494,321160825*25491,508162125*25491,408162125*25492,算法分析直接选择排序的关键词比较次数与记录的初始排列无关。假定整个待排序文件有n个记录，第i趟选择具有最大关键词的记录所需的比较总次数是n-i次。因此，总的关键词比较次数为(n-1)+(n-2)+1=记录交换次数是选择的趟数:n-1.,直接选择排序算法时间复杂度:O(n2)（包括最好、最坏和平均）.稳定性：不稳定的排序方法。空间复杂度：O(1).优点：简单、书写容易,i=1mid=4j=8A1A2A3A4A5A6A7A852012730402516,算法SM的改进,i=1mid=4j=8A1A2A3A4A5A6A7A852012730402516,算法SM的改进,i=1mid=4j=8A1A2A3A4A5A6A7A852012730402516,算法SM的改进,i=1mid=4j=8A1A2A3A4A5A6A7A852012730402516,算法SM的改进,i=1mid=4j=8A1A2A3A4A5A6A7A852012730402516,算法SM的改进,i=1mid=4j=8A1A2A3A4A5A6A7A852012730402516,算法SM的改进,淘汰赛的思想对于n个记录的关键词，进行两两比较，得到n/2个比较的优胜者(关键词大者)，作为第一步比较的结果保留下来。然后对这n/2个记录再进行关键词的两两比较，如此重复，直到选出一个关键词最大的记录为止。,n-1（15）次比较K(16)=94；(16)=6,4次比较（14）K(15)=93；(15)=10,4次比较（13）K(14)=91；(14)=1,|,次元素比较次数:(n1)+(n1)*log2nnlog2n,淘汰赛示意图,从开始寻找最大元素的过程就是找兄弟结点和父亲结点的过程.,从开始寻找最大元素的过程就是找兄弟结点和父亲结点的过程.完全二叉树：第i个元素的左、右儿子分别是第2i和第2i1个元素，父亲结点是第i/2个元素.,7.3.2堆排序原理利用淘汰赛的方式寻找当前序列中的最大记录关键与当前的最大记录做比较的记录解决堆,完全二叉树中的任意非叶结点的关键词大于等于它的两个儿子结点的关键词.我们把这样的数据结构称为堆(极大堆)。极大(大根)堆极小(小根)堆,例123456789101112949375918544511848581034,如果数组R中存放了堆，那么R1是最大的记录，将R1和Rn交换，使得最大记录放在Rn的位置。,例123456789101112949375918544511848581034,例123456789101112949375918544511848581034,例123456789101112349375918544511848581094,然后对R1，Rn-1进行调整，使它们构成一个堆。调整后，R1是R1，R2，Rn-1中最大的。然后再交换R1与Rn-1，使Rn-1中放入次最大的记录。,例123456789101112349375918544511848581094,例123456789101112939175488544511834581094,例123456789101112109175488544511834589394,例123456789101112109175488544511834589394,再对R1，R2，Rn-2进行调整，使之成为新堆，再进行类似的交换和调整，反复进行，直到调整范围只剩下一个记录R1为止。此时R1是n个记录中最小的，且数组Rn中的记录已经按从小到大排列了。,堆排序算法的粗略描述如下：（l）建立包含Kl，K2，Kn的堆；（2）FORinTO2STEP1DO（RlRi重建包含Kl，K2，Ki1的堆）,堆排序:若在输出堆顶的最大值之后，使得剩余n1个元素的序列重又建成一个堆，则得到n个元素中的次大值。如此反复执行，便能得到一个有序序列。堆排序需解决的两个问题：如何建堆；输出堆顶元素后，如何调整新堆。,重建堆R1与Ri交换后，只有R1与其左右儿子不满足堆的性质.如果根结点的儿子存在，则比较根和两个儿子的关键词.如果根结点的关键词大，则说明该结构已经是堆，终止重建过程.如果根结点的关键词小，则它和关键词大的儿子进行交换，并以这个儿子为根结点继续重建下去.,算法Restore（R，f，e）/重建堆R1初始化jfR2建堆WHILEje/2DO(IF(2jKjTHEN（RmRj.jm）ELSEje）重建堆演示,2初始建堆:将序号为n/2,n/2-1,1的结点作为根的子树都调整为堆即可。例关键字序列（42,13,91,23,24,16,05,88)。,初始建堆过程：,堆排序过程：,堆排序过程：,堆排序过程：,堆排序过程：,堆排序过程：,堆排序过程：,堆排序过程：,0513162324428891,算法HeapSort(R，n)/堆排序算法HS1初始建堆FORin2TO1STEP1DORestore（R，i，n）HS2排序FORinTO2STEP1DO(R1Ri.Restore(R，1，i1)堆排序演示,堆排序算法时间复杂度:O(nlog2n)（包括最好、最坏和平均）.稳定性：堆排序是不稳定的排序方法。空间复杂度：O(1).,7.4合并排序合并：把两个或多个有序文件组成一个单一的有序文件。两个文件的合并。,3合并排序。,合并排序过程示例,假定文件（Rt，Rt1，Rm）和文件（Rm1，Rn）都已经排序，如何合并这两个文件，得到排序好的大文件（Xt，Xt1，Xn）；执行合并过程，将文件R中长度为length的所有子文件合并到文件X中；,两个有序文件合并成一个大的有序文件算法Merge(R，t，m，n.X)算法Merge()演示M1初始化给每个文件一个头指针itjm1k1M2比较i和j所指记录WHILE（im）AND（jn）DO（IFKiKjTHEN（XkRiii1）ELSE（XkRjjj1）.kk+1）.M3复制余留记录项WHILE(im)Xk=Ri.ii1.kk+1.WHILE(jn)Xk=Rj.jj1.kk+1.,两个有序文件合并成一个大的有序文件算法Merge(R，t，m，n.X)算法Merge()演示M1初始化给每个文件一个头指针itjm1k1M2比较i和j所指记录WHILE（im）AND（jn）DO（IFKiKjTHEN（XkRiii1）ELSE（XkRjjj1）.kk+1）.M3复制余留记录项WHILE(im)Xk=Ri.ii1.kk+1.WHILE(jn)Xk=Rj.jj1.kk+1.,X,算法Merge(R，t，m，n.X)：假定文件（Rt，Rt1，Rm）和文件（Rm1，Rn）都已经排序，该算法合并这两个文件后得到排序好的大文件（Xt，Xt1，Xn）；,算法MPass（R，n，1engthX）/*一趟合并算法，该算法执行一趟合并过程，将文件R中长度为length的所有子文件合并到文件X中，n是R的记录个数*/MP1初始化i1MP2合并相邻的两个长度为length的子文件WHILEin2*length+1DO（Merge（R，i，ilengthl，i2*length1X）.ii2*length）MP3处理余留的长度小于2*length的子文件IFi+length1nTHENMerge（R，i，i+length1，n.X）ELSEFORj=iTOnDOXjRj,算法MPass（R，n，1engthX）/*一趟合并算法，该算法执行一趟合并过程，将文件R中长度为length的所有子文件合并到文件X中，n是R的记录个数*/MP1初始化i1MP2合并相邻的两个长度为length的子文件WHILEin2*length+1DO（Merge（R，i，ilengthl，i2*length1X）.ii2*length）MP3处理余留的长度小于2*length的子文件IFi+length1nTHENMerge（R，i，i+length1，n.X）ELSEFORj=iTOnDOXjRj,i,算法MPass（R，n，lengthX）：一趟合并算法，该算法执行一趟合并过程，将文件R中长度为length的所有子文件合并到文件X中，n是R的记录个数，该函数调用Merge()函数；,算法MSort(R，n)/直接两路合并排序算法，X是辅助文件，其记录结构与R相同MS1初始化length1MS2交替合并WHILElengthnDO（MPass（R，n，lengthX）.length2*lengthMPass（X，n，lengthR）.length2*length）,算法Merge(R，t，m，n.X)：假定文件（Rt，Rt1，Rm）和文件（Rm1，Rn）都已经排序，该算法合并这两个文件后得到排序好的大文件（Xt，Xt1，Xn）；算法Merge()演示算法MPass（R，n，lengthX）：一趟合并算法，该算法执行一趟合并过程，将文件R中长度为length的所有子文件合并到文件X中，n是R的记录个数，该函数调用Merge()函数；算法MPass()演示算法MSort(R，n)：该函数调用函数Mpass(),直接两路合并排序，X是辅助文件；合并排序MSort(R，n)演示,合并排序。,合并排序过程示例,合并趟数：第一趟，合并长度为1的n个文件；第二趟，合并长度小于等于2的个文件；第i趟，合并长度小于等于2i-1的文件，得到的文件长度大于2i-1，且小于等于2i.如果存在正整数k，使得2kn2k+1，合并排序共需要k+1趟合并(log2nk+1log2n+1即k+1=log2n).由于每趟合并的文件的总长度为n，而算法Merge所需的比较次数小于等于n（记录移动正好n次），因此合并排序在最坏情况下的关键词比较次数nlog2n，而记录移动次数正好为nlog2n,合并排序算法时间复杂度:O(nlog2n)（包括最好、最坏和平均）.稳定性：合并排序是稳定的排序方法。