当待排序区间R[low..high]中的排序码值都相同时，Partition函数返回的值是什么？此时快速排序的

设有n个元素的待排序元素序列为TA[]，元素在序列中随机排列。试编写一个函数、返回序列中按排序码值从小到大排序的第k（0≤k<n)个元素的值。

设待排序的排序码序列为（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个具有不同排序码值的元素进行起泡排序，在（①)情况下排序码比较次数最小;在（②)情况下排序码比较次数最大。

位置位于最中间的一个元奈，在三者之中选择一个其值居中的元素，将其交换到待排序序列的第一个元素位置，再做一趟划分，若设整数数组A有n个元素，设计一个函数，实现上述三者取中并交换到待排序序列第一个元素位置的功能。

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

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

对于快速排序算法，假设待排序的n个数据的取值都相等，则完成排序所需排序码比较次数是（①)，数据移动次数是（②)，递归工作栈所需活动记录个数是（③)。

A、n

B、2(n-1)

C、n(n-l)/2

D、D、log₂n

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

首先对较短的子序列进行排序，试编写相应的算法，并说明在此做法下，快速排序所需要的栈的深度为O(log₂n)，

在快速排序中，要使最坏情况下的空间复杂度为O（log₂n)，要对快速排序做（)修改。

A、先排小子区间

B、先排大子区间

C、划分基准为三者取中

D、采用链表排序