数据结构之交换排序题解

选择题

01. 对 n 个不同的元素利用冒泡法从小到大排序，在()情况下元素交换的次数最多

选项：
- A. 从大到小排列好的
- B. 从小到大排列好的
- C. 元素无序
- D. 元素基本有序
答案： A
解释： 通常情况下，冒泡排序最少进行 1 次冒泡，最多进行 n-1 次冒泡。初始序列为逆序时，需要进行 n-1 次冒泡，并且需要交换的次数最多。初始序列为正序时，仅进行 1 次冒泡（无交换）就可以终止算法。

02. 若用冒泡排序算法对序列 {10, 14, 26, 29, 41, 52} 从大到小排序，则需进行( )次比较

选项：
- A. 3
- B. 10
- C. 15
- D. 25
答案： C
解释： 冒泡排序在调整“逆序”时，比较次数为排列中逆序的个数。对逆序序列进行冒泡排序，每个元素向后调整时都需要进行比较，因此共需要比较 $5 + 4 + 3 + 2 + 1 = 15$ 次。

03. 用某种排序方法对线性表 {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. 2路归并排序
- D. 快速排序
答案： D
解释： 快速排序每趟都将基准元素放在其最终位置，然后以它为基准将序列划分为两个子序列。观察题中的排序过程可知，经过多次划分后，序列逐渐有序，因此为快速排序。

04. 一组记录的关键码为 (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 小的元素，并与之进行交换，而后从前向后扫描比 46 大的元素并将 46 与该元素交换，最终得到 (40, 46, 56, 38, 79, 84)。继续重复扫描操作，最终得到划分结果为 (40, 38, 46, 56, 79, 84)。

05. 快速排序算法在( )情况下最不利于发挥其长处。

选项：
- A. 要排序的数据量太大
- B. 要排序的数据中含有多个相同值
- C. 要排序的数据个数为奇数
- D. 要排序的数据已基本有序
答案： D
解释： 当待排序数据为基本有序时，每次选取第 n 个元素为基准，会导致划分区间分配不均匀，不利于发挥快速排序算法的优势。相反，当待排序数据分布较为随机时，基准元素能将序列划分为两个长度大致相等的序列，这时才能发挥快速排序的优势。

06. 就平均性能而言，目前最好的内部排序方法是()。

A. 冒泡排序
B. 直接插入排序
C. 希尔排序
D. 快速排序

答案: D
解释: 快速排序在平均性能上通常被认为是最优的内部排序算法，具有 $O(n \log n)$ 的时间复杂度。虽然希尔排序的时间复杂度也有改进，但快速排序的常数因子最小，因此性能较好。

07. 数据序列 F={2,1,4,9,8,10,6,20} 只能是下列排序算法中的( )两趟排序后的结果。

A. 快速排序
B. 冒泡排序
C. 选择排序
D. 插入排序

答案: A
解释: 在快速排序中，经过两趟排序后，某些元素会被移动到最终位置。根据给定的序列，只有快速排序的特性符合题意，其他排序算法在两趟后不会达到如此状态。

08. 对数据序列 {8,9,10,4,5,6,20,1,2} 采用冒泡排序（从后向前次序进行，要求升序），需进行的趟数至少是()。

A. 3
B. 4
C. 5
D. 8

答案: C
解释: 从后向前进行冒泡排序时，经过五趟排序后，序列已经全局有序，因此最少需要 5 趟。

09. 对下列关键字序列用快排进行排序时，速度最快的情形是( )，速度最慢的情形是( )。

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，而后对两个子表划分时，枢轴值再次将它们等分，所以该序列是快速排序最优的情况，速度最快。其他选项可以类似分析。

10. 对下列 4 个序列，以第一个关键字为基准用快速排序算法进行排序，在第一趟过程中移动记录次数最多的是()。

A. {92,96,88,42,30,35,110,100}
B. {92,96,100,110,42,35,30,88}
C. {42,30,35,92,100,96,88,110}
D. {100,96,92,35,30,110,88,42}

答案: B
解释: 在选项 B 中，枢轴值 92 会导致多个元素的移动，记录次数最多。其他选项的移动次数较少，因此 B 是移动记录次数最多的序列。

问题 11

问题: 下列序列中，()可能是执行第一趟快速排序后所得到的序列。

选项:

A. I、IV
B. I、II
C. III、IV
D. 只有 IV

答案: C. III、IV

解释:

显然，若按从小到大排序，则最终有序的序列是${11,18,23,68,69,73,93}$:若按从大到小排序，则最终有序的序列是${93,73,69,68,23,18,11}$。对比可知 I、II中没有处于最终位置的元素，故 I、II都不可能。I 中73 和 93 处于从大到小排序后的最终位置，而且 73 将序列分割成大于73 和小于 73 的两部分，故III是有可能的。IV中73 和 93 处于从小到大排列后的最终位置，73也将序列分割成大于 73 和小于 73 的两部分。

问题 12

问题: 对 n 个关键字进行快速排序，最大递归深度为()，最小递归深度为( )。

选项:

A. 1
B. n
C. log₂n
D. nlog₂n

答案: 最大递归深度为 B. n，最小递归深度为 C. log₂n。

解释:

当每次选择的枢轴是最小或最大值时，快速排序的递归深度会退化为 n（即形成链表）。
当每次选择的枢轴将数组等分时，递归深度为 log₂n。

问题 13

问题: 对一组数据 (2, 12, 16, 88, 5, 10) 进行排序，若前 3 趟排序结果如下:

第一趟排序结果: {2, 12, 16, 5, 10, 88}
第二趟排序结果: {2, 12, 5, 10, 16, 88}
第三趟排序结果: {2, 5, 10, 12, 16, 88}

则采用的排序方法可能是()。

选项:

A. 冒泡排序
B. 希尔排序
C. 归并排序
D. 基数排序

答案: A. 冒泡排序

解释:

在冒泡排序中，每一趟都会将最大的数移动到未排序部分的最后位置。
第一趟中，88 是最大值被放到最后。
第二趟和第三趟的变化符合冒泡排序的特征。

问题 14

问题: 采用递归方式对顺序表进行快速排序。下列关于递归次数的叙述中，正确的是()。

选项:

A. 递归次数与初始数据的排列次序无关
B. 每次划分后，先处理较长的分区可以减少递归次数
C. 每次划分后，先处理较短的分区可以减少递归次数
D. 递归次数与每次划分后得到的分区的处理顺序无关

答案: D. 递归次数与每次划分后得到的分区的处理顺序无关。

解释:

递归次数主要取决于如何选择枢轴和数据的初始排列。
处理较长或较短的分区并不会影响递归的深度，但选择的枢轴会影响分区的平衡程度，从而影响递归次数的多寡。

问题 15

问题: 为实现快速排序算法，待排序序列宜采用的存储方式是()。

选项:

A. 顺序存储
B. 散列存储
C. 链式存储
D. 索引存储

答案: A. 顺序存储

解释:

快速排序算法需要频繁地访问数组的不同部分，顺序存储（即数组）使得访问任意元素的时间复杂度为 O(1)，非常适合快速排序。
链式存储（链表）虽然能动态管理内存，但由于在排序过程中需要频繁地查找和交换节点，效率会大大降低。
散列存储和索引存储不适合快速排序，因为它们的访问方式和排序需求不符。

问题 16

问题: 下列选项中，不可能是快速排序第 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}

答案: C. {3, 2, 5, 4, 7, 6, 9}

解释:

快排的阶段性排序结果的特点是，第i趟完成时，会有i个以上的数出现在它最终将要出现的位置，即它左边的数都比它小，它右边的数都比它大。题目问第二趟排序的结果，即要找不存在两个这样的数的选项。A选项中2,3,6,7,9均符合，所以A排除;B选项中，2,9均符合，所以B排除:D选项中5.9均符合，所以D排除:最后看C选项，只有9一个数符合，所以C不可能是快速排序第二趟的结果。

问题 17

问题: 下列序列中，不可能是快速排序第二趟结果的是()。

选项:

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. {5, 2, 12, 28, 16, 32, 72, 60}

第一趟是以32为基准元素，第二趟的话60，72应该有序，因此无法解释。

程序题

01. 能否用队列来实现这个栈? 为什么?

问题: 在使用非递归方法实现快速排序时，通常要利用一个栈记忆待排序区间的两个端点。能否用队列来实现这个栈? 为什么?

答案: 可以用队列来代替栈。虽然栈是后进先出（LIFO），而队列是先进先出（FIFO），但在快速排序中，栈的主要作用是存储待处理子区间的上下界。使用队列时，可以先将待处理子区间的边界入队，在处理完一个子区间后，再从队列中取出下一个子区间进行处理。虽然处理顺序不同，但其功能仍然是可行的。

02. 编写双向冒泡排序算法

问题: 编写双向冒泡排序算法，在正反两个方向交替进行扫描，即第一趟把关键字最大的元素放在序列的最后面，第二趟把关键字最小的元素放在序列的最前面，如此反复进行。

答案: 以下是双向冒泡排序的代码实现：

void BubbleSort(ElemType A[], int n) {
    int low = 0, high = n - 1;
    bool flag = true; // 标志位，指示是否发生交换

    while (low < high && flag) {
        flag = false; // 每趟初始置 flag 为 false

        // 从前向后起泡
        for (int i = low; i < high; i++) {
            if (A[i] > A[i + 1]) {
                // 发生逆序，交换元素
                swap(A[i], A[i + 1]);
                flag = true; // 设置标志为 true，表示发生了交换
            }
        }
        high--; // 每趟结束后，更新上界

        // 从后向前起泡
        for (int i = high; i > low; i--) {
            if (A[i] < A[i - 1]) {
                // 发生逆序，交换元素
                swap(A[i], A[i - 1]);
                flag = true; // 设置标志为 true，表示发生了交换
            }
        }
        low++; // 每趟结束后，更新下界
    }
}

03. 设计把所有奇数移动到所有偶数前边的算法

问题: 已知线性表按顺序存储，且每个元素都是不相同的整数型元素，设计把所有奇数移动到所有偶数前边的算法(要求时间最少，辅助空间最少)。

答案: 可以采用基于快速排序的划分思想，只需遍历一次即可实现将奇数和偶数分开。以下是算法的实现：

void move(ElemType A[], int len) {
    int i = 0, j = len - 1; // i 指向从前向后查找，j 指向从后向前查找
    while (i < j) {
        // 从前向后找到一个偶数元素
        while (i < j && A[i] % 2 != 0) i++;
        // 从后向前找到一个奇数元素
        while (i < j && A[j] % 2 == 0) j--;
        // 如果 i < j，交换这两个元素
        if (i < j) {
            swap(A[i], A[j]);
            i++; // 移动指针
            j--; // 移动指针
        }
    }
}

04. 快速排序的随机划分算法

问题: 重新编写快速排序的划分算法，使其随机选择枢轴值，并根据该值对数组进行划分。

答案: 以下是实现随机选择枢轴的快速排序划分算法的代码：

#include <cstdlib> // for rand() and srand()
#include <ctime>   // for time()

int PartitionRandom(ElemType A[], int low, int high) {
    // 随机选择一个枢轴
    int randIndex = low + rand() % (high - low + 1);
    // 将枢轴值交换到第一个元素
    swap(A[randIndex], A[low]);
    
    ElemType pivot = A[low]; // 设置当前的枢轴值
    int i = low; // 初始化 i

    // 遍历并重新划分数组
    for (int j = low + 1; j <= high; j++) {
        if (A[j] < pivot) { // 如果当前元素小于枢轴值
            swap(A[++i], A[j]); // 交换元素到前面
        }
    }
    // 将枢轴元素放到正确位置
    swap(A[i], A[low]);
    return i; // 返回枢轴位置
}

05. 查找第 k 小的元素

问题: 编写一个算法，在数组 A[1..n] 中找出第 k 小的元素。

答案: 下面是基于快速排序划分操作的算法实现：

int kthElement(ElemType A[], int low, int high, int k) {
    if (low == high) {
        return A[low]; // 只有一个元素
    }

    int pivotIndex = PartitionRandom(A, low, high); // 获取划分后的枢轴位置
    int m = pivotIndex - low + 1; // 计算 pivot 的位置

    if (m == k) {
        return A[pivotIndex]; // 找到第 k 小的元素
    } else if (m < k) {
        return kthElement(A, pivotIndex + 1, high, k - m); // 在右侧子数组中查找
    } else {
        return kthElement(A, low, pivotIndex - 1, k); // 在左侧子数组中查找
    }
}

06. 荷兰国旗问题

问题: 设有一个仅由红、白、蓝三种颜色的条块组成的序列，请编写一个时间复杂度为 O(n) 的算法，使得这些条块按红、白、蓝的顺序排好。

答案: 下面是解决荷兰国旗问题的算法实现：

typedef enum { RED, WHITE, BLUE } Color; // 定义颜色类型

void flagArrange(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--;
                break;
        }
    }
}

