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

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

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

在快速排序方法中，进行每次划分时，是从当前待排序区间的（①)向（②)依次查找出处于逆序的元素并交

换之，最后将基准元素交换到一个确定位置，从而以该位置把当前区间划分为前后两个子区间。

当待排序区间R[low..high]中的排序码值都相同时，Partition函数返回的值是什么？此时快速排序的运行时间是多少？能否修改Partition，使得划分结果是均衡的(即划分后左、右区间的长度大致相等)？

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

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

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

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

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

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

A、锦标赛排序

B、快速排序

C、基数排序

D、归并排序

A.冒泡排序

B.快速排序

C.直接插入排序

D.折半插入排序

则在起泡排序过程中，什么情况下排序码会朝向与排序相反的方向移动，试举例说明。在快速排序过程中有这种现象吗？