数据结构JAVA语言描述习题答案(刘小晶等主编).第7章-排序(Java版)

1,第七章排序,教学内容,7.1排序的基本概念,7.2插入排序,7.3交换排序,7.4选择排序,7.5归并排序,7.6基数排序,教学重点与难点,重点：,掌握排序的基本概念以及各种常见排序方法的实现。,难点：,希尔排序、快速排序、归并排序和堆排序等高效排序方法。,4,【课前思考】,1.熟悉排序吗？过去曾经学过哪些排序方法？,在第一章中曾以选择排序和起泡排序为例讨论算法实际复杂度,2.自己有没有编过排序的程序？是用的什么策略？,5,1、排序的定义,3、内部排序的方法,4、排序算法的性能评价,5、待排序记录的类描述,2、排序的分类,7.1排序的基本概念,6,1、排序的定义,排序是计算机内经常进行的一种操作，是将一组“无序”的记录序列调整为“有序”的记录序列的一种操作。,例如：将下列关键字序列,52,49,80,36,14,58,61,23,97,75,调整为,14,23,36,49,52,58,61,75,80,97,7,严格定义如下：一般情况下，假设含n个记录的序列为R0,R1,，Rn-1其相应的关键字序列为K0,K1,，Kn-1,这些关键字相互之间可以进行比较，且在它们之间存在着这样一个关系：Kp1Kp2Kpn,按此固有关系将上式记录序列重新排列为Rp1,Rp2,，Rpn的操作称作排序。,1、排序的定义,8,关键字,是数据元素（或记录）中某个数据项的值，用以标识（识别）一个数据元素（或记录）。,若此关键字可以识别唯一的一个记录，则称之谓“主关键字”。,若此关键字能识别若干记录，则称之谓“次关键字”。,9,2、排序的分类,(1)按排序过程中所涉及到的存储器不同分为：,(2)按相同关键字在排序前后的位置不同分为：,稳定排序,内部排序,外部排序,不稳定排序,假设Ki=Kj（ij),且在排序前的序列中Ri领先于Rj（即ij)。若在排序后的序列中Ri仍领先于Rj，则称所用的排序方法是稳定的；反之，则称所用的排序方法是不稳定的。,10,3、内部排序的方法,内部排序的过程是一个逐步扩大记录的有序序列长度的过程。,经过一趟排序,有序序列区,无序序列区,有序序列区,无序序列区,11,基于不同的“扩大”有序序列长度的方法，内部排序方法大致可分下列几种类型：,插入类,交换类,选择类,归并类,其它方法,3、内部排序的方法,12,(1)插入类,将无序子序列中的一个或几个记录“插入”到有序序列中，从而增加记录的有序子序列的长度。,13,(2)交换类,通过“交换”无序序列中的记录从而得到其中关键字最小或最大的记录，并将它加入到有序子序列中，以此方法增加记录的有序子序列的长度。,14,(3)选择类,从记录的无序子序列中“选择”关键字最小或最大的记录，并将它加入到有序子序列中，以此方法增加记录的有序子序列的长度。,15,(4)归并类,通过“归并”两个或两个以上的记录有序子序列，逐步增加记录有序序列的长度。,(5)其它方法,就各类介绍一二个典型算法。,如：基数排序,下面就各类介绍一二个典型算法。,16,4、排序算法的性能评价,时间,空间：,指所需辅助空间的大小,稳定性,17,内部排序的时间分析：,实现内部排序的基本操作有两个：,（2）“移动”记录。,（1）“比较”序列中两个关键字的大小；,18,待排序的顺序表记录类描述如下:(P242)publicclassRecordNodeprivateComparablekey;/关键字privateObjectelement;/数据元素备注：1.key为Comparable接口类型，它能够赋值为任何实现Comparable接口类的对象。2.element为Object类型，在实际应用时，可根据不同问题定义为不同的具体类。,5、待排序记录的类描述,19,待排序的顺序表类(P243),publicclassSeqListprivateRecordNoder;/顺序表记录结点数组privateintcurlen;/顺序表长度，即记录个数/构造方法:构造一个存储空间容量为maxSize的顺序表publicSeqList(intmaxSize)this.r=newRecordNodemaxSize;/为顺序表分配maxSize个存储单元this.curlen=0;/置顺序表的当前长度为0,20,总思想：,每次将一个待排序的记录，按其关键字值的大小插入到前面已排序好的记录序列中的适当位置，直到全部记录插入完成为止。,7.2插入排序,21,有序序列r0.i-1,Ri,无序序列ri.n-1,一趟插入排序的基本思想：,有序序列r0.i,无序序列ri+1.n-1,22,实现“一趟插入排序”可分三步进行：,3将ri插入(复制)到rj+1的位置上。,2将rj+1.i-1中的所有记录均后移一个位置；,1在r0.i-1中查找ri的插入位置，r0.j.keyri.key=0”用来控制下标越界。为了提高算法效率，可对该算法进行如下改进：首先将待排序的n条记录从下标为1的存储单元开始依次存放在数组r中，再将顺序表的第0个存储单元设置为一个“监视哨”，即在查找之前把ri赋给r0，这样每循环一次只需要进行记录的比较，不需要比较下标是否越界,7.2.1直接插入排序-带监视哨的算法,29,例：,初始关键字：,（43）21891543,直接插入排序示例,r0r1r2r3r4r5,4321891543,30,从ri-1起向前进行顺序查找，监视哨设置在r0；,r0=ri;/设置“哨兵”,循环结束表明ri的插入位置为j+1,r0,j,ri,for(j=i-1;r0.getKeyrj.getKey;-j);/从后往前找,j=i-1,插入位置,如何查找到ri的插入位置？,7.2.1直接插入排序-带监视哨的算法,31,对于在查找过程中找到的那些关键字不小于Ri.key的记录，在查找的同时实现记录向后移动；,for(j=i-1;r0.getKeyrj.getKey;-j)rj+1=rj；,r0,j,ri,j=i-1,上述循环结束后可以直接进行“插入”,插入位置,后移并插入,7.2.1直接插入排序-带监视哨的算法,32,令i=2，,curlen-1,实现整个序列的排序。,for(i=2;i=curlen;+i)在r0.i-1中查找ri的插入位置;插入ri;,7.2.1直接插入排序-带监视哨的算法,33,voidinsertSortWithGuard()()/对顺序表作直接插入排序。for(i=2;i=this.curlen;+i),r0=ri;/复制为监视哨for(j=i-1;r0.getKey().compareTo(rj.getKey()0;j-)rj+1=rj;/记录后移rj+1=r0;/插入到正确位置,7.2.1直接插入排序-带监视哨的算法,P245算法7.2,34,不带监视哨的直接插入排序性能分析：,最好的情况（关键字在记录序列中顺序有序）：,“比较”的次数：,最坏的情况（关键字在记录序列中逆序有序）：,“比较”的次数：,0,“移动”的次数：,“移动”的次数：,35,平均值：约n2/4,.直接插入排序的时间复杂度：,2.只需记录的辅助空间,.是的排序方法,一个,稳定,O（n2),7.2.1直接插入排序-性能分析,36,（又称缩小增量排序）,基本思想：对待排记录序列先作“宏观”调整，再作“微观”调整。,所谓“宏观”调整，指的是，“跳跃式”的插入排序。具体做法为：,7.2.2希尔排序,37,将记录序列分成若干子序列，分别对每个子序列进行插入排序。,其中，d称为增量，它的值在排序过程中从大到小逐渐缩小，直至最后一趟排序减为1。,例如：将n个记录分成d个子序列：r0，r0+d，r0+2d，r0+kdr1，r1+d，r1+2d，r1+kdrd1，r2d1，r3d1，rd+kd-1,7.2.2希尔排序,38,例1：初始关键字序列如下：,49，38，65，97，76，13，27，49，5504，请写出它们的希尔排序的全过程(其中d=5,3,1）,7.2.2希尔排序,Page39,初始关键字：49,38,65,97,76,13,27,49,55,4,取d3=1三趟分组：,三趟排序结果：,一趟排序结果：,二趟排序结果：,取d1=5一趟分组：,取d2=3二趟分组：,不稳定的排序方法,40,publicvoidshellSort(intd)RecordNodetemp;inti,j;for(intk=0;k=0,P247算法7.3,7.2.2希尔排序-算法,41,.希尔排序的时间复杂度：不确定，但在插入排序中，希尔排序的效能最高，最好情况可达O（nlog2n),.是的排序方法,例：对序列2，1，1进行希尔排序（d分别取2,1时）结果：1，1，2,不稳定,2.只需记录的辅助空间,一个,7.2.2希尔排序-性能分析,42,1.冒泡排序,2.快速排序,7.2交换排序,43,1.基本思想：,将待排序的数组看成从上到下的存放，把关键字较小的记录看成“较轻的”，关键字较大的记录看成“较重的”，小关键字的记录好像水中的气泡一样，向上浮；大关键字的记录如水中的石块向下沉，当所有的气泡都浮到了相应的位置，且所有的石块都沉到了水中，排序就结束了。,7.3.1冒泡排序,44,从第一个记录开始，依次对无序区中相邻记录进行关键字比较，如果大在上，小在下，则交换，第一趟扫描下来表中最大的沉在最下面。然后再对前n-1个记录进行冒泡排序，直到排序成功为止。,一般地，第i趟扫描时,r0到rn-i和rn-i+1到rn1分别为当前的无序区和有序区。,2.基本步骤,7.3.1冒泡排序,45,假设在排序过程中，记录序列r0.n-1的状态为：,第i趟起泡排序,无序序列r0.n-i,有序序列rn-i+1.n-1,n-i+1,无序序列r0.n-i+1,有序序列rn-i+1.n-1,比较相邻记录，将关键字最大的记录交换到n-i+1的位置上,例1：写出对关键字序列43，21，89，15，28，43进行冒泡排序的各趟结果,7.3.1冒泡排序,46,985420,895420,859420,854920,854290,854209,大数沉淀，小数起泡,a0a1a2a3a4a5,for(i=0;iai+1)t=ai;ai=ai+1;ai+1=t;,47,854209,584209,548209,542809,542089,a0a1a2a3a4a5,for(i=0;iai+1)t=ai;ai=ai+1;ai+1=t;,48,542089,452089,425089,420589,a0a1a2a3a4a5,for(i=0;iai+1)t=ai;ai=ai+1;ai+1=t;,49,420589,240589,204589,a0a1a2a3a4a5,for(i=0;iai+1)t=ai;ai=ai+1;ai+1=t;,50,204589,024589,a0a1a2a3a4a5,for(i=0;iai+1)t=ai;ai=ai+1;ai+1=t;,51,for(i=0;iai+1),for(i=0;iai+1),for(i=0;iai+1),for(i=0;iai+1),for(j=1;jai+1,则将二者交换，以后重复上述二趟过程交换进行，直至整个数组有序。a)试问排序结束的条件是什么？b)实现上述排序过程的算法如何？,56,最好的情况（关键字在记录序列中顺序有序）：只需进行一趟起泡,“比较”的次数：,最坏的情况（关键字在记录序列中逆序有序）：需进行n-1趟起泡,“比较”的次数：,0,“移动”的次数：,“移动”的次数：,n-1,7.3.1冒泡排序-性能分析：,57,.起泡排序的时间复杂度：O（n2),2.只需一个记录的辅助空间O(1),.是稳定的排序方法,7.3.1冒泡排序-性能分析：,58,通过一趟排序将要排序的记录分割成独立的两个部分，其中一部分的所有记录的关键字值都比另外一部分的所有记录关键字值小，然后再按此方法对这两部分记录分别进行快速排序，整个排序过程可以递归进行，以此达到整个记录序列变成有序。,7.3.2快速排序,基本思想：,59,找一个记录，以它的关键字作为“枢轴”，凡其关键字小于枢轴的记录均移动至该记录之前，反之，凡关键字大于枢轴的记录均移动至该记录之后。,致使一趟排序之后，记录的无序序列rs.t将分割成两部分：rs.i-1和ri+1.t，且rj.getKey()ri.getKey()rj.getKey()(sji-1)枢轴(i+1jt)。,7.3.2快速排序-一趟快速排序,1.目标：,60,无序的记录序列,无序记录子序列(1),无序子序列(2),枢轴,通过一趟快速排序后,（一次划分）,7.3.2快速排序-一趟快速排序,61,low,high,i,j,设rs=52为枢轴,将rj.getKey()和枢轴关键字进行比较,要求rj.getKey()枢轴的关键字；,将ri.getKey()和枢轴关键字进行比较，要求ri.getKey()枢轴的关键字。,j,23,i,80,j,14,i,52,prvot,52,j,j,j,i,7.3.2快速排序-一趟快速排序,i,Page62,27,初始关键字：,65,13,97,49,不稳定的排序方法,63,可见，经过“一次划分”，将关键字序列52,49,80,36,14,58,61,97,23,75调整为:23,49,14,36,(52)58,61,97,80,75,在调整过程中，设立了两个变量：i和j，它们的初值分别为：low和high，,之后逐渐减小j，增加i，并保证rj.getKey()52，和ri.getKey()52,否则进行记录的“交换”。,7.3.2快速排序-一趟快速排序,64,以首结点为枢轴,考虑的结点序列为rlow，rlow+1，rhigh,且lowpivot,那么j=j-1,转(a)；否则ri=rj，i=i+1,转（b）(b)若ri.getKey()=pivot,那么i=i+1，转(b)；否则rj=ri,j=j-1,转2）3）如果i=j，则ri=pivot，算法结束。,2.算法基本步骤：,7.3.2快速排序-一趟快速排序,65,intPartition(inti,intj)/一趟快速排序算法7.5/Partition,RecordNodepivot=ri;/枢轴,while(ij),while(ij/从右向左搜索,if(ij)ri+=rj;,while(i0)i+;/从左向右搜索,if(ij)rj-=ri;,ri=pivot;returni;,66,再例如：根据算法步骤写出对关键字序列26，37，08，63，12，59，12，48进行快速排序的第一趟排序过程和每一趟排序结果。,67,3、快速排序,首先对无序的记录序列进行“一次划分”，之后分别对分割所得两个子序列“递归”进行快速排序。,无序的记录序列,无序记录子序列(1),无序子序列(2),枢轴,一次划分,分别进行快速排序,68,publicvoidqSort(intlow,inthigh)if(lowhigh)intpivotloc=Partition(low,high);/一趟排序，将排序表分为两部分qSort(low,pivotloc-1);/低子表递归排序qSort(pivotloc+1,high);/高子表递归排序,算法7.6递归形式的快速排序算法(P251),69,voidQuickSort()/对顺序表进行快速排序qSort(0,curlen-1);/QuickSort,第一次调用函数Qsort时，待排序记录序列的上、下界分别为0和curlen-1。,70,快速排序的性能分析,假设一次划分所得枢轴位置i=k，则对n个记录进行快排所需时间：,其中Tpass(n)为对n个记录进行一次划分所需时间。,若待排序列中记录的关键字是随机分布的，则k取1至n中任意一值的可能性相同。,T(n)=Tpass(n)+T(k-1)+T(n-k),71,设Tavg(1)b,则可得结果：,由此可得快速排序所需时间的平均值为：,72,1)快速排序的时间复杂度为:2)所需辅助空间3）是排序,O(nlog2n)是内部排序中性能最好的一种。,O（log2n）,不稳定,7.3.2快速排序-性能分析,73,若待排记录的初始状态为按关键字有序时，快速排序将蜕化为起泡排序，其时间复杂度为O(n2)。,为避免出现这种情况，需在进行一次划分之前，进行“预处理”，即：,先对R(s).key,R(t).key和R(s+t)/2.key，进行相互比较，然后取关键字为“三者取中”的记录为枢轴记录。,7.3.2快速排序,74,直接选择排序,树形选择排序,堆排序,7.4选择排序,75,1.基本思想,首先在所有记录中选出关键字值最小的记录，把它与第一个记录进行位置交换，然后在其余的记录中再选出关键字值次小的记录与第二个记录进行位置交换，依此类推，直到所有记录排好序。,7.4.1直接选择排序,76,假设排序过程中，待排记录序列的状态为：,有序序列R1.i-1,无序序列Ri.n,第i趟简单选择排序,从中选出关键字最小的记录,有序序列R1.i,无序序列Ri+1.n,7.4.1直接选择排序,77,例：写出对关键字系列4938659776132749进行选择排序的每一趟结果。,7.4.1直接选择排序,Page78,i=1,13,49,i=2,27,38,i=3,i=4,i=5,i=6,38,65,49,97,76,65,97,76,97,排序结束,79,2.基本步骤：,（1）置i为0。（2）当in-1，重复下列步骤：.a.在（Ri,Rn-1）中选出一个关键字值最小的记录Rk；b.若Rk不是Ri,(即k!=i），交换Ri,Rk的位置，否则不进行交换；c.i值加1。,80,直接选择排序的算法描述如下：,voidSelectSort()/对顺序表作简单选择排序。for(i=0;ilength-1;+i)/选择第i小的记录，并交换到位/SelectSort,j=SelectMinKey(R,i);/在Ri.n中选择关键字最小的记录,if(i!=j)RiRj;/与第i个记录交换,81,publicvoidselectsort()/算法7.8RecordNodetemp;for(inti=0;ithis.curlen-1;i+)if(min!=i)temp=ri;ri=rmin;rmin=temp;,intmin=i;for(intj=i+1;j0;i-)temp=r0;r0=ri;ri=temp;sift(0,i-1);,99,堆排序的时间复杂度分析：,1.对深度为k的堆，“筛选”所需进行的关键字比较的次数至多为2(k-1)；,3.调整“堆顶”n-1次，总共进行的关键字比较的次数不超过2(log2(n-1)+log2(n-2)+log22)2n(log2n),因此，堆排序的时间复杂度为O(nlogn)。,2.对n个关键字，建成深度为h(=log2n+1)的堆，所需进行的关键字比较的次数至多4n；,100,结论:1)堆排序的时间复杂度为2)所需辅助空间3）是排序,O(nlog2n),O(1),不稳定,101,归并排序的过程基于下列基本思想进行：将两个或两个以上的有序子序列“归并”为一个有序序列。,7.5归并排序,102,在内部排序中，通常采用的是2-路归并排序。即：将两个位置相邻的记录有序子序列,归并为一个记录的有序序列。,有序序列rl.n,有序子序列rl.m,有序子序列rm+1.n,这个操作对顺序表而言，是轻而易举的。,7.5归并排序,103,2-路归并的方法,将待排序记录R0到Rn-1看成是n个长度为1的有序子表，把这些子表依次两两归并，便得到n/2个有序的子表，然后，再把这n/2个有序的子表两两归并，如此重复，直到最后得到一个长度为n的有序表为止。,7.5归并排序,104,例如，如下图为2-路归并的一个例子：,(52)(23)(80)(36)(68)(14)(27),(2352)(3680)(1468)(27),(23365280)(142768),(14232736526880),一趟归并之后,二趟归并之后,三趟归并之后,7.5归并排序,105,归并排序的算法,如果记录无序序列Rs.t的两部分Rs.(s+t)/2和R(s+t)/2+1.t分别按关键字有序，则利用上述归并算法很容易将它们归并成整个记录序列是一个有序序列。,由此，应该先分别对这两部分进行2-路归并排序。,106,例如：,52,23,80,36,68,14(s=1,t=6),52,23,8036,68,14,52,2380,52,23,52,23,52,80,36,6814,3668,36,68,14,36,68,14,23,36,52,68,80,23,107,容易看出，对n个记录进行归并排序的时间复杂度为(nlogn)。即：每一趟归并的时间复杂度为O(n)，总共需进行log2n趟。,108,结论：1)归并排序的时间复杂度为2)所需辅助空间3）是排序,O(n),稳定,O(nlog2n),7.5归并排序-性能分析,109,基数排序是一种借助“多关键字排序”的思想来实现“单关键字排序”的内部排序算法。,多关键字的排序,链式基数排序,7.6基数排序,110,7.6.1多关键字的排序,n个记录的序列R1,R2,，Rn对关键字(Ki0,Ki1,Kid-1)有序是指：,其中:K0被称为“最主”位关键字,Kd-1被称为“最次”位关键字,对于序列中任意两个记录Ri和Rj(1ijn)都满足下列(词典)有序关系：(Ki0,Ki1,Kid-1)(Kj0,Kj1,Kjd-1),111,实现多关键字排序通常有两种作法:,最次位优先LSD法,最主位优先MSD法,7.6.1多关键字的排序,112,先对K1进行排序，并按K1的不同值将记录序列分成若干子序列之后，分别对K2进行排序，.，依次类推，直至最后对最次位关键字排序完成为止。,7.6.1多关键字的排序-MSD法,113,先对Kd进行排序，然后对Kd-1进行排序，依次类推，直至对最主位关键字K1排序完成为止。,排序过程中不需要根据“前一个”关键字的排序结果，将记录序列分割成若干个(“前一个”关键字不同的)子序列。,7.6.1多关键字的排序-LSD法,114,例如:学生记录含三个关键字:系别、班号和班内的序列号，其中以系别为最主位关键字。,无序序列,对K2排序,对K1排序,对K0排序,3,2,30,1,2,15,3,1,20,2,3,18,2,1,20,1,2,15,2,3,18,3,1,20,2,1,20,3,2,30,3,1,20,2,1,20,1,2,15,3,2,30,2,3,18,1,2,15,2,1,20,2,3,18,3,1,20,3,2,30,LSD的排序过程如下:,7.6.1多关键字的排序,115,7.6.2链式基数排序,假如多关键字的记录序列中，每个关键字的取值范围相同，则按LSD法进行排序时，可以采用“分配-收集”的方法，其好处是不需要进行关键字间的比较。,对于数字型或字符型的单关键字，可以看成是由多个数位或多个字符构成的多关键字，此时可以采用这种“分配-收集”的办法进行排序，称作基数排序法。,116,例如：对下列这组关键字209,386,768,185,247,606,230,834,539,首先按其“个位数”取值分别为0,1,9“分配”成10组，之后按从0至9的顺序将它们“收集”在一起；,然后按其“十位数”取值分别为0,1,9“分配”成10组，之后再按从0至9的顺序将它们“收集”在一起；,最后按其“百位数”重复一遍上述操作。,7.6.2链式基数排序,117,在计算机上实现基数排序时，为减少所需辅助存储空间，应采用链表作存储结构，即链式基数排序，具体作法为：,1)待排序记录以指针相链，构成一个链表；,)“分配”时，按当前“关键字位”所取值，将记录分配到不同的“链队列”中，每个队列中记录的“关键字位”相同；,)“收集”时，按当前关键字位取值从小到大将各队列首尾相链成一个链表;,)对每个关键字位均重复2)和3)两步。,7.6.2链式基数排序,118,例如：,p369367167239237138230139,进行第一次分配,进行第一次收集,f0r0,f7r7,f8r8,f9r9,p230,230,367,167,237,367167237,138,368239139,369,239,139,138,7.6.2链式基数排序,119,进行第二次分配,p230237138239139,p230367167237138368239139,f3r3,f6r6,230,237,138,239,139,367,167,368,367167368,进行第二次收集,7.6.2链式基数排序,120,进行第三次收集之后便得到记录的有序序列,f1r1,p230237138239139367167368,进行第三次分配,f2r2,f3r3,138,139,167,230,237,239,367,368,p138139167,230237239,367368,7.6.2链式基数排序,121,提醒注意：,“分配”和“收集”的实际操作仅为修改链表中的指针和设置队列的头、尾指针；,为查找使用，该链表尚需将它调整为有序表。,7.6.2链式基数排序,122,基数排序的时间复杂度为O(d(n+rd),其中：每一趟分配的时间复杂度为O(n)每一趟收集的时间复杂度为O(rd)(r为关键字的“基”，如十进制数的基为10，二进制数的基为2)d为“分配-收集”的趟数（等于关键字的位数）,基数排序是稳定排序。,基数排序所需用的计算时间不仅与文件的大小n有关，而且还与关键字的位数、关键字的基有