下载文档原格式
第10章排序10.1 知识点分析1．排序基本概念：（1）排序将数据元素的任意序列，重新排列成一个按关键字有序（递增或递减）的序列的过程称为排序。
（2）排序方法的稳定和不稳定若对任意的数据元素序列，使用某个排序方法，对它按关键字进行排序，若对原先具有相同键值元素间的位置关系，排序前与排序后保持一致，称此排序方法是稳定的；反之，则称为不稳定的。
（3）内排序整个排序过程都在内存进行的排序称为内排序，本书仅讨论内排序。
（4）外排序待排序的数据元素量大，以致内存一次不能容纳全部记录，在排序过程中需要对外存进行访问的排序称为外排序。
2．直接插入排序直接插入排序法是将一个记录插到已排序好的有序表中，从而得到一个新的，记录数增1的有序表。
3．二分插入排序二分插入排序法是用二分查找法在有序表中找到正确的插入位置，然后移动记录，空出插入位置，再进行插入的排序方法。
4．希尔排序希尔排序的基本思想是：先选取一个小于n的整数d1作为第一个增量，把待排序的数据分成d1个组，所有距离为d1的倍数的记录放在同一个组内，在各组内进行直接插入排序，每一趟排序会使数据更接近于有序。
然后，取第二个增量d2，d2< d1，重复进行上述分组和排序，直至所取的增量d i=1（其中d i< d i-1 < ……< d2< d1），即所有记录在同一组进行直接插入排序后为止。
5．冒泡排序冒泡法是指每相邻两个记录关键字比大小，大的记录往下沉（也可以小的往上浮）。
每一遍把最后一个下沉的位置记下，下一遍只需检查比较到此为止；到所有记录都不发生下沉时，整个过程结束。
6．快速排序快速排序法是通过一趟排序，将待排序的记录组分割成独立的两部分，其中前一部分记录的关键字均比枢轴记录的关键字小；后一部分记录的关键字均比枢轴记录的关键字大，枢轴记录得到了它在整个序列中的最终位置并被存放好。
第二趟再分别对分割成两部分子序列，再进行快速排序，这两部分子序列中的枢轴记录也得到了最终在序列中的位置而被存放好，并且它们又分别分割出独立的两个子序列……。
第10章排序一、选择题1．某内排序方法的稳定性是指( D )。
【南京理工大学 1997 一、10（2分）】A．该排序算法不允许有相同的关键字记录 B．该排序算法允许有相同的关键字记录C．平均时间为0（n log n）的排序方法 D．以上都不对2．下面给出的四种排序法中( D )排序法是不稳定性排序法。
【北京航空航天大学 1999 一、10 （2分）】 A. 插入 B. 冒泡 C. 二路归并 D. 堆积3．下列排序算法中，其中（D ）是稳定的。
【福州大学 1998 一、3 (2分)】A. 堆排序，冒泡排序B. 快速排序，堆排序C. 直接选择排序，归并排序D. 归并排序，冒泡排序4．稳定的排序方法是（ B ）【北方交通大学 2000 二、3（2分）】A．直接插入排序和快速排序 B．折半插入排序和起泡排序C．简单选择排序和四路归并排序 D．树形选择排序和shell排序5．下列排序方法中，哪一个是稳定的排序方法？（ B ）【北方交通大学 2001 一、8（2分）】A．直接选择排序 B．二分法插入排序 C．希尔排序 D．快速排序6. 快速排序方法在（ D ）情况下最不利于发挥其长处。
【燕山大学 2001 一、3 （2分）】A. 要排序的数据量太大B. 要排序的数据中含有多个相同值C. 要排序的数据个数为奇数D. 要排序的数据已基本有序7. 以下序列不是堆的是( D )。
【西安电子科技大学 2001应用一、5 （2分）】A. (100,85,98,77,80,60,82,40,20,10,66)B. (100,98,85,82,80,77,66,60,40,20,10)C. (10,20,40,60,66,77,80,82,85,98,100)D. (100,85,40,77,80,60,66,98,82,10,20)8．下列四个序列中，哪一个是堆（ C ）。
【北京工商大学 2001 一、8 （3分）】A. 75,65,30,15,25,45,20,10B. 75,65,45,10,30,25,20,15C. 75,45,65,30,15,25,20,10D. 75,45,65,10,25,30,20,159．从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放在已排序序列的合适位置，该排序方法称为( A )排序法。
9.1选择题1．从末排序的序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放在排序序列的合适位置，该排序方法称为（）排序法。
A）插入B）选择C）希尔D）二路归并【答案】A2．下面各种排序方法中，最好情况下时间复杂度为O(n)的是（）A）快速排序B）直接插入排序C）堆排序D）归并排序【答案】B3．用某种排序方法对线性表（25,84,21,47,15,27,68,35,20）进行排序时，无序序列的变化情况如下：25 84 21 47 15 27 68 35 2020 15 21 25 47 27 68 35 8415 20 21 25 35 27 47 68 8415 20 21 25 27 35 47 68 84则所采用的排序方法是（）Ａ）选择排序Ｂ）希尔排序Ｃ）归并排序Ｄ）快速排序【答案】Ｄ4．下面给出的四种排序法中，（）排序是不稳定排序法。
A）插入B）冒泡C）二路归并D）堆【答案】D5．快速排序方法在（）情况下最不利于发挥其长处。
Ａ）要排序的数据量太大Ｂ）要排序的数据中含有多个相同值Ｃ）要排序的数据已基本有序Ｄ）要排序的数据个数为奇数【答案】Ｃ6．一组记录的关键码为（46,79,56,38,40,84），则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为（）Ａ）38,40,46,56,79,84B）40,38,46,79,56,84C）40,38,46,56,79,84D）40,38,46,84,56,79【答案】Ｃ7．对记录的关键码{50，26，38，80，70，90，8，30，40，20}进行排序，各趟排序结束时的结果为：50,26,38,80,70,90 ,8,30,40,2050,8,30,40,20,90,26,38,80,7026,8,30,40,20,80,50,38,90,708,20,26,30,38,40,50,70,80,90其使用的排序方法是（）A）快速排序B）基数排序C）希尔排序D）归并排序【答案】C8．以下序列不是堆的是（）A）100,85,98,77,80,60,82,40,20,10,66B）100,98,85,82,80,77,66,60,40,20,10C）10,20,40,60,66,77,80,82,85,98,100D）100,85,40,77,80,60,66,98,82,10,20【答案】D【解析】根据堆采用完全二叉树的顺序存储形式及堆的特点，因第一个结点即根结点关键字值最大，则应建立一个大根堆，但依据此数据序列建立起堆后关键字值为40的左右孩子结点分别为60、66，不符合大根堆特点。
第十章排序一、单项选择题1.有一组序列48,36,68,99,75,24,58,52进行快速排序，要求结果按从小到大排序，则进行一次划分之后结果为_____。
A. (24 28 36) 48 (52 68 75 99)B. (28 36 24) 48 (75 99 68 52)C. (36 68 99) 48 (75 24 28 52)D. (28 36 24) 48 (99 75 68 52)2.已知两个有序表，若要将它们组合成一个新的有序表，最好的方法是_____。
A. 希尔排序B. 二分插入排序C. 合并排序D. 冒泡排序3.排序译意风稳定的和不稳定的之分，下列四个说法中，只有______是正确的。
A. 快速排序是稳定的排序方法B. 堆排序是不稳定的排序方法C. 希尔排序是稳定的排序方法D. 冒泡排序是不稳定的排序方法4. 下列排序方法中，____方法是不稳定的。
A. 冒泡排序B. 希尔排序C. 冒泡排序D. 直接插入排序5. 下列排序方法中，在待排序的数据已经有序时，花费时间反而最多的是______。
A.快速排序B. 希尔排序C. 冒泡排序D. 堆排序6. 快速排序方法在最好情况下的时间复杂度为______。
A. O(n)B. O(n2)C. O(nlog2n)D.(log2n)7. 下列排序方法中，时间复杂度不受数据初始状态影响，恒为O(n2)的是_______。
A. 堆排序B.冒泡排序C. 直接选择排序D.快速排序8. 依次将待排序序列中的元素和有序子序列合并为一个新的有序子序列的排序方法是____。
A. 快速排序B.插入排序C. 冒泡排序D. 堆排序9. 在表R中排序前已按键值递增顺序排序，则_____方法的比较次数最少。
A. 直接插入排序B. 快速排序C. 归并排序D. 选择排序10. 已知表A中每个元素距其最终位置不远，采用______方法最节省时间。
A. 堆排序B. 冒泡排序C. 快速排序D. 直接选择排序11. 在下列排序方法中，字比较的次数与记录的初始排列次序无关的是______。
A. 希尔排序B. 冒泡排序C. 插入排序D. 选择排序12. 快速排序方法在_____情况下最不利于发挥其长处。
A. 要排序的数据量太大B. 要排序的数据中含有多个相同值C. 要排序的数据已基本有序D. 要排序的数据个数为奇数13. 一组记录的关键字经一趟二路归并排序后得到含有５个长度为２的有序表：[25,48],[16,35],[79,82], [23,40],[36,72]，在此基础上按二路归并排序方法再对该序列进行一趟归并后的结果为______。
A. 16,25,35,48,23,40,79,82,36,72B. 16,25,35,48,79,82,23,36,40,72C. 16,25,48,35,79,82,23,36,40,72D. 16,25,35,48,79,23,36,40,72,8214. 一组记录的关键码为(46,74,18,53,14,20,40,38,86,65)，利用堆排序的方法建立的初始堆为____。
A. (14,18,38,46,65,40,20,53,86,74)B. (14,38,18,46,65,20,40,53,86,74)C. (14,18,20,38,40,46,53,65,74,86)D. (14,86,20,38,40,46,53,65,74,18)单项选择题参考答案1. B2. C3. B4. B5. A6. C7. C8. B9. A 10. B 11. D 12. C13. A 14. B二、多项选择题1. 高度为h 的堆中，最多有______个元素，最少有____个元素，最小的元素可能在_____位置。
A. 2h-1B. 2h-1C. 双亲结点D. 叶子结点2. 对于有n个元素的的数据进行排序，直接插入排序方法是从_____个元素开始，插入到前边适当位置的排序方法。
快速排序方法首先将第_____个元素移动到排序后的位置上。
A. 1B. 2C. n-1D. n3. 对于有n个元素的数据进行排序，直接选择排序方法首先将选择的元素放在第____个元素的位置上；堆排序首先从堆的根选择出最大（或最小）的元素移到位置____;归并排序方法首先将n个元素分成______组，再进行两两归并。
A. 1B. 2C. n-1D. n4. 以下排序法中，辅助空间为O(1)的有_______、_______.A. 冒泡排序B. 快速排序C. 堆排序D. 归并排序5. 若数据元素的个数n较小，应采用____和______排序方法。
A. 直接插入排序B. 堆排序C. 直接选择排序D. 归并排序6. 若数据元素个数n较大，应采用______和______排序方法。
A. 直接插入排序B. 堆排序C. 直接选择排序D. 归并排序多项选择题参考答案：1.A B D2. B A3. A D D4. A C5. A C6. B D三、填空题1. 在直接插入和直接选择排序中，若初始数据基本有序，则选用____，若初始数据基本反序，则选用_____。
解：直接插入排序直接选择排序2. 在对一组记录(50,40,95,20,15,70,60,45,80)进行直接选择排序时，第４次交换和选择后，未排序记录（即无序表）为_______。
解：(50,70,60,95,80)3. 在对一组记录(50, 40,95,20,15,70,60,45,80)进行堆排序时，根据初始记录构成初始堆后，最后４条记录为)________。
解：(50,60,40,20)４. 在对一组记录(50, 40,95,20,15,70,60,45,80)进行冒泡排序时，第一趟需进行相信记录的交换的次数为_______，在整个排序过程中共需进行_______趟才可完成。
解：６７四、简答题1.当R[low..high]中的关键字均相同时，Partition返回的值是什么？此时快速排序的运行时间是多少？能否修改Partition，使得划分结果是平衡的（即划分后左、右子区间的长度大致相等地）？解：当R[low..high]中的关键字均相同时，Partition返回的值是low。
此时快速排序的运行时间是O(n2).不能修改Partition，以使划分结果是平衡的。
2. 若文件初态是反序的，则直接插入、直接选择和冒泡排序哪一个更好？解：若文件初态是反序的，则直接选择排序更好。
因为反序时冒泡排序的比较和交换次数最多，而直接插入和直接选择排序的比较次数差不多，但直接插入时无素的移动次数较多。
３．若文件初态是反序的，且要求排序稳定，则在直接插入、直接选择、冒泡和快速排序中应选哪种方法？解：若文件初态是反序的，且排序是稳定的，则以上几种排序方法中直接插入排序更好，因为当文件刘反序时，快速排序和冒泡排序都处于最坏的情况，其时间复杂度为O(n2),且排序不是稳定的；虽然直接选择排序的交换次数较少，但它不稳定，所以直接插入排序更好。
４. 有序数组是堆吗？解：有序数组满足堆的定义，所以有序数组是堆。
5. 高度为h的堆中，最多有多少个元素？最少有多少个元素？在大根堆中，关键字最小的元素可能存放在堆的哪些地方？解：高度为h的堆中，最多有2h-1个元素（为满二叉树），最少有２h-1个元素。
在大根堆中，关键字最小的元素可能存放在堆的最下层或次下层。
6. 判别下列序列是否为堆（小根堆或大根堆），若不是，则将其调整为堆：(1) 100 86 48 76 33 39 42 57 66 21(2) 12 70 33 65 24 56 48 92 86 33(3) 103 97 56 38 66 23 42 12 30 52 06 20(4) 5 56 20 23 40 38 29 61 35 76 28 100解：(1) (3)是大根堆，(2) (3)不是堆(2)调整为小根堆：12243365335648928670(3)调整为小根堆：5232035283829615676401007. 将两个长度为n的有序表归并为一个长度为２n的有序表，最少需比较n次，最多需比较2n-1，请说明这两种情况发生时，两个被归并的表有何特征？解：若将两个长度为n的有序表归并为一个长度为２n的有序表需比较n次，则两个被归并的表应满足：其中一个表的所有元素均小于（或大于）另一个表中的任意元素，若将两个长度为n的有序表归并为一个长度为２n的有序表需比较2n-1次，则两个被归并的表应满足：其中一个表的所有元素不得均小于（或大于）另一个表中的两个或两个以上的元素。
8. 针对关键字是非负整数，快速排序、归并排序、堆排序和基数排序哪一个排序最快？若要求辅助空间为O(1)，则应选谁？若要求排序是稳定的，且关键字为实数，则应选谁？解：若关键字是非负整数，一般情况下在快速排序、归并排序、堆排序和基数排序中快速排序最快。
若要求辅助空间为o(1)，则应选堆排序，若要求排序是稳定的，且关键字为实数，则应选择归并排序。
四、算法设计题1. 将哨兵在R[n]中，被排序的记录放在R[0..n-1]中，编写直接插入排序算法。
解：直接插入排序算法如下：void InsertSort (SegList R){int i, j;for (i=1;i<=n-1; i++) {if (R[i].key<R[i-1].key) {R[n]=R[i]; j=i-1;do {R[j+1]=R[j];i--;} while （R[n].key <R[j].key &&j>-1）;R[j+1]=R[n];}}2. 以单链表作为存储结构实现直接插入排序算法。
解：先用*head和第一个结点构成一个有序表，用p镄针扫描余下的结点，将*p的key域值与有序表中的结点进行比较，找到合适的位置，将*p插入在*prev和*q之间。
算法如下：typedef strruct node {HeyType key;struct node *next;} Lnode;void InsertList (Lnode *&head){Lnode *p, *q, *prev, *temp;if (head->next==NULL)return;p=head->next;if (p->next==NULL)RETURN;head->next->next=NULL;p=p->next;while (p!=NULL) {q=head->next;pre=head;while (q1=NULL &&Q->KEY<P->KEY) {prev=q;q=q->next;}temp=p->next;p->next=q;prev->next=p;p=temp;}}3. 下面是一个自上往下扫描的冒泡排序的伪代码算法，它采用lastExchange来记录每趟扫描中进行交换有最后一个元素的位置，冯以它作为下一趟排序循环终止的控制值。
