第9章 排序

单项选择题

1.在所有排序方法中，关键字比较的次数与记录的初始排列次序无关的是 。 A. 希尔排序 B. 起泡排序 C. 插入排序 D. 选择排序

2.设有 10000 个无序的元素，希望用最快的速度挑选出其中前 10 个最大的元素，排序方法最好选用 。

A. 起泡排序 B. 快速排序 C. 堆排序 D. 基数排序

3.在待排序的元素序列基本有序的前提下，效率最高的排序方法是 。 A. 插入排序 B. 选择排序 C. 快速排序 D. 归并排序

4.一组记录的排序码为(46，79，56，38，40，84)，则利用堆排序的方法建立的初始堆为 。 A. 79，46，56，38，40，80 B. 84，79，56，38，40，46 C. 84，79，56，46，40，38 D. 84，56，79，40，46，38

5.在下列算法中， 算法可能出现下列情况：在最后一趟开始之前，所有的元素都不在其最终的位置上。

A．堆排序 B．冒泡排序 C．插入排序 D.快速排序

6.一组记录的关键码为(46，79，56，38，40，84)，则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为 。

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

7.一组记录的排序码为(48，16， 79，35，82，23，36，72)，按归并排序的方法对该序列进行一趟归并后的结果为 。

A. 16 48 35 79 23 82 36 72 B. 16 35 48 79 82 23 36 72 C. 16 48 35 79 82 23 36 72 D. 16 35 48 79 23 36 72 82

8.排序方法中，从未排序序列中依次取出元素与已排序序列（初始时为空）中的元素进行比较，将其放入已排序序列的正确位置上的方法，称为 。 A. 希尔排序 B. 起泡排序 C. 插入排序 D. 选择排序

9.排序方法中，从未排序序列中挑选元素，并将其依次放入已排序序列（初始时为空）的一端的方法，称为 。

A. 希尔排序 B. 归并排序 C. 插入排序 D. 选择排序

1-5 DCABC

29

6-9 CACD 填空题

1.在对一组记录(54，38，96，23，15，72，60，45，83)进行直接插入排序时，当把第 8 个记录 45 插入到有序表时，为寻找插入位置需比较 次。

2.对于关键字序列（12，13，11，18，60，15，7，20，25，100），用筛选法建堆，必须从键值为 的关键字开始。

3.对 n个记录的表 r[1..n]进行简单选择排序，所需进行的关键字间的比较次数为 4.在插入和选择排序中，若初始数据基本正序，则选用 ；若初始数据基本反序则选用 。 插入排序 选择排序

5.对 n 个元素的序列进行起泡排序时，最少的比较次数是 。 6. 排序不需要进行记录关键字间的比较。 1. 5 2. 60 3. n(n-1)/2 4. ① ② 5. n-1 6. 基数

综合题

1.已知序列49．38，65，97，76，13，27，请给出采用起泡排序对该序列作升序排列的每一趟的结果。

2.已知序列{503，87，512，61，908，170，897，275，653，462}，采用快速排序法对该序列作升序排序时的每一趟的结果。

3.已知序列{265，301，751，129，937，863，742，694，076，438}，采用基数排序法对该序列作升序排序时的每一趟的结果。

4.已知序列{503，17，512，908，170，897，275，653，426，154，509，612，677，765，703，94}，请给出采用希尔排序法(d1=8)对该序列作升序排序时的每一趟的结果。 5.已知序列{35，89，61，135，78，29，50}，请给出采用插入排序法对该序列作升序排序时的每一趟的结果。

6.已知序列{11，18，4，3，6，15，1，9，18，8}，请给出采用归并排序法对该序列作升序排序时的每一趟的结果。

1.解：根据起泡排序法的基本思想，比较无序区中相邻关键字。按照大小关系调整其位置，本题的解法是，通过比较已知序列中相邻关键字，并根据需要调整其位置、重复此过程直到没有关键字的位置交换为止，结果正好是关键字的升序排列。

30

依题意，采用起泡排序法排序的各趟的结果如下： 初始：49，38、65，97，76，13，27 第一趟；38，49，65，76，13，27，97 第二趟：38，49，65，13，27，76，97 第二趟：38，49．13，27，65，76，97 第四趟：38，13，27，49，65，76，97

第五趟：13，27，38，49，65．76，97 第六趟：13，27，38，49，65，76，97 第六题无元素交换，排序结束。

2.依题意，采用快速排序法排序的各趟的结果如下：

初始：503，87，512，61，908，170，897，275，653，462 第 1 趟：[462，87，275，61，170] 503 [897，908，653，512] 第 2 趟：[170，87，275，61] 462，503 [897，908，653，512] 第 3 趟：[61，87] 170 [275] 462，503 [897，908，653，512] 第 4 趟：61 [87] 170 [275] 462，503 [897，908，653，512] 第 5 趟：61，87，170 [275] 462，503 [897，908，653，512] 第 6 趟：61，87，170，275，462，503 [897，908，653，512] 第 7 趟：61，87，170，275，462，503 [512，653] 897 [908] 第 8 趟：61，87，170，275，462，503，512 [653] 897 [908] 第 9 趟：61，87，170，275，462，503，512，653，897 [908] 第 10 趟：61，87，170，275，462，503，512，653，897，908 3.依题意，采用基数排序法排序的各趟的结果如下：

初始态：265 301 751 129 937 863 742 694 076 438

第一趟：[] [301 751] [742] [863] [694] [265] [076] [937] [438] [129] 第二趟：[301] [] [129] [937 438] [742] [751] [863 265] [076] [] [694] 第三趟：[075] [129] [265] [301] [438] [] [694] [742 751] [863] [937] 4.依题意，采用希尔排序法排序的各趟的结果如下：

初始：503，17，512，908，170，897，275，653，426，154，509，612，677，765，703，94

第 1 趟(d1=8)：426，17，509，612，170，765，275，94，503，154，512，908，677，897，703，653

第 2 趟(d2=4)：170，17，275，94，426，154，509，612，503，765，512，653，677，897，703，908

第 3 趟(d3=2)：170，17，275，94，426，154，503，612，509，653，512，765，677，897，703，908

第 4 趟(d1=1)：17，94，154，170，275，426，503，509，512，612，653，677，703，765，897，908

5.依题意，采用直接插入排序法排序的各趟的结果如下

初始：(35)89，61，135，78，29，50

31

第一趟：（35，89，)6l，135，78，29，50 第二趟：(35，61，89，)135，78，29，50 第三趟：(35，6l，89，135)78，29，50 第四趟：(35，61，78，89，135)29，50 第五趟：(29，35，61，78，89．135)50 第六趟：(29，35，50，61，78，89，135)

依题意，采用归并排序法排序的各趟的结果如下：

初始：11，18，4，3，6，15，1，9，18，8

第 1 趟：[11，18] [3，4] [6，15] [1，9] [8，18] 第 2 趟：[3，4，11，18] [1，6，9，15] [8，18] 第 3 趟：[3，4，11，18] [1，6，8，9，15，18] 第 4 趟：[1，3，4，6，8，9，11，12，18，18] 第 4 趟归并完毕，则排序结束。

32

6.