8.3 交换排序·习题
复习入口
8.3 交换排序 · 8.3.1 冒泡排序 · 8.3.2 快速排序 · 8.3.2.1 快速排序的性能与应用
本节共24题:选择题20题,综合应用题4题。每题答案紧接题目折叠显示。
文字转录进度:24/24题。已转录题目的题干、选项和解析可编辑;示意图按需保留。
单项选择题
单项选择题 01
原书题目P350 · 解析P353 · 目视转录
对 n 个不同元素用冒泡法从小到大排序,在( )情况下元素交换次数最多。
A. 从大到小排列好的
B. 从小到大排列好的
C. 元素无序
D. 元素基本有序
查看答案与解析
答案:A。
冒泡最少 1 趟、最多 n−1 趟。初始逆序需 n−1 趟,交换次数最多;初始正序只需 1 趟,无交换便可结束。
单项选择题 02
原书题目P350 · 解析P353 · 目视转录
用冒泡排序对 {10,14,26,29,41,52} 从大到小排序,需进行( )次比较。
A. 3
B. 10
C. 15
D. 25
查看答案与解析
答案:C。
冒泡始终调整逆序,交换次数为逆序数。此例相对于目标顺序完全逆序,每个元素向后调整均需比较,共 5+4+3+2+1=15 次。
单项选择题 03
原书题目P351 · 解析P353 · 目视转录
用某算法对 {25,84,21,47,15,27,68,35,20} 排序,变化如下。
- 25,84,21,47,15,27,68,35,20
- 20,15,21,25,47,27,68,35,84
- 15,20,21,25,35,27,47,68,84
- 15,20,21,25,27,35,47,68,84
所采用算法是( )。
A. 选择排序
B. 插入排序
C. 二路归并排序
D. 快速排序
查看答案与解析
答案:D。
选择排序每趟确定一个最终位置,与过程不符;插入排序第 i 趟前 i+1 个元素应有序,也不符。第二步的 20,15 与 21,25 是反序的,不是归并排序。快速排序每趟把基准放最终位置,再划为两个子序列,观察可知符合快速排序。
单项选择题 04
原书题目P351 · 解析P353 · 目视转录
关键码 (46,79,56,38,40,84),用快速排序,以第一个记录为基准,从小到大的一次划分结果为( )。
A. (38,40,46,56,79,84)
B. (40,38,46,79,56,84)
C. (40,38,46,56,79,84)
D. (40,38,46,84,56,79)
查看答案与解析
答案:C。
以 46 为基准,先从后向前找比 46 小的 40,与之交换;再从前向后找比 46 大的 79,与基准交换,得 (40,46,56,38,79,84)。重复前后扫描,直到 46 位于最终位置,得到 C。
单项选择题 05
原书题目P351 · 解析P353 · 目视转录
快速排序在( )情况下最不利于发挥长处。
A. 数据量太大
B. 数据含多个相同值
C. 数据个数为奇数
D. 数据已基本有序
查看答案与解析
答案:D。
基本有序时,每次选首元素为基准导致划分不均,不利于发挥优势。数据随机时基准通常能划为大小较接近的两部分,快速排序优势更明显。
单项选择题 06
原书题目P351 · 解析P353 · 目视转录
就平均性能而言,当前最好的内部排序算法是( )。
A. 冒泡排序
B. 直接插入排序
C. 希尔排序
D. 快速排序
查看答案与解析
答案:D。
A、B 平均达到 ;希尔虽降低直接插入的复杂度,平均性能仍不如快速排序。多种算法平均时间均为 ,而快速排序的常数因子较小。
单项选择题 07
原书题目P351 · 解析P353 · 目视转录
序列 F={2,1,4,9,8,10,6,20} 只能是下列( )算法两趟排序后的结果。
A. 快速排序
B. 冒泡排序
C. 选择排序
D. 插入排序
查看答案与解析
答案:A。
插入排序两趟后前三元素应有序,显然不是。冒泡与选择两趟后应有两个元素在最终位置(最左或最右两端),本序列两端不满足,故只能选快速排序。
另解:最终序列为 1,2,4,6,8,9,10,20。当前位置相同的元素有 4、8、20,而最左、最右两元素未同时就位,所以不可能为冒泡、选择或插入。
单项选择题 08
原书题目P351 · 解析P353 · 目视转录
对 {8,9,10,4,5,6,20,1,2} 采用冒泡排序,从后往前依次进行、要求升序,需交换元素的趟数至少为( ),不考虑无交换的最后一趟。
A. 3
B. 4
C. 5
D. 8
查看答案与解析
答案:C。
| 趟数 | 结果 |
|---|---|
| 1 | 1,8,9,10,4,5,6,20,2 |
| 2 | 1,2,8,9,10,4,5,6,20 |
| 3 | 1,2,4,8,9,10,5,6,20 |
| 4 | 1,2,4,5,8,9,10,6,20 |
| 5 | 1,2,4,5,6,8,9,10,20 |
第五趟已全局有序。实际可在交换后判断是否还产生新逆序对,若不会产生则本趟后即全局有序,最少 5 趟。
单项选择题 09
原书题目P351 · 解析P354 · 目视转录
双向冒泡交替正反扫描,第一趟把最大值放最右,第二趟把最小值放最左,再缩小范围继续。对 {4,7,8,3,5,6,10,9,1,2} 排序,共需( )趟(第一趟左往右开始,从左往右或从右往左都称一趟)。
A. 7
B. 6
C. 8
D. 9
查看答案与解析
答案:B。
| 趟数 | 方向 | 序列 |
|---|---|---|
| 1 | 左→右 | 4,7,3,5,6,8,9,1,2,10 |
| 2 | 右→左 | 1,4,7,3,5,6,8,9,2,10 |
| 3 | 左→右 | 1,4,3,5,6,7,8,2,9,10 |
| 4 | 右→左 | 1,2,4,3,5,6,7,8,9,10 |
| 5 | 左→右 | 1,2,3,4,5,6,7,8,9,10 |
第五趟后有序,但需再进行一趟无交换的排序才能确认,故共 6 趟。
单项选择题 10
原书题目P351 · 解析P354 · 目视转录
下列序列用快速排序,每次基准均选子序列首元素。速度最快的是( ),最慢的是( )。
A. {21,25,5,17,9,23,30}
B. {25,23,30,17,21,5,9}
C. {21,9,17,30,25,23,5}
D. {5,9,17,21,23,25,30}
查看答案与解析
答案:A、D。
每次枢轴均把表分为长度相近的两子表时最快,表已有序或逆序时最慢。D 已有序。A 首趟枢轴 21 划为 {9,17,5} 和 {25,23,30},后续仍均分,是最优情况。
单项选择题 11
原书题目P351 · 解析P354 · 目视转录
以首关键字为基准,对下列序列做快速排序,第一趟移动记录次数最多的是( )。
A. 92,96,88,42,30,35,110,100
B. 92,96,100,110,42,35,30,88
C. 100,96,92,35,30,110,88,42
D. 42,30,35,92,100,96,88,110
查看答案与解析
答案:B。
逐项执行一趟。以 A 为例,35 移到第 1 位、96 移到第 6 位、30 移到第 2 位,再将枢轴移到原 30 单元,即第 5 位,共 4 次。同理 B 为 8 次,C 为 4 次,D 为 2 次。
单项选择题 12
原书题目P351 · 解析P354 · 目视转录
下列序列中,( )可能是第一趟快速排序后的结果(分别讨论从大到小、从小到大)。
Ⅰ.{68,11,18,69,23,93,73}
Ⅱ.{68,11,69,23,18,93,73}
Ⅲ.{93,73,68,11,69,23,18}
Ⅳ.{68,11,69,23,18,73,93}
A. Ⅰ、Ⅳ
B. Ⅱ、Ⅲ
C. Ⅲ、Ⅳ
D. 只有Ⅳ
查看答案与解析
答案:C。
升序最终为 11,18,23,68,69,73,93;降序最终为 93,73,69,68,23,18,11。Ⅰ、Ⅱ中没有处于最终位置的元素,不可能。Ⅲ中 93、73 处于降序最终位置,73 两侧分别大于、小于它,可能;Ⅳ中 73、93 处于升序最终位置,73 也把序列划成小于与大于它的两部分,可能。
单项选择题 13
原书题目P351 · 解析P354 · 目视转录
对 n 个关键字快速排序,最大递归深度为( ),最小递归深度为( )。
A. 1
B. n
C. log₂n
D. nlog₂n
查看答案与解析
答案:B、C。
递归深度为递归树高度。每次等分时高度为 log₂n;每次枢轴均是最大或最小值时,递归树退化为单链,高度 n。
单项选择题 14
原书题目P352 · 解析P354 · 目视转录
对 8 个元素快速排序,最好情况下关键字比较次数是( )。
A. 7
B. 8
C. 12
D. 13
查看答案与解析
答案:D。
最好每次划分长度接近。首趟比较 7 次,划为长度 3、4 两子表;第二趟分别比较 2、3 次;第三趟长度 2 子表比较 1 次。总共 7+2+3+1=13 次。
单项选择题 15
原书题目P352 · 解析P354 · 目视转录
【2010 统考真题】递归快速排序的下列叙述中,正确的是( )。
A. 递归次数与初始排列无关
B. 每次划分后先处理较长分区可减少递归次数
C. 每次划分后先处理较短分区可减少递归次数
D. 递归次数与每次划分后分区的处理顺序无关
查看答案与解析
答案:D。
递归次数与初始排列有关,划分较平衡时少,不平衡时多;与分区处理先后顺序无关。
单项选择题 16
原书题目P352 · 解析P354 · 目视转录
【2011 统考真题】为实现快速排序,待排序序列宜采用( )。
A. 顺序存储
B. 散列存储
C. 链式存储
D. 索引存储
查看答案与解析
答案:A。
大部分内部排序适用于顺序存储。快速排序既从后往前查找,也从前往后查找,宜用顺序存储。
单项选择题 17
原书题目P352 · 解析P354 · 目视转录
【2014 统考真题】下列不可能是快速排序第二趟结果的是( )。
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
查看答案与解析
答案:C。
首趟确定一个枢轴。若枢轴在首端或尾端,第二趟对余下 n−1 个元素划分,再确定一个,因此至少两个最终位置,其中至少一个在端点;若首趟枢轴不在端点,第二趟对两个子序列分别划分,至少确定三个最终位置。
A 中 2、3、6、7、9 符合前述情况;B 中 2、9 符合第一种;D 中 5、9 符合第一种;C 只有 9 就位,故不可能。
单项选择题 18
原书题目P352 · 解析P355 · 目视转录
【2019 统考真题】对尚未确定最终位置的所有元素进行一遍处理称一趟。下列不可能为快速排序第二趟结果的是( )。
A. 5,2,16,12,28,60,32,72
B. 2,16,5,28,12,60,32,72
C. 2,12,16,5,28,32,72,60
D. 5,2,12,28,16,32,72,60
查看答案与解析
答案:D。
依据上题结论,A 的 28、72 符合第一种情况,B 的 2、72 符合第一种,C 的 2、28、32 符合第一或第二种。D 只有 12、32 就位,且均不在端点,既不符合第一种,也不符合第二种。
单项选择题 19
原书题目P352 · 解析P355 · 目视转录
【2023 统考真题】快速排序某次划分后序列为 68,11,70,23,80,77,48,81,93,88,则本次划分枢轴是( )。
A. 11
B. 70
C. 80
D. 81
查看答案与解析
答案:D。
最终升序为 11,23,48,68,70,77,80,81,88,93,与当前序列相同位置的只有 77、81,选项中只有 81。且 77 左边有比它大的 80,不可能为枢轴;81 左边均小于它、右边均大于它,因此为 81。
单项选择题 20
原书题目P352 · 解析P355 · 目视转录
【2024 统考真题】对含 n(n>3)个元素的数组 M 快速排序,第一趟将除枢轴外的 n−1 个元素划为均非空的 P、Q 两块,则正确的是( )。
A. P 与 Q 块间有序
B. P 与 Q 块内有序
C. P、Q 元素个数大致相等
D. P、Q 中均不存在相等元素
查看答案与解析
答案:A。
首趟划为小于枢轴的 P、枢轴、大于枢轴的 Q。两块内部无序,但 P 内元素≤枢轴,Q 内元素≥枢轴,所以 P≤Q,块间有序。
综合应用题
综合应用题 01
原书题目P352 · 解析P355 · 目视转录
线性表按顺序存储,元素为各不相同的整数。设计把所有奇数移到所有偶数前面的算法,要求时间最短、辅助空间最小。
查看答案与解析
整理注记
若输入允许负整数,奇数判断应写为x%2!=0。C/C++中负奇数的余数可能为-1,使用x%2==1会漏判。
借用快速排序划分思想,只遍历一次,时间 ,空间 。从前找偶数、从后找奇数并交换,重复直至两指针相遇。
void move(ElemType A[], int len) {
int i = 0, j = len - 1;
while (i < j) {
while (i < j && A[i] % 2 != 0) i++;
while (i < j && A[j] % 2 != 1) j--;
if (i < j) {
Swap(A[i], A[j]);
i++;
j--;
}
}
}
转录核对:原书后向扫描用
A[j]%2!=1判断“不是奇数”。对 C/C++ 中可能为负的整数,应改为A[j]%2==0,与前向扫描的奇偶定义保持一致。
综合应用题 02
原书题目P352 · 解析P355 · 目视转录
编写算法,在数组 L[1..n] 中找出第 k 小的元素(从小到大排序后第 k 个位置的元素)。
查看答案与解析
直接排序再取 L[k],平均时间至少 ;也可用小顶堆,建堆后取 k 次,时间 。更精巧的方法基于快速排序划分:选择 pivot,将表划为 L[1..m−1]、pivot、L[m+1..n];m=k 时直接返回;m<k 时在右表找第 k−m 小;m>k 时在左表找第 k 小。
平均时间可达 ,空间取决于划分及递归实现。原书代码中 k 始终是原数组的目标下标。
int kth_elem(int a[], int low, int high, int k) {
int pivot = a[low];
int low_temp = low, high_temp = high;
while (low < high) {
while (low < high && a[high] >= pivot) --high;
a[low] = a[high];
while (low < high && a[low] <= pivot) ++low;
a[high] = a[low];
}
a[low] = pivot;
if (low == k)
return a[low];
else if (low > k)
return kth_elem(a, low_temp, low - 1, k);
else
return kth_elem(a, low + 1, high_temp, k);
}
综合应用题 03
原书题目P352 · 解析P356 · 目视转录
荷兰国旗问题:顺序表中仅有红、白、蓝三种颜色的条块,请编写时间复杂度为 的算法,使其按红、白、蓝排列。完成如下算法。
typedef enum {RED, WHITE, BLUE} color;
void Flag_Arrange(color a[], int n) { /* ... */ }
查看答案与解析
顺序扫描,把红块换到最前,蓝块换到最后。设 i、j、k,j 为当前扫描位置,i 前全部红色,k 后全部蓝色。根据 a[j] 颜色决定是否交换到前、后部。初始 i=0、k=n−1。
typedef enum {RED, WHITE, BLUE} color;
void Flag_Arrange(color a[], int n) {
int i = 0, j = 0, k = n - 1;
while (j <= k) {
switch (a[j]) {
case RED:
Swap(a[i], a[j]);
i++;
j++;
break;
case WHITE:
j++;
break;
case BLUE:
Swap(a[j], a[k]);
k--;
// 不做 j++,因为交换过来的元素仍可能是蓝色
}
}
}
把正数、负数、零排成负数在前、零在中、正数在后,也可采用同样方法。思考:为什么 RED 分支不用考虑交换后 a[j] 仍为红色,BLUE 分支却要重新判断?
综合应用题 04
原书题目P352 · 解析P357 · 目视转录
【2016 统考真题】正整数集合 ,n≥2,划为不相交子集 A₁、A₂,元素个数为 n₁、n₂,元素和为 S₁、S₂。设计尽可能高效的划分,使 |n₁−n₂| 最小且 |S₁−S₂| 最大。
- 给出基本设计思想。
- 用 C 或 C++ 描述算法,关键处注释。
- 说明平均时间和空间复杂度。
查看答案与解析
- 将最小的 ⌊n/2⌋ 个元素放 A₁,其余放 A₂,可同时满足要求。仿照快速排序按枢轴划分,若枢轴位置 i 等于目标中间秩则结束;i 较小时只继续划分右侧,i 较大时只继续划分左侧。无需全部排序,平均时间 ,空间 。
- 实现如下,k=n/2,数组从 0 开始,因此目标枢轴下标为 k−1。
int setPartition(int a[], int n) {
int pivotkey, low = 0, low0 = 0, high = n - 1,
high0 = n - 1, flag = 1, k = n / 2, i;
int s1 = 0, s2 = 0;
while (flag) {
pivotkey = a[low];
while (low < high) {
while (low < high && a[high] >= pivotkey) --high;
if (low != high) a[low] = a[high];
while (low < high && a[low] <= pivotkey) ++low;
if (low != high) a[high] = a[low];
}
a[low] = pivotkey;
if (low == k - 1)
flag = 0;
else {
if (low < k - 1) {
low0 = ++low;
high = high0;
}
else {
high0 = --high;
low = low0;
}
}
}
for (i = 0; i < k; i++) s1 += a[i];
for (i = k; i < n; i++) s2 += a[i];
return s2 - s1;
}
- 平均时间复杂度 ,空间复杂度 。