使用递归的快速排序算法时，为了保证排序过程的时间复杂度不超过O(nlog₂n)，必须做到()。

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

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

A、锦标赛排序

B、快速排序

C、基数排序

D、归并排序

在归并排序中，进行每趟归并的时间复杂度为（①)，整个排序过程的时间复杂度为（②)，空间复杂度为（③)。

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

下面是一个快速排序的逆归算法。为了避免最坏情况，取基准记录pivot采用从lelt，right和中取中间值，并交换到low位置的办法。数组A存放待排序的一组记录，数据类型为T，left和right是待排序子区间的最左端点和最右端点。

(1)实现三者取中子程序mediancy(A，left，right);

(2)改写QuickSort算法，不用栈消去第二个递归调用QuickSort(A，pivotPos+1，right);

(3)继续改写QuickSort算法，用栈消去剩下的递归调用。

快速排序在平均情况下的时间复杂度为（①)，在最坏情况下的时间复杂度为（②).

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

A、先排小子区间

B、先排大子区间

C、划分基准为三者取中

D、采用链表排序

T.

(1)该算法的功能是什么？

(2)若待排序数据序列为(10，20，30，40，50，60)，给出每次while执行的结果序列。

(3)若待排序数序列为(60，50，40，30，20，10)，给出每次while执行的结果序列。

A.冒泡排序

B.快速排序

C.直接插入排序

D.折半插入排序