07.【2016统考真题】

已知由 $ n $ ( $ n > 2 $ ) 个正整数构成的集合 $ A = {a_0, a_1, , a_{n-1}} $，将其划分为两个不相交的子集 $ A_1 $ 和 $ A_2 $，元素个数分别是 $ n/2 $ 和 $ n/2 $，并且尽量使得两个子集的元素和 $ S_1 $ 和 $ S_2 $ 之间的差 $ |S_1 - S_2| $ 最小。设计一个尽可能高效的划分算法，满足上述要求。

解答

1) 算法的基本设计思想

我们可以使用快速选择算法（Quickselect）来找到第 $ n/2 $ 小的元素，进而实现集合的划分。算法步骤如下：

选择一个枢轴（pivot）元素，并根据该枢轴将数组划分成两个部分。
根据枢轴的位置判断是否已找到所需的 $ n/2 $ 小元素。
- 如果枢轴位置为 $ n/2 $，则完成划分。
- 如果枢轴位置小于 $ n/2 $，则继续在右半部分查找。
- 如果枢轴位置大于 $ n/2 $，则继续在左半部分查找。
计算两个子集的和 $ S_1 $ 和 $ S_2 $。

该算法的效率在于它只需在每次划分后查找一部分元素，因此可以在平均 $ O(n) $ 时间内完成。

