首页 › 题库 › GESP编程能力等级认证 › 7.2 快速排序

GESP-C++五级 题库

共 9 道题 · 按题型筛选,点「查看答案」核对解析
章节 7.2 快速排序 清除
1 单选题 适中 GESP编程能力等级认证 ·GESP-C++五级 · 7.2 快速排序

下述C++代码实现了快速排序算法,下面说法错误的是( )。

A

. 快速排序之所以叫“快速”,是因为它在平均情况下运行速度较快,常数小、就地排序,实践中通常比归并排序更高效。

B

在平均情况下,划分的递归层数为 log n,每层中的总循环数为 ,总时间为 O(nlog n)。

C

在最差情况下,每轮划分操作都将长度为 的数组划分为长度为 0 和 n-1的两个子数组,此时递归层数达到 n,每层中的循环数为 ,总时间为 。

D

划分函数 partition 中“从右往左查找”与“从左往右查找”的顺序可以交换

答案与解析
正确答案:D
这道题暂未补解析。
题目详情
2 单选题 适中 GESP编程能力等级认证 ·GESP-C++五级 · 7.2 快速排序

关于下述C++代码的快速排序算法,说法【错误】的是?( )

int randomPartition(std::vector<int>& arr, int low, int high) {
    int random = low + rand() % (high - low + 1);
    std::swap(arr[random], arr[high]);
    int pivot = arr[high];
    int i = low - 1;
    for (int j = low; j < high; j++) {
        if (arr[j] <= pivot) {
            i++;
            std::swap(arr[i], arr[j]);
        }
    }
    std::swap(arr[i + 1], arr[high]);
    return i + 1;
}
void quickSort(std::vector<int>& arr, int low, int high) {
    if (low < high) {
        int pi = randomPartition(arr, low, high);
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}
A
在 randomPartition 函数中,变量 i 的作用是记录大于基准值的元素的边界
B
randomPartition 函数随机选择基准值,可以避免输入数据特定模式导致的最坏情况下时间复杂度
C
快速排序平均时间复杂度是 O(n log n)
D
快速排序是稳定排序算法
答案与解析
正确答案:D
这道题暂未补解析。
题目详情
3 单选题 适中 GESP编程能力等级认证 ·GESP-C++五级 · 7.2 快速排序

考虑以下C++代码实现的快速排序算法,将数据从小到大排序,则横线上应填的最佳代码是?( )

int partition(vector<int>& arr, int low, int high) {
    int pivot = arr[high]; // 基准值
    int i = low - 1;
    for (int j = low; j < high; j++) {
        ____________________ // 在此处填入代码
    }
    swap(arr[i + 1], arr[high]);
    return i + 1;
}
// 快速排序
void quickSort(vector<int>& arr, int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high);
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}
A
if (arr[j] > pivot) {
    i++;
    swap(arr[i], arr[j]);
}
B
if (arr[j] < pivot) {
    i++;
    swap(arr[i], arr[j]);
}
C
if (arr[j] < pivot) {
    swap(arr[i], arr[j]);
    i++;
}
D
if (arr[j] == pivot) {
    i++;
    swap(arr[i], arr[j]);
}
答案与解析
正确答案:B

快速排序是一种分治算法,其基本步骤如下:

选择基准:从数组中选择一个元素作为基准(通常选择最后一个元素)。

分区:重新排列数组,使得所有比基准小的元素放在基准前面,所有比基准大的元素放在基准后面。分区完成后,基准就位于其最终排序后的正确位置。

递归排序:递归地对基准前后的子数组进行快速排序。

在分区过程中:

i初始化为low - 1,表示小于基准的区域最初为空。

j从low到high - 1遍历数组。

如果arr[j]小于pivot,则i增加1,并将arr[i]和arr[j]交换。这样,arr[i]现在是一个小于pivot的元素。

本题答案为选项B。

题目详情
4 单选题 适中 GESP编程能力等级认证 ·GESP-C++五级 · 7.2 快速排序

考虑以下C++代码实现的快速排序算法:

int partition(vector<int>& arr, int left, int right) {
	int pivot = arr[right]; // 基准值
	int i = left - 1;
	
	for (int j = left; j < right; j++) {
		if (arr[j] < pivot) {
			i++;
			swap(arr[i], arr[j]);
		}
	}
	swap(arr[i + 1], arr[right]);
	return i + 1;
}

// 快速排序
void quickSort(vector<int>& arr, int left, int right) {
	if (left < right) {
		int pi = partition(arr, left, right);
		quickSort(arr, left, pi - 1);
		quickSort(arr, pi + 1, right);
	}
}

以下关于快速排序的说法,正确的是( )。

