排序趟数与序列的原始状态有关的排序方法是 排序法

结束后关键字序列的状态。

①直接插入排序;

②折半插入排序;

③希尔排序(增量选取5，3，1);

④冒泡排序;

⑤快速排序;

⑥简单选择排序;

⑦二路归并排序。

以关键字序列（tim,kay,eva,roy,dot,jon,kim,ann,tom,jim,guy.amy)为例，手工执行以下排序算法（按字典序比较关键字的大小)，写出每一趟排字结束时的关键字状态! （1)直接插入排序:（2)冒泡排序:（3)直接选择排序: （4)快速排序:（5)归并排序:（6)基数排序。

设待排序的排序码序列为（12，2，16，30，28，10，16，20，6，18)，试分别写出使用以下排序方法每趟排序后

的结果，并说明做了多少次排序码比较，注意，后一个16附带一个“*”表明这是一个与前面某一个元素具有相同排序码值(16)的元素。

(1)直接插入排序

(2)希尔排序(增量为5，2，1)

(3)起泡排序

(4)快速排序

(5)简单选择排序

(6)锦标赛排序

(7)堆排序

(8)二路归并排序

(9)基数排序

在二路归并排序中，对n个元素进行归并的趟数为（)。

按排序策略分类，起泡排序属于（①)。对n个元素的序列进行排序时，如果待排序元素序列的初始排列已

经全部有序，则起泡排序过程中需进行(②)次元素值的比较，(③)次元素值的交换。如果待排序元素序列的初始排列完全逆序，则起泡排序过程中需进行(④)次元素值的比较，(⑤)次元素的交换。(1)供选择的答案：A、插入排序;B、选择排序;C、交换排序;D、分配排序;E、归并排序.

在下列指定的排序算法中，（)使用的附加空间与输人序列的长度及初始排列无关。

A、锦标赛排序

B、快速排序

C、基数排序

D、归并排序

下面关于置换-选择排序的叙述中不正确的是（)。

A、置换-选择排序用于生成外排序的初始归并段

B、置换-选择排序是完成将一个磁盘文件排列成有序文件有效的外排序算法

C、置换-选择排序生成的初始归并段的长度平均是内存工作区的2倍

D、置换-选择排序是一些不等长的初始归并段

数项i扫描，若A[i]≥Ali+1]，则交换它们。第三趟对所有的奇数项扫描，第四趟对所有的偶数项扫描，……，如此反复，直到整个序列全部排好序为止。

(1)这种排序方法结束的条件是什么？

(2)写出奇偶交换排序的算法。

(3)当待排序排序码序列的初始排列是从小到大有序，或从大到小有序时，在奇偶交换排序过程中的排序码比较次数是多少？

假定一组记录的排序码为（46，79，56，38，40，80)，对其进行归并排序的过程中，第二趟归并后的结果为（)，