第7章 排序
一、选择题
1．某内排序方法的稳定性是指( D )。
A．该排序算法不允许有相同的关键字记录 B．该排序算法允许有相同的关键字记录
C．平均时间为0（n log n）的排序方法 D．以上都不对
2．下面给出的四种排序法中( D )排序法是不稳定性排序法。
A. 插入 B. 冒泡 C. 二路归并 D. 堆
3．下列排序算法中，其中（ D ）是稳定的。
A. 堆排序，冒泡排序 B. 快速排序，堆排序
C. 直接选择排序，归并排序 D. 归并排序，冒泡排序
4．稳定的排序方法是（ B ）
A．直接插入排序和快速排序 B．折半插入排序和起泡排序
C．简单选择排序和四路归并排序 D．树形选择排序和shell排序
5．下列排序方法中，哪一个是稳定的排序方法？（ B ）
A．直接选择排序 B．二分法插入排序 C．希尔排序 D．快速排序
6．若要求尽可能快地对序列进行稳定的排序，则应选（B）。
A．快速排序 B．归并排序 C．冒泡排序
7．如果待排序序列中两个数据元素具有相同的值，在排序前后它们的相互位置发生颠倒，则称该排序算法是不稳定的。（ CE ）就是不稳定的排序方法。
A．起泡排序 B．归并排序 C．Shell排序 D．直接插入排序 E．简单选择排序
8．若要求排序是稳定的，且关键字为实数，则在下列排序方法中应选（A ）排序为宜。
A．直接插入 B．直接选择 C．堆 D．快速 E．基数
9．若需在O(nlog2n)的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是（ C ）。
A. 快速排序 B. 堆排序 C. 归并排序 D. 直接插入排序
10．下面的排序算法中，不稳定的是（ CDF ）
A.起泡排序 B.折半插入排序 C.简单选择排序 D.希尔排序 E.基数排序 F.堆排序。
11．下列内部排序算法中：
A．快速排序 B.直接插入排序 C. 二路归并排序 D. 简单选择排序 E. 起泡排序 F. 堆排序
（1） 其比较次数与序列初态无关的算法是（ DC ） （2）不稳定的排序算法是（ ADF ）
（3）在初始序列已基本有序（除去n个元素中的某k个元素后即呈有序，k<<n）的情况下，排序效率最高的算法是（B ）
（4）排序的平均时间复杂度为O(n•logn)的算法是（ACF ）为O(n•n)的算法是（BDE ）
12．排序趟数与序列的原始状态有关的排序方法是( CD )排序法。
A．插入 B. 选择 C. 冒泡 D. 快速
13．下面给出的四种排序方法中，排序过程中的比较次数与排序方法无关的是。( A )
A．选择排序法 B. 插入排序法 C. 快速排序法 D. 堆积排序法
14．对下列四种排序方法，在排序中关键字比较次数同记录初始排列无关的是( BD )。
A．直接插入 B. 二分法插入 C. 快速排序 D. 归并排序
15．在下列排序算法中,哪一个算法的时间复杂度与初始排序无关（D ）。
A． 直接插入排序 B. 气泡排序 C. 快速排序 D. 直接选择排序
16．比较次数与排序的初始状态无关的排序方法是( D )。
A．直接插入排序 B．起泡排序 C．快速排序 D．简单选择排序
17．数据序列（8，9，10，4，5，6，20，1，2）只能是下列排序算法中的( C )的两趟排序后的结果。
A．选择排序 B.冒泡排序 C.插入排序 D.堆排序
18．数据序列（2，1，4，9，8，10，6，20）只能是下列排序算法中的( A )的两趟排序后的结果。
A. 快速排序 B. 冒泡排序 C. 选择排序 D. 插入排序
19．对一组数据（84，47，25，15，21）排序，数据的排列次序在排序的过程中的变化为
（1） 84 47 25 15 21 （2） 15 47 25 84 21 （3） 15 21 25 84 47 （4） 15 21 25 47 84
则采用的排序是( A )。
A. 选择 B. 冒泡 C. 快速 D. 插入
20．对序列{15，9，7，8，20，-1，4}进行排序，进行一趟后数据的排列变为{4，9，-1，8，20，7，15}；则采用的是（ C ）排序。
A. 选择 B. 快速 C. 希尔 D. 冒泡
21．若上题的数据经一趟排序后的排列为{9，15，7，8，20，-1，4}，则采用的是（C ）排序。
A．选择 B. 堆 C. 直接插入 D. 冒泡
22．下列排序算法中( B )不能保证每趟排序至少能将一个元素放到其最终的位置上。
A.快速排序 B. shell排序 C. 堆排序 D.冒泡排序
23．下列排序算法中( C )排序在一趟结束后不一定能选出一个元素放在其最终位置上。
A. 选择 B. 冒泡 C. 归并 D. 堆
24．下列序列中，（ C）是执行第一趟快速排序后所得的序列。
A. [68，11，18，69] [23，93，73] B. [68，11，69，23] [18，93，73]
C. [93，73] [68，11，69，23，18] D. [68，11，69，23，18] [93，73]
25．有一组数据（15，9，7，8，20，-1，7，4） 用快速排序的划分方法进行一趟划分后数据的排序为 ( A )（按递增序）。
A．下面的B，C，D都不对。 B．9，7，8，4，-1，7，15，20
C．20，15，8，9，7，-1，4，7 D. 9，4，7，8，7，-1，15，20
26．一组记录的关键码为（46，79，56，38，40，84），则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为（ C ）。
A．(38,40,46,56,79,84) B. (40,38,46,79,56,84)
C．(40,38,46,56,79,84) D. (40,38,46,84,56,79)
27. 在下面的排序方法中，辅助空间为O（n）的是( D ) 。
A．希尔排序 B. 堆排序 C. 选择排序 D. 归并排序
28．下列排序算法中，在待排序数据已有序时，花费时间反而最多的是( C )排序。
A． 冒泡 B. 希尔 C. 快速 D. 堆
29.下列排序算法中，在每一趟都能选出一个元素放到其最终位置上，并且其时间性能受数据初始特性影响的是：（ B ）。
A. 直接插入排序 B. 快速排序 C. 直接选择排序 D. 堆排序
30. 对初始状态为递增序列的表按递增顺序排序，最省时间的是（ c ）算法，最费时间的是（ b ）算法。
A. 堆排序 B. 快速排序 C. 插入排序 D. 归并排序
31. 就平均性能而言，目前最好的内排序方法是( D )排序法。
A. 冒泡 B. 希尔插入 C. 交换 D. 快速
32．如果只想得到1000个元素组成的序列中第5个最小元素之前的部分排序的序列，用（ D）方法最快。
A．起泡排序 B．快速排列 C．Shell排序 D．堆排序 E．简单选择排序
33．在文件“局部有序”或文件长度较小的情况下，最佳内部排序的方法是（A ）
A．直接插入排序 B．冒泡排序 C．简单选择排序
34．下列排序算法中，（ D ）算法可能会出现下面情况：在最后一趟开始之前，所有元素都不在其最终的位置上。
A. 堆排序 B. 冒泡排序 C. 快速排序 D. 插入排序
35. 下列排序算法中，占用辅助空间最多的是：( A )
A. 归并排序 B. 快速排序 C. 希尔排序 D. 堆排序
36．从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放在已排序序列的合适位置，该排序方法称为( A)排序法。
A. 插入 B. 选择 C. 希尔 D. 二路归并
37. 在排序算法中，每次从未排序的记录中挑出最小（或最大）关键码字的记录，加入到已排序记录的末尾，该排序方法是（ A ）。
A. 选择 B. 冒泡 C. 插入 D. 堆
38．用直接插入排序方法对下面四个序列进行排序（由小到大），元素比较次数最少的是（ C ）。
A． 94,32,40,90,80,46,21,69 B．32,40,21,46,69,94,90,80
C． 21,32,46,40,80,69,90,94 D．90,69,80,46,21,32,94,40
39．直接插入排序在最好情况下的时间复杂度为（ B ）
A．O(logn) B．O(n) C．O(n*logn) D．O(n2)
40. 若用冒泡排序方法对序列{10,14,26,29,41,52}从大到小排序，需进行 （ C ）次比较。
A. 3 B. 10 C. 15 D. 25
41. 采用简单选择排序，比较次数与移动次数分别为( C )。
A. O（n）,O(logn) B.O(logn),0(n*n) C. 0(n*n),0(n) D. 0(nlogn),0(n)
42. 对序列{15，9，7，8，20，-1，4，} 用希尔排序方法排序，经一趟后序列变为{15，-l，4，8，20，9，7}则该次采用的增量是 ( B )
A. l B. 4 C. 3 D. 2
43．对下列关键字序列用快速排序法进行排序时，速度最快的情形是（ A ）。
A． {21,25,5,17,9,23,30} B．{25,23,30,17,21,5,9}
C． {21,9,17,30,25,23,5} Ｄ．{5,9,17,21,23,25,30}
44．对关键码序列28，16，32，12，60，2，5，72快速排序，从小到大一次划分结果为（B ）。
A. (2,5,12,16)26(60,32,72) B. (5,16,2,12)28(60,32,72)
C. (2,16,12,5)28(60,32,72) D. (5,16,2,12)28(32,60,72)
45．对n个记录的线性表进行快速排序为减少算法的递归深度，以下叙述正确的是（ A ）
A．每次分区后，先处理较短的部分 B．每次分区后，先处理较长的部分
C．与算法每次分区后的处理顺序无关 D．以上三者都不对
46．当n个整型数据是有序时，对这n个数据用快速排序算法排序，则时间复杂度是 ( 6 )，当用递归算法求n!时，算法的时间复杂度是 ( 7 )，则：(6)-(7)=（C ）
A. O(n) B. O(nlogn) C. O(n*n) D. O(logn)
47．快速排序在最坏情况下的时间复杂度是( B ),比( D )的性能差。
A．O(NlogN) B．O(N2) C．O(N3) D．堆排序E．冒泡排序F．选择排序
48. 快速排序方法在（ D ）情况下最不利于发挥其长处。
A. 要排序的数据量太大 B. 要排序的数据中含有多个相同值
C. 要排序的数据个数为奇数 D. 要排序的数据已基本有序
49．在含有n个关键字的小根堆（堆顶元素最小）中，关键字最大的记录有可能存储在（D ）位置上。
A．ën/2û B．ën/2û -1 C．1 D．ën/2û +2
50. 以下序列不是堆的是( D )。
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)
51．下列四个序列中，哪一个是堆（C ）。
A.75,65,30,15,25,45,20,10 B.75,65,45,10,30,25,20,15
C.75,45,65,30,15,25,20,10 D.75,45,65,10,25,30,20,15
52. 堆排序是（E ）类排序，堆排序平均执行的时间复杂度和需要附加的存储空间复杂度分别是（G）
A. 插入 B. 交换 C. 归并 D. 基数 E. 选择
F. O（n2）和O（1） G. O（nlog2n）和O（1）
H. O（nlog2n）和O（n） I. O（n2）和O（n）
53．在对n个元素的序列进行排序时，堆排序所需要的附加存储空间是（ B ）。
A. O(log2n) B. O(1) C. O(n) D. O(nlog2n)
54． 对n 个记录的文件进行堆排序，最坏情况下的执行时间是多少？（ C ）
A．O（log2n）B．O（n） C．O（nlog2n） D．O（n*n）
55. 有一组数据（15，9，7，8，20，-1，7，4），用堆排序的筛选方法建立的初始堆为 （ C ）
A．-1，4，8，9，20，7，15，7 B．-1，7，15，7，4，8，20，9
C．-1，4，7，8，20，15，7，9 D．A，B，C均不对。
56. 归并排序中，归并的趟数是( B )。
A．O（n） B．O(logn) C．O(nlogn) D．O(n*n)
57． 在排序算法中每一项都与其它各项进行比较，计算出小于该项的项的个数，以确定该项的位置叫( B )
A．插入排序 B．枚举排序 C．选择排序 D．交换排序
58．就排序算法所用的辅助空间而言，堆排序，快速排序，归并排序的关系是 （A ）
A．堆排序〈 快速排序〈归并排序 B．堆排序〈 归并排序〈快速排序
C．堆排序〉 归并排序 〉快速排序 D．堆排序 > 快速排序 > 归并排序
E．以上答案都不对
59．排序方法有许多种，（1）法从未排序的序列中依次取出元素，与已排序序列（初始时为空）中的元素作比较，将其放入已排序序列的正确位置上；（2）法从未排序的序列中挑选元素，并将其依次放入已排序序列（初始时为空）的一端； 交换排序方法是对序列中的元素进行一系列比较，当被比较的两元素逆序时，进行交换；（3）和（4）是基于这类方法的两种排序方法， 而（4）是比（3）效率更高的方法；（5）法是基于选择排序的一种排序方法，是完全二叉树结构的一个重要应用。 CADBG
（1）--（5）: A．选择排序 B．快速排序 C．插入排序 D．起泡排序
E．归并排序 F．shell排序 G．堆排序 H．基数排序
二、填空题
1．若不考虑基数排序，则在排序过程中，主要进行的两种基本操作是关键字的__比较____和记录的___移动__。
2. 外排序的基本操作过程是__生成有序归并段_____和_归并______。
3. 属于不稳定排序的有_希尔排序、简单选择排序、快速排序、堆排序_________。
4．分别采用堆排序，快速排序，冒泡排序和归并排序，对初态为有序的表，则最省时间的是__冒泡___算法，最费时间的是___快速___算法。
5. 不受待排序初始序列的影响，时间复杂度为O(N2)的排序算法是_简单选择排序____，在排序算法的最后一趟开始之前，所有元素都可能不在其最终位置上的排序算法是__直接插入排序___。
6．直接插入排序用监视哨的作用是__免去查找过程中每一步都要检测整个表是否查找完毕，提高了查找效_____。
7．对n个记录的表r[1..n]进行简单选择排序，所需进行的关键字间的比较次数为__ n(n-1)/2_____。
8. 设用希尔排序对数组{98，36，-9，0，47，23，1，8，10，7}进行排序，给出的步长（也称增量序列）依次是4，2，1则排序需______3____趟，写出第一趟结束后，数组中数据的排列次序_ (10,7,-9,0,47,23,1,8,98,36)________。
9．从平均时间性能而言，____快速______排序最佳。
10．对于7个元素的集合{1，2，3，4，5，6，7}进行快速排序，具有最小比较和交换次数的初始排列次序为_ (4,1,3,2,6,5,7)____。
11．快速排序在_每次划分能得到两个等长的子序列____的情况下最易发挥其长处。
12．在数据表有序时，快速排序算法的时间复杂度是__ O(n2)__。
13．堆排序的算法时间复杂度为：_ O(nlog2n)____。
三、应用题
1． 在堆排序、快速排序和合并排序中：
(1)．若只从存储空间考虑，则应首先选取哪种排序方法，其次选取哪种排序方法，最后选取哪种排序方法？
(2)．若只从排序结果的稳定性考虑，则应选取哪种排序方法？
(3)．若只从平均情况下排序最快考虑，则应选取哪种排序方法？
(4)．若只从最坏情况下排序最快并且要节省内存考虑，则应选取哪种排序方法？
(1)堆排序，快速排序，归并排序(2)归并排序 (3)快速排序 (4)堆排序
2. 快排序、堆排序、合并排序、Shell排序中哪种排序平均比较次数最少，哪种排序占用空间最多，哪几种排序算法是不稳定的？
平均比较次数最少: 快速排序; 占用空间最多: 归并排序; 不稳定排序算法:快速排序、堆排序、希尔排序。
3．算法模拟
设待排序的记录共7个，排序码分别为8，3，2，5，9，1，6。
(1) 用直接插入排序。试以排序码序列的变化描述形式说明排序全过程（动态过程）要求按递减顺序排序。
(2) 用直接选择排序。试以排序码序列的变化描述形式说明排序全过程（动态过程）要求按递减顺序排序。
(3) 直接插入排序算法和直接选择排序算法的稳定性如何？
(1)直接插入排序
第一趟 (3)[8,3],2,5,9,1,6
第二趟 (2)[8,3,2],5,9,1,6
第三趟 (5)[8,5,3,2],9,1,6
第四趟 (9)[9,8,5,3,2],1,6
第五趟 (1)[9,8,5,3,2,1],6
第六趟 (6)[9,8,6,5,3,2,1]
(2)直接选择排序（第六趟后仅剩一个元素，是最小的，直接选择排序结束）
第一趟 (9)[9],3,2,5,8,1,6
第二趟 (8)[9,8],2,5,3,1,6
第三趟 (6)[9,8,6],5,3,1,2
第四趟 (5)[9,8,6,5],3,1,2
第五趟 (3)[9,8,6,5,3],1,2
第六趟 (2)[9,8,6,5,3,2],1
(3)直接插入排序是稳定排序，直接选择排序是不稳定排序。
4．对给定文件（28，07，39，10，65，14，61，17，50，21）选择第一个元素28进行划分，写出其快速排序第一遍的排序过程。
初始序列：[28],07,39,10,65,14,61,17,50,21
21移动：21,07,39,10,65,14,61,17,50,[]
39移动：21,07,[],10,65,14,61,17,50,39
17移动：21,07,17,10,65,14,61,[],50,39
65移动：21,07,17,10,[],14,61,65,50,39
14移动：21,07,17,10,14,[28],61,65,50,39
5．已知一关键码序列为：3，87，12，61，70，97，26，45。试根据堆排序原理，填写完整下示各步骤结果。
建立堆结构：__ :97,87,26,61,70,12,3,45___________
交换与调整：
（1）87 70 26 61 45 12 3 97;
（2）______ 70,61,26,3,45,12,87,97______________;
（3）61 45 26 3 12 70 87 97;
（4）_______ 45,12,26,3,61,70,87,97_____________;
（5）26 12 3 45 61 70 87 97;
（6）_______ 12,3,26,45,61,70,87,97_____________;
（7）3 12 26 45 61 70 87 97;
6．全国有10000人参加物理竞赛，只录取成绩优异的前10名，并将他们从高分到低分输出。而对落选的其他考生，不需排出名次，问此种情况下，用何种排序方法速度最快？为什么？
堆排序
在内部排序方法中，一趟排序后只有简单选择排序和冒泡排序可以选出一个最大（或最小）元素，并加入到已有的有序子序列中，但要比较n-1次。选次大元素要再比较n-2次,其时间复杂度是O(n2)。从10000个元素中选10个元素不能使用这种方法。而快速排序、插入排序、归并排序、基数排序等时间性能好的排序，都要等到最后才能确定各元素位置。只有堆排序，在未结束全部排序前，可以有部分排序结果。建立堆后，堆顶元素就是最大（或最小，视大堆或小堆而定）元素，然后，调堆又选出次大（小）元素。凡要求在n个元素中选出k(k<<n,k>2)
个最大（或最小）元素，一般均使用堆排序。因为堆排序建堆比较次数至多不超过4n,对深度为k的堆，在调堆算法中进行的关键字的比较次数至多为2(k-1)次，且辅助空间为O(1)。
7. 给出一组关键字：29，18，25，47，58，12，51，10，分别写出按下列各种排序方法进行排序时的变化过程：
(1) 归并排序 每归并一次书写一个次序。
(2) 快速排序 每划分一次书写一个次序。
(3) 堆排序 先建成一个堆，然后每从堆顶取下一个元素后，将堆调整一次。
(1)2路归并
第一趟:18,29,25,47,12,58,10,51；
第二趟:18,25,29,47,10,12,51,58；
第三趟:10,12,18,25,29,47,51,58
(2)快速排序
第一趟:10,18,25,12,29,58,51,47；
第二趟:10,18,25,12,29,47,51,88；
第三趟:10,12,18,25,29,47,51,88
(3)堆排序 建大堆
58,47,51,29,18,12,25,10；
①51,47,25,29,18,12,10,58；
②47,29,25,10,18,12,51,58；
③29,18,25,10,12,47,51,58；
④25,18,12,10,29,47,51,58；
⑤18,10,12,25,29,47,51,58；
⑥12,10,18,25,29,47,51,58；
⑦10,12,18,25,29,47,51,58
8．请写出应填入下列叙述中（ ）内的正确答案。
排序有各种方法，如插入排序、快速排序、堆排序等。
设一数组中原有数据如下：15，13，20，18，12，60。下面是一组由不同排序方法进行一遍排序后的结果。
（快速 ）排序的结果为：12，13，15，18，20，60
（ 冒泡）排序的结果为：13，15，18，12，20，60
（直接插入 ）排序的结果为：13，15，20，18，12，60
（ 堆）排序的结果为：12，13，20，18，15，60
五、算法设计题：
1．冒泡排序算法是把大的元素向上移（气泡的上浮），也可以把小的元素向下移（气泡的下沉）请给出上浮和下沉过程交替的冒泡排序算法。
void BubbleSort2(int a[],int n) //相邻两趟向相反方向起泡的冒泡排序算法
{ change=1;low=0;high=n-1; //冒泡的上下界
while(low<high && change)
{ change=0; //设不发生交换
for(i=low;i<high;i++) //从上向下起泡
if(a[i]>a[i+1]){a[i]<-->a[i+1];change=1;} //有交换，修改标志change
high--; //修改上界
for(i=high;i>low;i--) //从下向上起泡
if(a[i]<a[i-1]){a[i]<-->a[i-1];change=1;}
low++; //修改下界
}//while
}//BubbleSort2
2．写出一趟快速排序算法。
int Partition(RecType R[]，int l，int h)
//一趟快速排序算法，枢轴记录到位，并返回其所在位置，
{ int i=l; j=h; R[0] = R[i]; x =R[i].key;
while(i<j)
{ while(i<j && R[j].key>=x) j--;
if (i<j) R[i] = R[j];
while(i<j && R[i].key<=x) i++;
if (i<j) R[j] = R[i];
}//while
R[i]=R[0];
return i;
3．非递归的快速排序算法。
void QuickSort(rectype r[n+1]; int n)
// 对r[1..n]进行快速排序的非递归算法
{typedef struct
{ int low,high; }node
node s[n+1]；//栈，容量足够大
int quickpass(rectype r[],int,int); // 函数声明
int top=1; s[top].low=1; s[top].high=n;
while (top>0)
{ss=s[top].low; tt=s[top].high; top--;
if (ss<tt)
{k=quickpass(r,ss,tt);
if (k-ss>1) {s[++top].low=ss; s[top].high=k-1;}
if (tt-k>1) {s[++top].low=k+1; s[top].high=tt;}
}
} // 算法结束
int quickpass(rectype r[];int s,t)
{i=s; j=t; rp=r[i]; x=r[i].key;
while （i<j）
{while (i<j && x<=r[j].key) j--;
if (i<j) r[i++]=r[j];
while (i<j && x>=r[j].key) i++;
if (i<j) r[j--]=r[i];;
]
r[i]=rp;
return (i);
} // 一次划分算法结束