A
快速排序通过递归对子问题进行求解。
B
快速排序的最坏时间复杂度是 O(nlogn)。
C
快速排序是一个稳定的排序算法。
D
在最优情况下,快速排序的时间复杂度是 O(n)。
答案与解析
正确答案:A
这道题暂未补解析。
题目详情
5 单选题 适中 GESP编程能力等级认证 ·GESP-C++五级 · 7.2 快速排序

假设快速排序算法的输入是一个长度为 n 的已排序数组,且该快速排序算法在分治过程总是选择第一个元素作为基准元素。下面选项( )描述的是在这种情况下的快速排序行为。

A
快速排序对于此类输入的表现最好,因为数组已经排序。
B
快速排序对于此类输入的时间复杂度是 O(nlogn)。
C
快速排序对于此类输入的时间复杂度是O(n2)。
D
快速排序无法对此类数组进行排序,因为数组已经排序。
答案与解析
正确答案:C

快速排序的过程是,每次选择一个基准值,比基准值大的放到它的右边 ,比基准值小的放到它的左边,但是这个序列是一个有序序列,且每次都是选择最小的元素作为基准值,所以每次所有的值都会放到基准值的右边,也就是说,每次都只是把基准值这个位置排序好。

题目详情
6 单选题 适中 GESP编程能力等级认证 ·GESP-C++五级 · 7.2 快速排序

为了正确实现快速排序,下面横线上的代码应为( )。

void qsort(vector<int>& arr, int left, int right) {
	int i, j, mid;
	int pivot;
	
	i = left;
	j = right;
	mid = (left + right) / 2; // 计算中间元素的索引
	pivot = arr[mid]; // 选择中间元素作为基准值
	
	do {
		while (arr[i] < pivot) i++;
		while (arr[j] > pivot) j--;
		if (i <= j) {
			swap(arr[i], arr[j]); // 交换两个元素
			i++; j--;
		}
	} ________________________________; // 在此处填入代码
	if (left < j) qsort(arr, left, j); // 对左子数组进行快速排序
	if (i < right) qsort(arr, i, right); // 对右子数组进行快速排序
}
A
while (i <= mid)
B
while (i < mid)
C
while (i < j)
D
while (i <= j)
答案与解析
正确答案:D

快速排序的分区过程中,我们使用两个指针i和j分别从左到右和从右到左遍历数组,将小于基准值的元素放到基准值的左边,大于基准值的元素放到右边。

具体的分区过程如下:

首先选择一个基准值pivot,通常选择中间元素arr[mid]。

使用两个指针i和j,分别从数组的左右两端开始向中间移动。

i从左向右移动,直到找到一个大于或等于pivot的元素。

j从右向左移动,直到找到一个小于或等于pivot的元素。

如果i <= j,则交换arr[i]和arr[j],然后i向后移动一位,j向前移动一位。

重复步骤2和3,直到i大于j,此时所有小于等于pivot的元素都在pivot的左边,所有大于等于pivot的元素都在pivot的右边。

在填写横线上的代码时,应该使用while (i <= j),因为分区过程应该持续进行直到i超过j,这样保证了整个分区过程的完成。

题目详情
7 单选题 适中 GESP编程能力等级认证 ·GESP-C++五级 · 7.2 快速排序

在快速排序中,选择的主元素(pivot)会影响算法的(   )。

A
不影响
B
时间复杂度
C
空间复杂度
D
时间复杂度和空间复杂度
答案与解析
正确答案:B
这道题暂未补解析。
题目详情
8 单选题 适中 GESP编程能力等级认证 ·GESP-C++五级 · 7.2 快速排序

下面的C++代码实现对list的快速排序,有关说法,错误的是(   )。

A

qSort(less) + qSort(greater) + (vector<int>)pivot

B

(vector<int>)pivot + (qSort(less) + qSort(greater))

C

(qSort(less) + (vector<int>)pivot + qSort(greater))

D

qSort(less) + pivot + qSort(greater)

答案与解析
正确答案:C
这道题暂未补解析。
题目详情
9 判断题 偏易 GESP编程能力等级认证 ·GESP-C++五级 · 7.2 快速排序

通过在数组的第一个、最中间和最后一个这3个数据中选择中间值作为枢轴(比较基准),快速排序算法可降低落入最坏情况的概率。

A
对
B
错
答案与解析
正确答案:对
确定数组的第一个、最中间和最后一个元素的值;比较这三个元素的大小;选取其中数值上处于中间位置的元素作为枢轴;将该枢轴用于划分操作,使小于枢轴的元素置于其左,大于枢轴的元素置于其右;完成一次划分后递归处理左右子数组。
题目详情