问答题
阅读下列说明，回答问题1至问题3。
[说明]
快速排序是一种典型的分治算法。采用快速排序对数组A[P..r]排序的3个步骤如下。
(1)分解：选择一个枢轴(pivot)元素划分数组。将数组A[p..r]划分为两个子数组(可能为空)A[p..g-1]和A[q+1..]，使得A[g]大于等于A[p..q-1]中的每个元素，小于A[q+1..r]中的每个元素。q的值在划分过程中计算。
(2)递归求解：通过递归的调用快速排序，对子数组A[p..q-1]和A[q+1..r]分别排序。
(3)合并：快速排序在原地排序，故不需合并操作。
[问题1]
下面是快速排序的伪代码，请填补其中的空缺。伪代码中的主要变量说明如下。
A：待排序数组。
p，r：数组元素下标，从p到r。
q：划分的位置。
x：枢轴元素。
i：整型变量，用于描述数组下标。下标小于或等于i的元素的值小于或等于枢轴元素的值。
j：循环控制变量，表示数组元素下标。
QUICKSORT (A,p， r)
if (p＜r)
q = PARTITION(A,p,r)；
QUICKSORT(A，p，q-1)；
QUICKSORT (A，q+1，r)；
PARTITION (A，p，r)
x=A[r]; i=p-1；
for(j=p；j≤r-1; j++)
if(A[j]≤x)
i=i+1;
交换A[i]和A[j]
交换 (1) 和 (2) //注：空(1)和空(2)答案可互换，但两空全部答对方可得分
return (3)
[问题2]
(1)假设要排序包含n个元素的数组，清给出在各种不同的划分情况下，快速排序的时间复杂度，用0记号。最佳情况为 (4) ，平均情况为 (5) ，最坏情况为 (6) 。
(2)假设要排序的n个元素都具有相同值时，快速排序的运行时间复杂度属于哪种情况? (7) 。(最佳、平均、最坏)
[问题3]
(1)待排序数组是否能被较均匀地划分对快速排序的性能有重要影响，因此枢轴元素的选取非常重要。有人提出从待排序的数组元素中随机地取出一个元素作为枢轴元素，下面是随机化快速排序划分的伪代码。利用原有的快速排序的划分操作，请填充其中的空缺处。其中，RANDOM(i/j)表示随机取i到j之间的一个数，包括i和j。
RANDOMIZED-PARTITION(A,p,r)
i= RANDOM(p，r);
交换 (8) 和 (9) ；//注：空(8)和空(9)答案可互换
return PARTITION(A,p,r);
(2)随机化快速排序是否能够消除最坏情况的发生? (10) 。(是或否)
【正确答案】[问题1] (1)A[i+1] (2)A[r]
(3)(i+1)或++i (其中(1)和(2)的内容可互换)
{或者(1)A[++i] (2)A[r]或A[q] (3)i(其中(1)和(2)的内容可互换)}
[问题2] (4) O(nlog2n) (5) O(nlog2n) (6)O(n2)(7)最坏
[问题3] (8)A[i] (9)A[r](其中(8)和(9)可互换) (10)否
【答案解析】[分析] 本题是一个算法分析题，一方而考查考生对分治算法的快速排序的理解，另一方面考查考生对伪代码、快速排序的复杂度的掌握，做题的关键是要读懂题干，理解题干中对算法的描述。
[问题1] 本问题考查伪代码。题中QUICKSORT(A，p，r)函数是采用了递归方法来处理的。快速排序的核心就是找到可划分的位置g，当找到划分位置q以后，再用递归的方法分别对QUICKSORT(A,p，q-1)和QUICKSORT(A，q+1，r)继续找可划分位置。函数PARTITION(A，p，r)的功能是求划分位置。在PARTITION(A，p，r)中，是把最后一个元素作为枢轴元素，x=A[r]; for循环语句用于实现一趟划分，比x小的则在A[i+1]的前头，比x大的则在A[i]的后头。当循环结束以后，将枢轴元素与A[i+1]元素对换，对换以后A[i+1]这个元素的位置就确定了，将它返回作为前段数组的结束位置，作为后段数组的起始地址。所以第(1)空填A[i+1]，第(2)空填A[r]，第(3)空填(i+1)或++i。
[问题2] 本问题考查快速排序的时间复杂度。快速排序的时间主要耗费在划分操作上，对长度为k的区间进行划分，共需要k-1次关键字的比较。时间复杂度都分三种情况：最坏情况、平均情况和最好情况。最坏情况是每次划分选取的基准都是当前无序区中关键字最小f或最大)的记录，划分结果是基准左边的子区间为空(或右边的子区间为空)，而划分所得的另一个非空的子区间中记录数目，仅仅比划分前的无序区中记录个数减少一个。因此，快速排序必须做n-1次划分，第i次划分开始时区间长度为n-i+1，所需的比较次数为n-i(1≤i≤n-1)，故总的比较次数达到最大值：n(n-1)/2。这样，每次取当前无序区的第1个记录为基准，那么当文件的记录已按递增或递减排列时，每次划分所取的基准就是当前无序区中关键字最小(或最大)的记录，因此快速排序所需的比较次数最多，此时时间复杂度是O(n2)。最好情况下，每次划分所需的基准都是当前无序区的“中值”记录，划分的结果是基准的左、右两个无序子区间的长度大致相等，总的关键字比较次数为：O(nlog2n)。就平均性能而言，它是基于关键字比较的内部排序算法中速度最快的，快速排序因此得名，它的平均时间复杂度为：O(nlog2n)。若n个元素都具有相同的值，无论怎么选择，所选取的基准都是当前无序区中关键字最大(或最小)的记录，属于最坏情况。
[问题3] 本问题考查快速排序随机化排序方法。随机化的快速排序与一般的快速排序算法差别很小。但随机化后，算法的性能大大提高了，尤其是对初始化有序的文件，一般不可能导致最坏情况发生。算法的随机化不仅仅适用于快速排序，也适用于其他需要数据随机分布的算法。但是也不能绝对消除最坏情况的发生，所以第(10)空填：否。