当所有待排序记录的排序码都相等，计算下列排序方法的运行时间：(1) 直接插入排序;(2)堆排序;(3)起泡排序;(4)简单选择排序。

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

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

(1)直接插入排序

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

(3)起泡排序

(4)快速排序

(5)简单选择排序

(6)锦标赛排序

(7)堆排序

(8)二路归并排序

(9)基数排序

A.基数排序

B.起泡排序

C.希尔排序，增量3

D.简单选择排序

E.直接插入排序

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

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

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

①直接插入排序;

②折半插入排序;

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

④冒泡排序;

⑤快速排序;

⑥简单选择排序;

⑦二路归并排序。

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

若排序码是非负整数，快速排序、归并排序、堆排序和基数排序哪一种最快？若要求辅助空间为O（1)，则应选择哪一种？若要求排序是稳定的且排序码是浮点数，则应选择哪一种？

如果有一个时间复杂性为O（n²)的算法（如起泡排序、选择排序或插人排序等)，在有200个元素

如果有一个时间复杂性为O(n²)的算法(如起泡排序、选择排序或插人排序等)，在有

200个元素的数组上运行需要耗时3.1ms，试问在下列类似的数组上运行大约需要多长时间？

(1)具有400个元素;

(2)具有40000个元素。

A.冒泡排序

B.快速排序

C.直接插入排序

D.折半插入排序

同的排序中间结果，设要将集合(tang，deng，an，wan，shi，bai，fang，l)中的排序码按升序排列，则(1)是起泡排序一趟扫描的结果，(2)是初始步长为4的希尔排序一趟扫描的结果。(3)是二路归并排序一趟扫描的结果。(4)是以第一个元素为分界元素的快速排序一趟扫描的结果。(5)是堆排序初始建堆的结果。

A.deng，tang，an，wan，bai，shi，fang，li

B.an，deng，bai，li，shi，tang，iang，wan

C.deng，an，tang，shi，bai，fang，li，wan

D.deng，tang，an，wan，bai，shi，fang，li

E.an，bai，deng，fang，li，shi，tang，wan

F.an，tang，deng，wan，shi，bai，fang，li

G.li，deng，an，shi，bai，fang，tang，wan

H.shi，bai，an，li，tang，deng，fang，wan