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

排序排序：排序指按规定的顺序排列一个给定对象集合中的诸元素。文件:它是待排序数据对象的有限集合。记录：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)12(1)(2)()nni123456789Ki070902160805121413ρ(i)351942687Kρ(i)020507080912131416排序的时间开销:排序的时间开销是衡量算法好坏的最重要的标志。排序的时间开销可用算法执行中关键词的比较次数与数据的移动次数来衡量。各节给出算法运行期望时间代价是对按平均情况进行估算。对于那些受对象关键词序列初始排列及对象个数影响较大的，需要按最好情况和最坏情况进行估算。算法执行时所需的附加存储空间:评价算法好坏的另一标准。排序算法的稳定性:当Kρ(i)=Kρ(j)并且ij时，总有ρ(i)ρ(j)，这里1≤i，j≤n，则我们就称该排序过程具有稳定性.排序的时间开销(时间复杂性)算法执行时所需的附加存储空间（空间复杂性）排序算法的稳定性算法基本思想插入排序，交换排序，选择排序，合并排序算法适用条件分类：内排序和外排序升序和降序存储：数组和链表7.1插入排序插入排序思想：将一个记录插入到已排好序的有序表中，从而得到一个新的、记录数加一的有序表。（915232837）20（915??232837）20排序方法:R1，R2，…，Rn–1,Rn．第一步：R1；第二步：R1,R2第三步：(R1,R2),R3……第j步：(R1，R2，…，Rj–1),Rj；……第n步：(R1，R2，…，Rn–1),Rn．有序序列R[1..j-1]无序序列R[j+1..n]R[j]关键问题:如何找到插入位置？？？(R1，R2，…，Rj–1)Rj直接插入排序直接插入排序思想：从后向前依次和每个记录比较，找到插入位置。直接插入排序的算法算法InsertSort(R，n)/*本算法排列n个记录，使得它们相应的关键词排列成一个非递减的序列*/1.IS1[逐一排序]2.FORj＝2TOnDO3.(i←j–1．//每次循环Rj插入到R1，…，Rj–1中4.K←Kj.R←Rj.5.WHILEi＞0ANDK＜KiDO6.(Ri+1←Ri．7.i←i–l)．8.Ri+1←R)▌有序序列R[1..j-1]无序序列R[j+1..n]R[j]i各趟排序结果21254925*1608123456123456temp21254925*160825j=2i←j–1．K←Kj.R←Rj.//i=1,K=25,R=R2WHILEi＞0ANDK＜KiDO(Ri+1←Ri．i←i–l)．Ri+1←R各趟排序结果21254925*1608123456123456temp21254925*160825j=2123456temp21254925*160849j=321254925*1608123456j=425*212525*1608j=516123456temp49WHILEi＞0ANDK＜KiDOj=5时的排序过程161621254925*0816j=5i=4123456temp491621254925*0816j=5i=3123456temp25*1621254925*08123456temp16j=5i=22516214925*081625j=5i=1123456temp21254925*081621j=5i=016123456temp212525*1608j=608123456temp492516214925*081625j=5i=1123456temp21254925*081621j=5i=016123456temp21254925*1608完成123456算法InsertSort的每次FOR循环，正好完成了把Rj插入到R1，R2，…，Rj–1之中（此时K1≤K2≤…≤Kj–1）之中．算法InsertSort(R，n)/*本算法排列n个记录，使得它们相应的关键词排列成一个非递减的序列*/1.IS1[逐一排序]2.FORj＝2TOnDO3.(i←j–1．//每次循环Rj插入到R1，…，Rj–1中4.K←Kj.R←Rj.5.WHILEi＞0ANDK＜KiDO6.(Ri+1←Ri．7.i←i–l)．8.Ri+1←R)▌WHILE语句每次比较都要判断i是否大于零，为了减少在特殊情况下的比较次数，这里我们可引入一个虚设的记录R0，使K0≤min{Ki|1≤i≤n}．//K0=－∞算法InsertSort(R，n)/*本算法排列n个记录，使得它们相应的关键词排列成一个非递减的序列*/1.IS1[逐一排序]2.FORj＝2TOnDO3.(i←j–1．//每次循环Rj插入到R1，…，Rj–1中4.K←Kj.R←Rj.5.WHILEi＞0ANDK＜KiDO6.(Ri+1←Ri．7.i←i–l)．8.Ri+1←R)▌插入排序的算法算法InsertSortA(R，s,e)ISA1[逐一排序]FORj＝s+1TOeDO(i←j–1．K←Kj.R←Rj.WHILEK＜KiDO(Ri+1←Ri．i←i–l)．Ri+1←R)▌FORj＝s+1TOeDO(i←j–1．K←Kj.R←Rj.WHILEK＜KiDO(Ri+1←Ri．i←i–l)．Ri+1←R)▌k[1]k[2]k[3]k[4]k[0]k[5]8724－∞6j插入排序演示插入算法分析：设dj是Rj左边关键词大于Kj的记录个数，则算法InsertSortA中关键词的比较次数为：记录的移动次数为njnjjjdnd221)1(njjdnn2)1()1(1.FORj＝s+1TOeDO2.(i←j–1．K←Kj.R←Rj.3.WHILEK＜KiDO4.(Ri+1←Ri．5.i←i–l)．6.Ri+1←R)▌对于序列K1，K2，…，Kn，如果1≤i＜j≤n，且KiKj，则称（Ki，Kj）为上述序列的一个反序对.正好是序列K1，K2，…，Kn的反序对个数2njjd我们设想K1，K2，…，Kn是这样生成的：第一次从｛K1，K2，…，Kn｝中选出一个元素，不妨假定为最小元素Kρ(1)；{Kρ(1)，…，Kρ(n)}Kρ(1)d1=0,p11=1我们设想K1，K2，…，Kn是这样生成的：第一次从｛K1，K2，…，Kn｝中选出一个元素，不妨假定为最小元素Kρ(1)；第二次从{Kρ(2)，…，Kρ(n)}选取一个元素，不妨假定为最小元素Kρ(2)，Kρ(2)放在Kρ(1)的左边或者右边，如放在左边则产生一个反序对，而放在右边不产生反序对；{Kρ(1)，…，Kρ(n)}Kρ(1)d1=0,p11=1Kρ(1),Kρ(2)d2=0,p21=1/2Kρ(2),Kρ(1)d2=1,p22=1/2我们设想K1，K2，…，Kn是这样生成的：第一次从｛K1，K2，…，Kn｝中选出一个元素，不妨假定为最小元素Kρ(1)；第二次从{Kρ(2)，…，Kρ(n)}选取一个元素，不妨假定为最小元素Kρ(2)，Kρ(2)放在Kρ(1)的左边或者右边，如放在左边则产生一个反序对，而放在右边不产生反序对；第三次从{Kρ(3)，…，Kρ(n)}中选出一个元素，仍不妨假定为最小的元素Kρ(3)，Kρ(3)可以放在Kρ(1)和Kρ(2)的左边、中间或者右边，并且由此产生的反序对的个数是2，l，0，…．Kρ(?),Kρ(?),Kρ(3)d2=0,p1=1/3Kρ(?),Kρ(3),Kρ(?)d2=1,p2=1/3Kρ(3),Kρ(?),Kρ(?)d2=2,p3=1/3如果我们假设Kρ(j)插人到Kρ(1)，Kρ(2)，…，Kρ(j–1)的每个位置的概率是相等的，即Kρ(2)放在Kρ(1)的左边或右边的概率是1/2；Kρ(3)放在Kρ(1)和Kρ(2)的左边、中间和右边的概率是1/3；…………………………………Kρ(n)插到Kρ(1)，…，Kρ(n–1)的任何位置的概率是1/n.2njjd=0+21(0+1)+31(0+1+2)+…+n1(0+1+2+…+n–1)=0+21+33+…+21n=n(n–1)/4即2njjd的期望值为n(n–1)/4.平均情况下:若待排序文件中记录所有可能的排列的概率相同，则可取上述最好情况和最坏情况的平均情况。在平均情况下的关键词比较次数和记录移动次数分别为因此，直接插入排序的时间复杂度为o(n2)。2(1)(4)14njjnnnd2(1)(8)(1)(1)4njjnnnnd最好情况下，排序前记录已经按关键词从小到大有序排列，每趟只需与前面的有序部分的最后一个记录的关键词比较1次，记录移动2次，总的关键词比较次数为n-1，记录移动次数为2(n-1)。最坏情况下:第i趟时第i个记录前面的所有记录的关键词都比第i个记录的关键词大，即dj取最大值，因此必须与前面i-1个记录都做关键词比较，并且每做1次比较就要做1次记录移动。则总的关键词比较次数为2211)1(22nndndnjnjjj记录移动次数为241112nndnnnjj比较次数记录移动次数最好n–12n–2平均4)4)(1(nn4)8)(1(nn最坏2)2)(1(nn2)4)(1(nn直接插入排序算法优点:是算法的执行过程相当清晰，并且书写容易.缺点:期望复杂性为O(n2).稳定性：直接插入排序是稳定的排序方法。最好情况是：当被排序文件初态为正序时，算法的时间复杂度为O(n).辅助空间：O(1)一种改进的方法是对半插入法，即在插入第j个元素时，不是像直接插人排序那样顺序寻找插入的位置，而是采用对半（或二分）的方法25*1621254908123456temp16j=5i=2123456temp2516214925*081625j=5i=1123456temp21254925*081621j=5i=01616希尔排序●希尔排序（渐减增量排序法）思想：把记录按下标的一定增量分组，对每组使用直接插入排序法，随着增量逐渐减少，所分成的组包含的关键词越来越多，到增量值减至1时，整个文件恰好被分成一个组，算法便告终止.●希尔排序增量的取法(16条记录)：d1===8∟n/2∟∟16/2∟d2===4∟d1/2∟∟8/2∟d3===2∟d2/2∟∟4/2∟d4===1∟d3/2∟∟2/2∟输入文件包含16个记录.取渐减增量序列如下：8，4，2，1增量值为8时的排序503087512061908170897275653426154509612677765703增量值为4时的排序503087154061612170765275653426512509908677897703增量值为2时的排序503087154