2) 算法实现

下面是该算法的 C++ 实现，关键部分附有注释：

#include <iostream>
#include <vector>
#include <cstdlib> // For rand()

using namespace std;

// 快速选择算法的划分函数
int partition(vector<int>& A, int low, int high, int pivotIndex) {
    int pivotValue = A[pivotIndex];
    // 将枢轴值移动到最后
    swap(A[pivotIndex], A[high]);
    int storeIndex = low;
    
    for (int i = low; i < high; i++) {
        // 如果当前元素小于枢轴值
        if (A[i] < pivotValue) {
            swap(A[storeIndex], A[i]);
            storeIndex++;
        }
    }
    // 将枢轴值放回其最终位置
    swap(A[storeIndex], A[high]);
    return storeIndex; // 返回枢轴的新索引
}

// 快速选择算法
int quickSelect(vector<int>& A, int low, int high, int k) {
    if (low == high) return A[low]; // 只有一个元素

    // 随机选择枢轴
    int pivotIndex = low + rand() % (high - low + 1);
    pivotIndex = partition(A, low, high, pivotIndex);
    
    // 根据枢轴的位置决定下一步
    if (k == pivotIndex) {
        return A[k];
    } else if (k < pivotIndex) {
        return quickSelect(A, low, pivotIndex - 1, k);
    } else {
        return quickSelect(A, pivotIndex + 1, high, k);
    }
}

// 主函数
pair<vector<int>, vector<int>> setPartition(vector<int>& A) {
    int n = A.size();
    int k = n / 2; // 要划分的元素个数

    // 找到第 k 小的元素
    int pivotValue = quickSelect(A, 0, n - 1, k - 1);

    // 将小于和大于等于枢轴值的元素划分到两个集合
    vector<int> A1, A2;
    for (int num : A) {
        if (num < pivotValue) {
            A1.push_back(num);
        } else {
            A2.push_back(num);
        }
    }
    // 如果 A1 还少于 k 个元素，需添加 pivots
    while (A1.size() < k && !A2.empty()) {
        A1.push_back(A2.back());
        A2.pop_back();
    }
    // 返回两个集合
    return {A1, A2};
}

// 测试函数
int main() {
    vector<int> A = {3, 1, 4, 1, 5, 9, 2, 6, 5};
    auto [A1, A2] = setPartition(A);
    
    cout << "A1: ";
    for (int num : A1) cout << num << " ";
    cout << "\nA2: ";
    for (int num : A2) cout << num << " ";
    cout << endl;

    return 0;
}