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} 排序,变化如下。

  1. 25,84,21,47,15,27,68,35,20
  2. 20,15,21,25,47,27,68,35,84
  3. 15,20,21,25,35,27,47,68,84
  4. 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 平均达到 O(n2)O(n^2);希尔虽降低直接插入的复杂度,平均性能仍不如快速排序。多种算法平均时间均为 O(nlog⁡2n)O(n\log_2n),而快速排序的常数因子较小。

单项选择题 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。

趟数结果
11,8,9,10,4,5,6,20,2
21,2,8,9,10,4,5,6,20
31,2,4,8,9,10,5,6,20
41,2,4,5,8,9,10,6,20
51,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会漏判。

借用快速排序划分思想,只遍历一次,时间 O(n)O(n),空间 O(1)O(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],平均时间至少 O(nlog⁡2n)O(n\log_2n);也可用小顶堆,建堆后取 k 次,时间 O(n+klog⁡2n)O(n+k\log_2n)。更精巧的方法基于快速排序划分:选择 pivot,将表划为 L[1..m−1]、pivot、L[m+1..n];m=k 时直接返回;m<k 时在右表找第 k−m 小;m>k 时在左表找第 k 小。

平均时间可达 O(n)O(n),空间取决于划分及递归实现。原书代码中 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 · 目视转录

荷兰国旗问题:顺序表中仅有红、白、蓝三种颜色的条块,请编写时间复杂度为 O(n)O(n) 的算法,使其按红、白、蓝排列。完成如下算法。

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 统考真题】正整数集合 A={ak∣0≤k<n}A=\{a_k\mid0\le k<n\},n≥2,划为不相交子集 A₁、A₂,元素个数为 n₁、n₂,元素和为 S₁、S₂。设计尽可能高效的划分,使 |n₁−n₂| 最小且 |S₁−S₂| 最大。

  1. 给出基本设计思想。
  2. 用 C 或 C++ 描述算法,关键处注释。
  3. 说明平均时间和空间复杂度。
查看答案与解析
  1. 将最小的 ⌊n/2⌋ 个元素放 A₁,其余放 A₂,可同时满足要求。仿照快速排序按枢轴划分,若枢轴位置 i 等于目标中间秩则结束;i 较小时只继续划分右侧,i 较大时只继续划分左侧。无需全部排序,平均时间 O(n)O(n),空间 O(1)O(1)。
  2. 实现如下,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;
}
  1. 平均时间复杂度 O(n)O(n),空间复杂度 O(1)O(1)。