三、关于快速排序算法QUICKSORT (1)试用几话简单地描述快速排序算法 QUICKSORT 的算法思想。 (2)试将下面的 QUICKSORT 算法的子过程 quicksort 的伪代码程序中的第1,2,3,4步补充完整。 算法QUICKSORT INPUT:n个元素数组A[1··n] OUTPUT:按非降序排列的数组A 1. quicksort(A, 1, n) 过程 quicksort(A,low, high) 1.if??? then 2. 3 5. end if (3)试对 QUICKSORT算法进行最坏情况分析，QUICKSORT 算法的最坏情况是怎样的?最坏情况何时会发生?请至少举一个导致最坏情况发生的输入示例。在最坏情况下，QUICKSORT算法执行的总元素比较次数是多少?从而可以得出结论，在最坏情况下，QUICKSORT算法的时间复杂度是怎样的?(4)为了避免上述最坏情况的发生，可以怎样对 QUICKSORT 算法进行改进?试列式分析这样改进之后的算法时间复杂度是怎样的?

1. 快速排序算法QUICKSORT的算法思想是：通过一趟排序将待排序记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，然后再按此方法对这两部分记录分别进行快速排序，以达到整个序列有序的目的。
2. 过程quicksort的伪代码程序中的第1,2,3,4步补充完整如下：

quicksort(A, low, high)
1. if low < high then
2.    pivotpos = partition(A, low, high)
3.    quicksort(A, low, pivotpos - 1)
4.    quicksort(A, pivotpos + 1, high)
5. end if

其中，partition是快速排序算法中用于划分数组的子过程。
3. QUICKSORT算法的最坏情况是每次选取的枢轴都是当前子数组中的最大或最小值，这种情况下，每次划分只能将子数组的长度减少1，即子数组未能得到有效缩小，递归深度达到n，时间复杂度为O(n^2)。例如，对于一个已经排好序的数组，如果每次都选择第一个元素作为枢轴，则会导致最坏情况的发生。
在最坏情况下，QUICKSORT算法执行的总元素比较次数是n(n-1)/2，即O(n^2)。
4. 为了避免最坏情况的发生，可以采用以下改进措施：
- 随机选取枢轴，可以避免每次都选取最大或最小元素的情况，降低发生最坏情况的概率。
- 三数取中法，即选取子数组的头、尾、中间三个元素的中位数作为枢轴，可以避免选取到最大或最小元素的情况，并且对于已经有序的数组也能有较好的效果。
- 在递归深度达到一定程度时，采用其他排序算法如插入排序等，可以避免递归深度过深的情况。
采用随机选取枢轴的改进，可以将最坏情况的概率降低到极低的程度，时间复杂度的期望值为O(nlogn)。