《排序》练习题一、单项选择题1.若对n个元素进行直接插入排序，在进行第i趟排序时，假定元素r[i+1]的插入位置为r[j]，则需要移动元素的次数为（）。
A. j-iB. i-j-1C. i-jD. i-j+12.在对n个元素进行直接插入排序的过程中，共需要进行（）趟。
A. nB. n+1C. n-1D. 2n3.在对n个元素进行冒泡排序的过程中，最好情况下的时间复杂度为（）。
n) C. O(n)2 D. O(n)A. O(1)B. O(log24.在对n个元素进行快速排序的过程中，若每次划分得到的左、右两个子区间中元素的个数相等。
）或只差一个，则排序的时间复杂度为（2D. O(n) ) n) C. O(n A. O(1)B. O(nlog25.在对n个元素进行直接插入排序的过程中，算法的空间复杂度为（）。
B. O(logD. O(nlogn)2 A. O(1)n) C. O(n) 226.设一组初始记录关键字序列(5，2，6，3，8)，利用冒泡排序进行升序排序，且排序中从后往前。
进行比较，则第一趟冒泡排序的结果为（）(B) 2，6， 8，5，6，3，8，(A) 25，3(D) 2，3，， (C) 2，3，56， 8 6，5，87.对下列四个序列进行快速排序，各以第一个元素为基准进行第一次划分，则在该次划分过程中）。
需要移动元素次数最多的序列为（A. 1, 3, 5, 7, 9B. 9, 7, 5, 3, 1C. 5, 1, 3, 7, 9D. 5, 7, 9, 3, 1在对n。
）个元素进行堆排序的过程中，时间复杂度为（8.2D. O(nlogn C. O(n A. O(1) B.O(logn) ) )以下序列不可以构成小跟堆的是（9.） B. 1, 3, 5, 9, 7, 12 A. 12, 9,22。
7, 5, 3, 1D. 1, 5, 3, 9, 12, 7C. 1, 5, 3, 7, 9, 1210.设一组初始记录关键字序列(5，8，6，3，2)，以第一个记录关键字5为基准进行一趟从大到小快速排序的结果为（）。
A. 2，3，5，8，6B. 2，3，5，6，8C. 3，2，5，8，6D. 3，2，5，8，611.假定对元素序列（7, 3, 5, 9, 1, 12）进行堆排序，并且采用小根堆，则由初始数据构成的初始堆为（）。
A. 1, 3, 5, 7, 9, 12B. 1, 3, 5, 9, 7, 12D. 1, 5, 3, 9, 12, 7C. 1, 5, 3, 7, 9, 12，则进行第一趟堆排序后，再重新建堆得到的结果为(1, 5, 3, 9, 12, 7, 15, 10)假定一个初始堆为12. （。
） B. 3, 5, 9, 7, 12, 10, 15, 1A. 3, 5, 7, 9, 12, 10, 15, 1C. 3, 7, 5, 9, 12, 10, 15, 1D. 3, 5, 7, 12, 9, 10, 15, 113.若对n个元素进行归并排序，则进行归并的趟数为（）。
A. nB. n-1C. n/2D. ?logn?214.若要从1000个元素中得到10个最小值元素，最好采用（）方法。
A. 直接插入排序B. 归并排序D. 快速排序 C. 堆排序15.若要对1000个元素排序，要求既快又稳定，则最好采用（）方法。
归并排序B. 快速排序D. A. 直接插入排序堆排序C.二、填空题 _____1_。
n1.对个记录进行冒泡排序时，最少的比较次数为__n-1______，最少的趟数为_，在最坏情况下的时间复杂度为__O(nlogn)______2.快速排序在平均情况下的时间复杂度为22__O(n)___。
为根堆小立序排方法建的初始为一3.假定组记录(46,79,56,38,40,84)，则利用堆 __。
_(38,40,56,79,46,84)为的结果划的快，对其进行速排序第一次分后录定4.假一组记为(46,79,56,38,40,80) ___。
(40,38,46,56,79,80)___，对其进行归并排序的过程中，供需要(46,79,56,38,40,80,46,75,28,46)5.假定一组记录为 _____4_____趟完成。
____排序方法是稳定的。
_的所有排序方法中，O(nlogn)___归并在时间复杂度为6.2，则一9 }，进行从小到大的希尔排序，且分组增量d=3，，，7.设有一无序序列{3245，4112，1 。
趟希尔排序后的序列为_ {12,1,9,32,45,41} _三、判断题2 ) ( 。
0)．1希尔排序算法的平均时间复杂度为O(n 堆是完全二叉树，完全二叉树不一定是堆。
．（1）2 ）在对排序中，若要进行升序排序，则需要建立大根堆。
．3（1．4 0）若给出的待排序序列已有序，则使用快速排序的进行排序的时间复杂度是O(n)。
（ 1 （）若待排序序列已基本有序，则使用冒泡排序会比快速排序的时间效率会更好。
．5 6．堆排序是稳定的排序算法。
）（0四、应用题，给出采用直接插入排序法进行排序时(46,74,53,14,26,38,86,65,27,34) 1. 已知一组记录为每一趟的排序结果。
，给出采用冒泡排序法进行排序时每一 2. 已知一组记录为(46,74,53,14,26,38,86,65,27,34) 趟的排序结果。
，给出采用快速排序法进行排序时每一已知一组记录为 3. (46,74,53,14,26,38,86,65,27,34) 趟的排序结果。
，给出采用简单选择排序法进行排序时(46,74,53,14,26,38,86,65,27,34)已知一组记录为 4.每一趟的排序结果。
5. 已知一组记录为(46,74,53,14,26,38,86,65,27,34)，给出采用堆排序法进行排序时每一趟的排序结果。
6. 已知一组记录为(46,74,53,14,26,38,86,65,27,34)，给出采用归并排序法进行排序时每一趟的排序结果。
．四、应用题（参考答案）1.(0) [46] 74 53 14 26 38 86 65 27 34(1) [46 74] 53 14 26 38 86 65 27 34(2) [46 53 74] 14 26 38 86 65 27 34(3) [14 46 53 74] 26 38 86 65 27 34(4) [14 26 46 53 74] 38 86 65 27 34(5) [14 26 38 46 53 74] 86 65 27 34(6) [14 26 38 46 53 74 86] 65 27 34(7) [14 26 38 46 53 65 74 86] 27 34(8) [14 26 27 38 46 53 65 74 86] 342.(0) [46 74 53 14 26 38 86 65 27 34](1) [46 53 14 26 38 74 65 27 34] 86(2) [46 14 26 38 53 65 27 34] 74 86(3) [14 26 38 46 53 27 34] 65 74 86(4) [14 26 38 46 27 34] 53 65 74 86(5) [14 26 38 27 34] 46 53 65 74 86(6) [14 26 27 34] 38 46 53 65 74 86(7) [14 26 27 34] 38 46 53 65 74 86 3.(0) [46 74 53 14 26 38 86 65 27 34](1) [34 27 38 14 26] 46 [86 65 53 74](2) [26 27 14] 34 38 46 [74 65 53] 86(3) 14 26 27 34 38 46 [53 65] 74 86(4) 14 26 27 34 38 46 53 65 74 86 4.(0) [46 74 53 14 26 38 86 65 27 34](1) 14 [74 53 46 26 38 86 65 27 34](2) 14 26 [53 46 74 38 86 65 27 34](3) 14 26 27 [46 74 38 86 65 53 34](4) 14 26 27 34 [74 38 86 65 53 46](5) 14 26 27 34 38 [74 86 65 53 46](6) 14 26 27 34 38 46 [86 65 53 74](7) 14 26 27 34 38 46 53 [65 86 74](8) 14 26 27 34 38 46 53 65 [86 74](9) 14 26 27 34 38 46 53 65 74 [86] 5. 构成初始堆（即建堆）的过程：1 2 3 4 5 6 7 8 9 10(0) 46 74 53 14 26 38 86 65 27 34(1) 46 74 53 14 26 38 86 65 27 34(2) 46 74 53 14 26 38 86 65 27 34(3) 46 74 38 14 26 53 86 65 27 34(4) 46 14 38 27 26 53 86 65 74 34(5) 14 26 38 27 34 53 86 65 74 46进行堆排序的过程：(0) 14 26 38 27 34 53 86 65 74 46(1) 26 27 38 46 34 53 86 65 74 [14](2) 27 34 38 46 74 53 86 65 [26 14](3) 34 46 38 65 74 53 86 [27 26 14](4) 38 46 53 65 74 86 [34 27 26 14](5) 46 65 53 86 74 [38 34 27 26 14](6) 53 65 74 86 [46 38 34 27 26 14](7) 65 86 74 [53 46 38 34 27 26 14](9) 86 [74 65 53 46 38 34 27 26 14]6.(0) [46] [74] [53] [14] [26] [38] [86] [65] [27] [34](1) [46 74] [14 53] [26 38] [65 86] [27 34](2) [14 46 53 74] [26 38 65 86] [27 34](3) [14 26 38 46 53 65 74 86] [27 34](3) [14 26 27 34 38 46 53 65 74 86]。