在快速排序算法中，基础子问题可以是1个元素的数组，也可以是10个元素的数组。前者不需要排序，后者可以用冒泡排序。

正确答案：这是一道考查快速排序算法伪代码的分析题。快速排序是对冒泡排序的一种改进其基本思想是：通过一趟排序将要排序的数据分割成独立的两部分其中一部分的所有数据都比另外一部分的所有数据都要小然后再按此方法对这两部分数据分别进行快速排序整个排序过程可以递归进行以此达到整个数据变成有序序列。快速排序最核心的处理是进行划分即PARTITION操作：根据枢轴元素的值把一个较大的数组分成两个较小的子数组一个子数组的所有元素的值小于等于枢轴元素的值一个子数组的所有元素的值大于枢轴元素的值而子数组内的元素不排序。划分时以最后一个元素为枢轴元素从左到右依次访问数组的每一个元素判断其与枢轴元素的大小关系并进行元素的交换如图2-30所示。 在[问题1]所给出的伪代码中当for循环结束后A[p..i]中的值应小于等于枢轴元素值x而A[i+1..r-1]中的值应大于枢轴元素值x。此时A[i+1]是第一个比A[r]大的元素因此A[r]与A[i+1]进行交换得到划分后的两个子数组。PARTITION操作返回枢轴元素的位置因此返回值为i+l。
这是一道考查快速排序算法伪代码的分析题。快速排序是对冒泡排序的一种改进，其基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。快速排序最核心的处理是进行划分，即PARTITION操作：根据枢轴元素的值，把一个较大的数组分成两个较小的子数组，一个子数组的所有元素的值小于等于枢轴元素的值，一个子数组的所有元素的值大于枢轴元素的值，而子数组内的元素不排序。划分时，以最后一个元素为枢轴元素，从左到右依次访问数组的每一个元素，判断其与枢轴元素的大小关系，并进行元素的交换，如图2-30所示。 在[问题1]所给出的伪代码中，当for循环结束后，A[p..i]中的值应小于等于枢轴元素值x，而A[i+1..r-1]中的值应大于枢轴元素值x。此时A[i+1]是第一个比A[r]大的元素，因此A[r]与A[i+1]进行交换，得到划分后的两个子数组。PARTITION操作返回枢轴元素的位置，因此返回值为i+l。

正确答案：A
本题考查快速排序算法。快速排序算法是应用最为广泛的排序算法之一。其基本思想是将n个元素划分为两个部分：一部分元素值小于某个数；另一部分元素值大于某个数，该数的位置确定；然后进一步划分前面部分和后面部分。根据该叙述，可以知道，这里采用的是分治算法设计策略。由于已知划分操作的时间复杂度为，不需要合并子问题的答案。对于最好的情况，应该是每次划分都把n个元素划分为大约2个n/2个元素的子数组，此时T(n)=2T(n/2)+解该递归式，可得时间复杂度为。若刚好划分的极度不均衡，即每个划分刚好把n个元素划分为一边0个元素，一边n-l个元素，此时T(n)=T(n/1)+解该递归式，可得时间复杂度为。

答案：D

解析：

答案：D

解析：

答案：B

解析：

正确答案：A

正确答案：A

答案：A

解析：

答案：B

解析：