🏷️ 知识点：快速排序
使用快速排序算法对含 N（N ≥ 3） 个元素的数组 M 进行排序，若第一趟排序将除枢轴外的 N-1 个元素划分为 P 和 Q 两个部分，则下列叙述中，正确的是（ ）。
A. P 和 Q 块间有序 B. P 和 Q 均块内有序 C. P 和 Q 的元素个数大致相等 D. P 和 Q 中均不存在相等的元素
[tag_link]
正确答案：A
本题考察快排的原理，快排第一趟找到枢轴之后，枢轴的左边的元素即 P 块都是小于枢轴的，枢轴的右边的元素即 Q 块是大于枢轴的，所以 P 和 Q 块间有序，然而块内未必是有序的，所以还需要继续对 P 和 Q 两块进行递归快排。
对一组数据（84,47,15,21,25）排序，数据在排序的过程中的变化如下：
A. 堆排序 B. 冒泡排序 C. 快速排序 D. 插入排序
[tag_link]
正确答案：C
观察排序过程中的变化：初始序列为 (84,47,15,21,25)。 第一步变为 (25,47,15,21,84)，这类似于快速排序中选择第一个元素 84 作为枢轴进行分区的结果：将小于 84 的元素移至左边，大于的移至右边，最终 84 被放置到正确位置（末尾）。 第二步变为 (21,25,15,47,84)，这对应于对左子序列 (25,47,15,21) 进行快速排序的分区操作，选择 25 作为枢轴，经过交换和调整后得到此序列。 这些步骤符合快速排序的分区递归特性。
其他排序方法不符：冒泡排序每趟通过相邻交换将最大元素移至末尾，第一趟后应为 (47,15,21,25,84)，与第二步不同； 插入排序逐步构建有序序列，不会直接将 84 移至末尾； 堆排序需先建堆再交换调整，但第二步到第三步的变化不似堆调整过程。 因此，所选方法为快速排序。
对关键码序列 28,16,32,12,60,25,72 快速排序，从小到大一次划分结果为（ ）。
A. (2,5,12,16) 28 (60,32,72) B. (5,16,12) 28 (60,32,72) C. (2,16,12,5) 28 (60,32,72) D. (5,16,2,12) 28 (32,60,72)
[tag_link]
正确答案：B
快速排序的一次划分通常以序列的第一个元素作为基准（pivot）。
对于序列 28,16,32,12,60,25,72，选择 28 作为基准，目标是将序列划分为左边所有元素小于 28，右边所有元素大于 28。 常见划分方法（如 Lomuto 划分）的步骤如下：
- 从左向右扫描，将小于 28 的元素移动到左侧，大于等于 28 的元素留在右侧。 >
- 最终交换基准元素到正确位置。 >
具体过程：初始化基准为 28。 > 遍历序列，小于 28 的元素有 16、12 和 25。 > 通过交换操作，划分后基准 28 位于中间位置，左边为小于 28 的元素（顺序可能改变），右边为大于 28 的元素。 > 划分结果为左边序列 (25,16,12)，基准 28，右边序列 (60,32,72)。 >
观察选项，B 选项为 (5,16,12) 28 (60,32,72)，其中左边有三个元素，与小于 28 的元素个数一致； > 右边为 (60,32,72)，与大于 28 的元素一致。 > 虽然 B 中写为“5”，但根据序列元素推断应为“25”（可能为笔误），且其他选项左边元素个数不符合要求，因此 B 为正确答案。 >
下列选项中，不可能是快速排序第2趟排序结果的是()。
A.2,3,5,4,6,7,9
B.2,7,5,6,4,3,9
C.3,2,5,4,7,6,9
D.4,2,3,5,7,6,9
[tag_link]
正确答案：C
快速排序 的阶段性排序结果的特点是，第 i 趟完成时，会有 i 个以上的数出现在它最终将要出现的位置，即它左边的数都比它小，它右边的数都比它大。
题目问第二趟 排序的结果，即要找不存在两个这样的数的选项。
A 选项中 2、3、6、7、9 均符合，所以 A 排除；
B 选项中，2、9 均符合，所以 B 排除；
D 选项中 5、9 均符合，所以 D 选项排除；
最后看 C 选项，只有 9 一个数符合，所以 C 不可能是快速排序第二趟的结果。
组成原理 12 程序 P 在机器 M 上的执行时间是 20 秒，编译优化后，P 执行的指令数减少到原来的 70%，而 CPI 增加到原来的 1.2 倍，则 P 在 M 上的执行时间是（ ）。
计算机性能指标 A. 8.4 秒 B. 11.7 秒 C. 14 秒 D. 16.8 秒 查看答案与解析 收藏 正确答案： 不妨设原来指令条数为 X，那么原 CPI 就为 20/x，经过编译优化后，指令条数减少到原来的 70%，即指令条数为 0.7x，而 CPI 增加到原来的 1.2 倍，即 24/x，那么 现在 P 在 M 上的执行时间就为 指令条数×CPI = 0.7x × 24/x = 24x0.7 = 16.8s，选 D。
使用快速排序算法对数据进行升序排序，若经过一次划分后得到的数据序列是 68, 11, 70, 23, 80, 77, 48, 81, 93, 88，则该次划分的轴枢（ ）。
A. 11 B. 70 C. 80 D. 81
[tag_link]
正确答案：D
在 快速排序 中，划分过程通常选择一个枢轴元素来将待排序序列划分为两个子序列。因为是升序排序，所以枢纽元素的前半个子序列的值需要都小于枢轴值，后半个子序列的值需要都大于枢轴值。分别从每个选项来看，A 选项的枢轴值为 11，前半个子序列的值只有68，大于枢轴值 11，不符合。B 选项的枢轴值为 70，前半个子序列都小于 70，但后半个子序列存在 23 和 48 小于 70，不符合。C 选项的枢轴值为 80，前半个子序列的值都小于 80，但是后半个子序列存在 48 小于 80，不符合。D 选项的枢轴值为 81，81 前面的元素都小于 81，81 后面的元素都大于 81，符合。因此本题的正确选项为 D。
已知由n(n≥2)个正整数构成的集合A=ak∣0≤k<n，将其划分为两个不相交的子集A1和A2，元素个数分别是n1和n2，A1和A2中元素之和分别为S1和S2。设计一个尽可能高效的划分算法，满足∣n1−n2∣最小且∣S1−S2∣最大。要求：
(1) 给出算法的基本设计思想。
(2) 根据设计思想，采用 C 或 C++ 语言描述算法，关键之处给出注释。
(3) 说明你所设计算法的时间复杂度和空间复杂度。
1）算法的基本设计思想由题意知，将最小的⌊n/2⌋个元素放在A1中，其余的元素放在A2中，分组结果即可满足题目要求。仿照快速排序的思想，基于枢轴将个整数划分为两个子集。根据划分后枢轴所处的位置i分别处理：
- 若i=⌊n/2⌋，则分组完成，算法结束；
- 若i<⌊n/2⌋，则枢轴及之前的所有元素均属于A1,继续对 i 之后的元素进行划分；
- 若i>⌊n/2⌋，则枢轴及之后的所有元素均属于A2，继续对i之前的元素进行划分；基于该设计思想实现的算法，无须对全部元素进行全排序，其平均时间复杂度是O(n)，空间复杂度是O(1)。
2）算法实现实现
[tag_link]
参考 快速排序的单向递归算法。
int partition(int a[], int low, int high) {
int l = low;
int r = high;
int pivot = a[l];
while (l < r) {
while (l < r && a[r] >= pivot) {
r--;
}
a[l] = a[r];
while (l < r && a[l] <= pivot) {
l++;
}
a[r] = a[l];
}
a[l] = pivot;
return l;
}
// 按照第 k 个元素进行分区
void quickSelect(int a[], int low, int high, int k) {
if (low < high) {
int pivotIndex = partition(a, low, high);
if (pivotIndex == k) {
return
} else if (pivotIndex < k) {
quickSelect(a, pivotIndex+1, high, k);
} else {
quickSelect(a, low, pivotIndex-1, k);
}
}
}
// 空间复杂度：O(1)
// 时间复杂度：O(n)
void solve(int a[], int n) {
quickSelect(a, 0, n-1, n/2);
int S1 = 0;
int S2 = 0;
for (int i = 0; i < n/2; i++) {
S1 += a[i];
}
for (int i = n/2; i < n; i++) {
S2 += a[i];
}
return S2 - S1;
}
3）本参考答案给出的算法平均时间复杂度是O(n), 空间复杂度是O(1)。