快速排序算法在排序过程中，在待排序数组中确定一个元素为基准元素，根据基准元素把待排序数组划分成两个部分，前面一部分元素值小于等于基准元素，而后面一部分元素值大于基准元素。然后再分别对前后两个部分进一步进行划分。根据上述描述，快速排序算法采用了（）算法设计策略。

成两个部分，前面一部分元素值小于等于基准元素，而后面一部分元素值大于基准元素。然后再分别对前后两个部分进一步进行划分。根据上述描述，快速排序算法采用了 (61) 算法设计策略。已知确定基准元素操作的时间复杂度为，则快速排序算法的最好和最坏情况下的时间复杂度为 (62) 。

A.分治

B.动态规划

C.贪心

D.回溯

阅读以下算法说明，根据要求回答问题1～问题3。

[说明]

快速排序是一种典型的分治算法。采用快速排序对数组A[p..r]排序的3个步骤如下。

1．分解：选择一个枢轴(pivot)元素划分数组。将数组A[p..r]划分为两个子数组(可能为空)A[p..q-1]和A[q+1..r]，使得A[q]大于等于A[p..q-1]中的每个元素，小于A[q+1..r]中的每个元素。q的值在划分过程中计算。

2．递归求解：通过递归的调用快速排序，对子数组A[p..q-1]和A[q+1..r]分别排序。

3．合并：快速排序在原地排序，故无需合并操作。

下面是快速排序的伪代码，请将空缺处(1)～(3)的内容填写完整。伪代码中的主要变量说明如下。

A：待排序数组

p,r：数组元素下标，从p到r

q：划分的位置

x：枢轴元素

i：整型变量，用于描述数组下标。下标小于或等于i的元素的值，小于或等于枢轴元素的值

j：循环控制变量，表示数组元素下标

排序

实验目的：

(1)熟练掌握在顺序表上实现排序的各种方法。

(2)深刻理解各种排序方法的特点，并能灵活运用。

(3)掌握和理解本实验中出现的一些基本的C语言语句。

(4)体会算法在程序设计中的重要性。

实验内容：

编写一个排序菜单程序，在其中调用不同的排序算法，实现对任意无序序列的递增排序操作。在主程序中输入初始序列，分别调用直接插入排序、冒泡排序、直接选择排序、快速排序等排序算法，输出排序后的结果。题目要求：在所有的排序算法中，待排序数据均从数组的0单元放起。

A.冒泡排序

B.插入排序

C.快速排序

D.基数排序

A.冒泡排序

B.希尔排序

C.快速排序

D.堆排序

A.冒泡排序

B.插入排序

C.快速排序

D.基数排序

A.归并排序

B.希尔排序

C.快速排序

D.堆排序

A.冒泡

B.希尔

C.快速

D.堆

A.冒泡

B.希尔

C.快速

D.堆