数据结构答案第10章排序学习与指导.docVIP

第10章 排序10.1 知识点分析1排序基本概念：（1）排序 将数据元素的任意序列，重新排列成一个按关键字有序（递增或递减）的序列的过程称为排序。（2）排序方法的稳定和不稳定若对任意的数据元素序列，使用某个排序方法，对它按关键字进行排序，若对原先具有相同键值元素间的位置关系，排序前与排序后保持一致，称此排序方法是稳定的；反之，则称为不稳定的。（3）内排序整个排序过程都在内存进行的排序称为内排序，本书仅讨论内排序。（4）外排序待排序的数据元素量大，以致内存一次不能容纳全部记录，在排序过程中需要对外存进行访问的排序称为外排序。2直接插入排序直接插入排序法是将一个记录插到已排序好的有序表中，从而得到一个新的，记录数增1的有序表。3二分插入排序 二分插入排序法是用二分查找法在有序表中找到正确的插入位置，然后移动记录，空出插入位置，再进行插入的排序方法。4希尔排序希尔排序的基本思想是：先选取一个小于n的整数d1作为第一个增量，把待排序的数据分成d1个组，所有距离为d1的倍数的记录放在同一个组内，在各组内进行直接插入排序，每一趟排序会使数据更接近于有序。然后，取第二个增量d2，d2 d1，重复进行上述分组和排序，直至所取的增量di=1（其中di di-1 d2 d1），即所有记录在同一组进行直接插入排序后为止。5冒泡排序 冒泡法是指每相邻两个记录关键字比大小，大的记录往下沉（也可以小的往上浮）。每一遍把最后一个下沉的位置记下，下一遍只需检查比较到此为止；到所有记录都不发生下沉时，整个过程结束。6快速排序 快速排序法是通过一趟排序，将待排序的记录组分割成独立的两部分，其中前一部分记录的关键字均比枢轴记录的关键字小；后一部分记录的关键字均比枢轴记录的关键字大，枢轴记录得到了它在整个序列中的最终位置并被存放好。第二趟再分别对分割成两部分子序列，再进行快速排序，这两部分子序列中的枢轴记录也得到了最终在序列中的位置而被存放好，并且它们又分别分割出独立的两个子序列。7简单选择排序（1）初始状态：整个数组r划分成两个部分，即有序区（初始为空）和无序区。（2）基本操作：从无序中选择关键字值最小的记录，将其与无序区的第一个记录交换（实质是添加到有序区尾部）。（3）从初态（有序区为空）开始，重复步骤（2），直到终态（无序区为空）。8堆排序（1）把用数组来存储待排序的记录，将R1.n看成是一棵完全二叉树。（2）利用完全二叉树双亲结点和孩子结点之间的内在关系，将其建成堆，从而在当前无序区中选择关键字最大的记录，然后将最大的关键字取出。（3）对剩下的关键字再建堆，得到次大的关键字。如此反复进行，直到最小值，从而将全部关键字排序好为止。9归并排序归并排序是将两个或两个以上的有序子表合并成一个新的有序表。其基本思想是：（1）将n个记录的待排序序列看成是有n个长度都为1的有序子表组成。（2）将两两相邻的子表归并为一个有序子表。（3重复上述步骤，直至归并为一个长度为n的有序表。10各种排序方法的比较评估一个排序法的好坏，除了用排序的时间及空间外，尚需考虑稳定度、最坏状况和程序的编写难易程度。以下就常用的排序法按最坏情况下所需时间、平均所需时间、是否属于稳定排序、所需的额外空间等以表10-1来表示。 10-1 排序性能比较表排序法最坏所需时间平均所需时间稳定性所需的额外空间直接插入O (n 2)O (n 2)YesO (1)希尔排序O (n 2)O (n1.3)NoO (1)冒泡排序O (n 2)O (n 2)YesO (1)快速排序O (n 2)O (nlog2n)NoO (log2n)选择排序O ( n 2)O (n 2)YesO (1)堆排序O (nlog2n)O (nlog2n)NoO (1)归并排序O (nlog2n)O (nlog2n)YesO (n)10.2 典型习题分析【例1】 当初始序列已按关键字有序时，用直接插入算法进行排序，需要比较次数为（ ）。An-1 Blog2n C2log2n Dn2分析：直接插入排序是每趟从待排序列中取一个元素，按关键字从有序区间的尾部向前查找插入位置。当初始序列已按关键字值有序时，则每趟比较一个就找到了正确位置，也就是本身位置，则n个元素需要进行n-1趟排序，故总的比较为n-1次，答案为A。【例2】一组记录的键值为（12，38，35，25，74，50，63，90），按2路归并排序方法对该序列进行一趟归并后的结果为（ ）。A12,38,25,35,50,74,63,90 B12,38,35,25,74,50,63,90C12,25,35,38,50,74,63,90 D12,35,38,25,63,50,74,90分析：2路归并排序是将两个有序子表合并成一个新的有序表。其基本思想是：（1）将n个记录的待排序序列看成是有n个长度都为1的有序子表组成；（2）将两两相邻的子表归并为一个有序子表；（3）重复上述步骤，直至归并为一个长度为n的有序表。 初始值 12 38 35 25 74 50 63 90第一趟排序结果：12 38 25 35 50 74 63 90 答案为A。【例3】待排序的记录初态是按码值降序排列的，若欲将其按码值升序重新排列，则直接插入排序、简单选择排序和冒泡排序哪一个更好? 解： 当待排序的记录初态是按码值降序排列时，用冒泡排序法比较和交换的次数最多；而直接插入排序和简单选择排序的比较次数相近。但是直接插入排序时记录的移动次数比较多。所以，当待排序的记录初态是按码值降序排列，要按码值升序重新排列时，用简单选择排序更好。【例4】设待排序记录的初态是按关键字值递增排列的，分别用堆排序、快速排序、冒泡排序和归并排序方法对其仍按递增进行排序，则哪种排序方法最省时间？哪种排序方法最费时间？解： 堆排序和归并排序所用时间复杂度为O(nlog2n)；当待排记录的初始状态是按关键字值递增时，用快速排序法，因为每次选取的中间元素都是最小的，故划分出的左右两个区域一个为空，另一个比原区域少一个元素，使得元素比较只比上一趟少一次，所以总的时间复杂度为O(n2)；对于冒泡排序来说，其平均所需时间和最坏所需时间都是O(n2)，但是如果在算法中设置一个标志flag，用于记录每趟排序中是否出现记录的交换。如果没有交换，则表明待排序序列已经有序，则可结束排序。综上所述本题采用这样冒泡排序所用时间最省；采用快速排序最费时间。【例5】设有n个互不相同的元素，试问能否用少于2n-3次的比较次数，从这n个关键字中选出最大元素和最小元素？ 解： 若采用先选最小元素（通过n-1次比较得到），再在剩余的n-1个元素中选最大元素（通过n-2次比较得到）的方法，则共需要 (n-1)+(n-2)=2n-3次比较。可以通过成对比较元素，来减少比较次数。具体方法如下：先比较第1对元素，较小者送当前最小变量min，较大者送当前最大变量max；然后依次对第i对元素（i=2，3，），进行比较。对于每一对元素，做一次比较（大小）以后，分别将较小者和当前最小元素变量min比较；将较大者和当前最大元素变量max比较（共比较3次）。若较小者小于min，则令较小者取代当前的min；若较大者大于max，则令较大者取代当前的max。待所有元素比较完成以后，max和min分别就是最大元素和最小元素。因为第1对元素只比较了1次，其余的各对元素分别都需要进行3次比较，所以总的比较次数是：1+(-1)3=3-2，显然小于2n-3次。【例6】已知序列（503，87，512，61，908，170，897，275，653，462）请给出采用快速排序法作升序排序时的第一趟的结果。分析：设待排序列的下界和上界分别为low和high，Rlow是枢轴元素，一趟快速排序的具体过程如下：（1）首先将Rlow中的记录保存到pivot变量中，用两个整型变量i，j分别指向low和high所在位置上的记录；（2）先从j所指的记录起自右向左逐一将关键字和pivot.key进行比较，当找到第1个关键字小于pivot.key的记录时，将此记录复制到i所指的位置上去；（3）然后从i+1所指的记录起自左向右逐一将关键字和pivot.key进行比较，当找到第1个关键字大于pivot.key的记录时，将该记录复制到j所指的位置上去；（4）接着再从j-1所指的记录重复以上的（2）、（3）两步，直到i=j为止，此时将pivot中的记录放回到i（或j）的位置上。一趟快速排序完成。 排序过程如下： 503 87 512 61 908 170 897 275 653 462 交换 462 87 512 61 908 170 897 275 653 503 交换 462 87 503 61 908 170 897 275 653 512 交换 462 87 275 61 908 170 897 503 653 512 交换462 87 275 61 503 170 897 908 653 512 交换462 87 275 61 170 503 897 908 653 512第一趟快速排序结果是462，87，275，61，170，503，897，908，653，512。【例7】在快速排序法中，当Rlow.high中的关键字有序时，Partition（int i,int j）（参考教材P242-243快速排序算法）的返回值是什么？此时快速排序的运行时间是多少？应该如何修改，才能使得划分的结果是平衡的？ 分析：如果Rlow.high中的关键字是递增有序的，则Partition返回值是low；如果Rlow.high中的关键字是递减有序，则Partition返回值是high。在这两种情况下，快速排序的运行时间均为：O(n2)。要使划分的结果仅可能平衡，应选取其中间位置上的记录作为划分的基准为宜。我们可以通过修改Partition来实现：在进入扫描循环之前，取R(low+high)/2作为划分元，将其与Rlow交换，然后进入扫描循环。但是，若Rlow.high中的所有关键字均相同，则该方法仍然不能奏效，此时可以采用如下算法：int Partition(SeqList R,int *i,int *j) int pivot=R(*i+*j)/2.key; / *i和*j是当前无序区的下界和上界 RecType temp;while(*i=*j)while(R*i.keypirot) (*j)-;if(*i=*j) temp=R*i;R*i=R*j;R*j=temp; (*i)+;(*j)-;void QuickSort(SeqList R,int low,int high) / 递归形式的快速排序int i=low,j=high;if(lowhigh) Partition(R,&i,$j); / 调用Partition()函数QuickSort(R,low,j); / 对低子表递归排序QuickSort(R,i,high); / 对高子表递归排序 【例8】利用一维数组a可以对n个整数进行排序，其中一种排序算法的处理思想是：将n个整数分别作为数组a的n个元素的值，每次（即第i次）从元素ai到an中挑出最小的一个元素ak(ikn)，然后将ak与ai换位。这样反复n-1次完成排序。编写实现上述算法的函数：void sort(int a,int n)。分析：本排序法为直接选择排序法，算法如下：void sort(int a,int n) / 对数组a 中n个元素进行直接选择排序 int i,j,x,m; for(i=1;i=n-1;i+) min=i; / min保存当前最小元素下标，初始值为ifor(j=i+1;j=n;j+) / 从下一个元素到最后一个元素，找最小元素，并把下标存放在min if (aj=0;i-) if (Ri.keyRi+1.key) Rn=Ri; / Rn是哨兵j=i+1;do Rj-1=Rj; / 将关键字小于Ri.key的记录向右移j+;while(Rj.key Ai+1，则交换它们。第三趟有对所有的奇数项，第四趟对所有的偶数项，如此反复，直到整个序列全部排好序为止。分析：根据题目要求，可设一个布尔变量BL，判断在每一次做过一趟奇数项扫描和一趟偶数项扫描后是否有过交换。若BL为1，表示刚才有过交换，还需继续做下一趟奇数项扫描和一趟偶数项扫描；若BL为0，表示刚才没有交换，可以结束排序。算法如下：OddEvenSort ( int Vector ,int n) int i, BL,temp;do BL = 0; for ( i = 1; i Vectori+1 ) / 相邻两项比较, 发生逆序 BL = 1; / 作交换标记 temp=Vectori; / 交换Vectori=Vectori+1;Vectori+1=temp; for ( i = 0; i Vectori+1 ) / 相邻两项比较, 发生逆序 BL = 1; / 作交换标记 temp=Vectori; / 交换Vectori=Vectori+1;Vectori+1=temp; while ( BL != 0 );10.3 单元练习9解答一判断题答案 题目123456789101112答案二填空题答案（1） 比较（2） 时间复杂度（3） 内排序（4） 外存（5） n-1（6） i-1（7） O(n2)（8） O(n2)（9） O(log2n)（10） O(n)（11） 快速排序（12） 不变（13） 插入排序（14） 直接插入（15） 冒泡排序（16） 直接插入（17） 选择排序（18） 3 （19） L2（20） 54，72，60，96，80 三选择题答案题目12345678910答案ADBBDCCDBC题目11121314151617181920答案AAAABCBBAC四排序过程分析答案（1） 10 8 18 15 7 16第一趟结束时结果： 8 10 18 15 7 16第二趟结束时结果： 8 10 18 15 7 16第三趟结束时结果： 8 10 15 18 7 16第四趟结束时结果： 7 8 10 15 18 16第五趟结束时结果： 7 8 10 15 16 18（2） 18 17 60 40 07 32 73 65第一趟结束时结果： 17 18 60 40 07 32 73 65第二趟结束时结果： 17 18 60 40 07 32 73 65第三趟结束时结果： 17 18 40 60 07 32 73 65第四趟结束时结果： 07 17 18 40 60 32 73 65第五趟结束时结果： 07 17 18 32 40 60 73 65第六趟结束时结果： 07 17 18 32 40 60 73 65第七趟结束时结果： 07 17 18 32 40 60 65 73 （3） 17 18 60 40 7 32 73 65 85第一趟排序结果： 17 18 40 7 32 60 65 73 85第二趟排序结果： 17 18 7 32 40 60 65 73第三趟排序结果： 17 7 18 32 40 60 65第四趟排序结果： 7 17 18 32 40 60第五趟排序结果： 7 17 18 32 40第五趟排序过程中已无记录交换，排序结束。（4） 80 18 09 90 27 75 42 69 34第一趟排序结果： 18 09 80 27 75 42 69 34 90第二趟排序结果： 09 18 27 75 42 69 34 80第三趟排序结果： 09 18 27 42 69 34 75第四趟排序结果： 09 18 27 42 34 69第五趟排序结果： 09 18 27 34 40第六趟排序结果： 09 18 27 34第六趟排序过程中已无记录交换，排序结束。（5） 10 18 4 3 6 12 9 15 8d=4 6 12 4 3 8 18 9 15 10d=2 4 3 6 12 8 15 9 18 10d=1 3 4 6 8 9 10 12 15 18 （6） 12 02 16 30 28 10 17 20 06 18d=5 10 02 16 06 18 12 17 20 30 28d=2 12 02 16 06 17 12 18 20 30 28d=1 02 06 10 12 16 17 18 20 28 30（7） 10 18 4 3 6 12 9 15 10 18 3 4 6 12 9 15 第一趟排序结果 3 4 10 18 6 9 12 15 第二趟排序结果 3 4 6 9 10 12 15 18 第三趟排序结果（8） 53 36 48 36 60 7 18 41（7） 36 48 36 60 53 18 41（7 18） 48 36 60 53 36 41（7 18 36） 48 60 53 36 41（7 18 36 36） 60 53 48 41（7 18 36 36 41） 53 48 60（7 18 36 36 41 48） 53 60（7 18 36 36 41 48 53） 60（7 18 36 36 41 48 53 60 ）（9） 10 1 15 18 7 15 low high 交换 7 1 15 18 10 15 low high 交换第一趟排序结果： 7 1 10 18 15 15