数据结构之内部排序习题

选择题

01. 若要求排序是稳定的，且关键字为实数，则在下列排序方法中应选：

A. 直接插入排序
B. 选择排序
C. 基数排序
D. 快速排序

答案: A

解析: 稳定排序是指在排序后两个相等的元素其相对次序保持不变。基数排序不适用于实数，而选择排序和快速排序都不是稳定的，只有直接插入排序是稳定的，并且可以处理实数。

02. 以下排序方法中时间复杂度为 \(O(n \log n)\) 且稳定的是：

A. 堆排序
B. 快速排序
C. 归并排序
D. 直接插入排序

答案: C

解析: 堆排序和快速排序不是稳定的，而直接插入排序的时间复杂度是 \(O(n^2)\)。归并排序的时间复杂度是 \(O(n \log n)\) 且是稳定的。

03. 设被排序的结点序列共有 \(N\) 个结点，在该序列中的结点已十分接近有序的情况下，用直接插入排序、归并排序和快速排序对其进行排序，这些算法的时间复杂度应为：

A. \(O(N)\), \(O(N \log N)\), \(O(N \log N)\)
B. \(O(N)\), \(O(N \log N)\), \(O(N)\)
C. \(O(N)\), \(O(N \log N)\), \(O(N^2)\)
D. \(O(N)\), \(O(N \log N)\), \(O(N \log N)\)

答案: C

解析: 在接近有序的情况下，直接插入排序的时间复杂度为 \(O(N)\)，归并排序无论如何都保持 \(O(N \log N)\)，而快速排序在最好的情况下也可以达到 \(O(N^2)\)。

04. 下列排序算法中属于稳定排序的是 (①)，平均时间复杂度为 \(O(n \log n)\) 的是 (②)，在最好的情况下，时间复杂度可以达到线性时间的有 (③)：

I.冒泡排序
II. 堆排序
III. 选择排序
IV. 直接插入排序
V. 希尔排序
VI. 归并排序
VII. 快速排序

A. ①I、IV、VI ②I、VI、VII ③I、IV
B. ①I、III、V ②I、VI、VII ③I、V
C. ①I、IV、VI ②VI、VII ③IV、VII
D. ①II、III、IV ②V、VI、VII ③I、III

答案: A

解析:

  • 稳定排序：冒泡排序、直接插入排序、归并排序。
  • 平均时间复杂度为 \(O(n \log n)\) 的有冒泡排序、归并排序、快速排序。
  • 最好情况下可以达到线性时间的是冒泡排序和直接插入排序。

05. 就排序算法所用的辅助空间而言，堆排序、快速排序和归并排序的关系是：

A. 堆排序 < 快速排序 < 归并排序
B. 堆排序 < 归并排序 < 快速排序
C. 堆排序 > 归并排序 > 快速排序
D. 堆排序 > 快速排序 > 归并排序

答案: A

解析:

  • 堆排序的空间复杂度为 \(O(1)\)（只需常量空间）。
  • 快速排序的空间复杂度在最坏情况下为 \(O(n)\)，平均情况下为 \(O(\log n)\)（主要是递归栈空间）。
  • 归并排序的空间复杂度为 \(O(n)\)（需要额外的存储空间来合并）。 因此，堆排序 < 快速排序 < 归并排序 是正确的选项。

06. 排序趟数与序列的原始状态无关的排序方法是：

I.直接插入排序
II. 简单选择排序
III. 冒泡排序
IV. 基数排序

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

答案: A

解析:

交换类的排序，其趟数和原始序列状态有关，故冒泡排序与初始序列有关。直接插入排序:每趟排序都插入一个元素，所以排序趟数固定为n-1:简单选择排序:每趟排序都选出一个最小

(或最大)的元素，所以排序趟数固定为n-1:基数排序:每趟排序都要进行“分配”和“收集”排序趟数固定为 d。

07. 若序列的原始状态为 {1, 2, 3, 4, 5, 10, 6, 7, 8, 9}，要想使得排序过程中的元素比较次数最少，则应该采用的方法是：

A. 插入排序
B. 选择排序
C. 希尔排序
D. 冒泡排序

答案: A

解析:

  • 在基本有序的序列中，直接插入排序的比较次数较少，因为它每次只需将新元素插入到正确的位置。
  • 插入排序在这种情况下只需进行 \(n + 4\) 次比较，而希尔排序和冒泡排序的比较次数较多。因此，选择插入排序是最佳选择。

08. 一般情况下，以下查找效率最低的数据结构是：

A. 有序顺序表
B. 二叉排序树
C. 堆
D. 平衡二叉树

答案: C

解析:

  • 堆用于优先队列的实现，查找操作的效率较低，因为它不是有序的。在查找时，堆需要遍历所有元素，效率低于有序顺序表和二叉排序树，后者可以利用其结构特性实现更高效的查找。
  • 平衡二叉树能够保证对数时间复杂度的查找效率。因此，选择堆作为查找效率最低的数据结构是正确的。

09. 排序趟数与序列的原始状态有关的排序方法是：

A. 插入排序
B. 选择排序
C. 冒泡排序
D. 基数排序

答案: C

解析:

  • 插入排序和选择排序的排序趟数始终为 \(n - 1\)，与序列的初始状态无关。
  • 冒泡排序的趟数与初始序列的状态有关。如果序列基本有序，某趟比较后没有发生元素交换，则说明已排好序，因此需要的趟数会减少。
  • 基数排序的趟数与关键字的位数有关，因此也不受初始状态影响。

综上所述，只有冒泡排序的趟数与初始状态有关。

10. 在内部排序过程中，对尚未确定最终位置的所有元素进行一遍处理称为一趟排序。下列排序方法中，每趟排序结束都至少能够确定一个元素最终位置的方法是：

I.简单选择排序
II. 希尔排序
III. 快速排序
IV. 堆排序
V. 2路归并排序

A. 仅 I、III、IV
B. 仅 I、III、V
C. 仅 II、IV
D. 仅 III、IV、V

答案: A

解析:

  • 简单选择排序每次选择未排序序列中的最小元素放入其最终位置。
  • 快速排序每趟排序结束后都将枢轴元素放到最终位置。
  • 堆排序通过调整堆的结构，每次将根节点与最后一个元素交换，确定根节点的最终位置。
  • 希尔排序和2路归并排序每趟处理的结果可能会局部有序，但不能确定单个元素的最终位置，因此不符合题意。

因此，选项 A 是正确的。

11. 下列排序算法中，元素的移动次数与关键字的初始排列次序无关的是：

A. 直接插入排序
B. 冒泡排序
C. 基数排序
D. 快速排序

答案: C

解析:

  • 直接插入排序的元素移动次数与初始排列次序密切相关。若序列接近有序，则移动次数会减少。
  • 冒泡排序的移动次数同样与初始状态有关，若初始序列基本有序，则移动次数会减少。
  • 基数排序的元素移动次数与初始排列次序无关，因为它通过位数进行分配，独立于元素的初始顺序。
  • 快速排序的移动次数也与初始排列次序有关，具体取决于划分的效果。

综上所述，选项 C 是正确的。

12.【2017 统考真题】下列排序方法中，若将顺序存储更换为链式存储，则算法的时间效率会降低的是：

I. 插入排序
II. 选择排序
III. 冒泡排序
IV. 希尔排序
V. 堆排序

A. 仅 I、II
B. 仅 II、III
C. 仅 I、IV
D. 仅 IV、V

答案: D

解析:

  • 插入排序、选择排序、冒泡排序的时间复杂度为 \(O(n^2)\)，在链式存储下仍为 \(O(n^2)\)。
  • 希尔排序和堆排序依赖顺序存储的随机访问特性，若改为链式存储，无法实现有效的随机访问，导致时间复杂度增加。因此，时间效率会降低。
  • 综上所述，选择 D 作为答案。

13.【2019 统考真题】选择一个排序算法时，除算法的时空效率外，下列因素中，还需要考虑的是：

I. 数据的规模
II. 数据的存储方式
III. 算法的稳定性
IV. 数据的初始状态

A. 仅 I
B. 仅 I、II
C. 仅 I、II、IV
D. I、II、III、IV

答案: D

解析:

  • 选择排序算法时，除了时空效率，还应考虑数据的规模、存储方式、稳定性和初始状态等因素。
  • 数据的规模影响选择的排序算法的复杂度，存储方式（如顺序存储与链式存储）会影响算法的实现，稳定性要求会影响可选算法的类型，初始状态影响某些算法的效率。
  • 因此，选择 D 作为答案是正确的。

14.【2020统考真题】对大部分元素已有序的数组排序时，直接插入排序比简单选择排序效率更高，其原因是：

I. 直接插入排序过程中元素之间的比较次数更少
II. 直接插入排序过程中所需的辅助空间更少
III. 直接插入排序过程中元素的移动次数更少

A. 仅 I
B. 仅 III
C. 仅 I、II
D. I、II 和 III

答案: A

解析:

  • 当数组基本有序时，直接插入排序的比较次数为 \(n - 1\)，而简单选择排序的比较次数为 \(n(n - 1)/2\)，因此比较次数上直接插入排序更少。
  • 直接插入排序和简单选择排序的辅助空间都是 \(O(1)\)，所以 II 不成立。
  • 在初始有序的情况下，直接插入排序的移动次数可以为 0，而简单选择排序仍需移动，因此 III 也不一定成立。
  • 因此，只有 I 是正确的，所以选择 A 作为答案。

程序题

问题01

问题: 设关键字序列为 \(\{3,7,6,9,7,1,4,5,20\}\)，对其进行排序的最小交换次数是多少？

解答过程

选择简单选择排序（Selection Sort）来计算最小交换次数，原因如下：

  • 直接插入排序：在有序序列中，可能需要较多的元素移动，但交换次数较少。
  • 简单选择排序：每次选择最小元素并交换到当前位置，因此交换次数容易计算。

初始序列

$ {3, 7, 6, 9, 7, 1, 4, 5, 20} $

排序过程

  1. 第一轮: 找到最小元素 \(1\)，与第一个元素 \(3\) 交换。
    • 交换次数: 1
    • 新序列: \(\{1, 7, 6, 9, 7, 3, 4, 5, 20\}\)
  2. 第二轮: 找到最小元素 \(3\)，与第二个元素 \(7\) 交换。
    • 交换次数: 2
    • 新序列: \(\{1, 3, 6, 9, 7, 7, 4, 5, 20\}\)
  3. 第三轮: 找到最小元素 \(4\)，与第三个元素 \(6\) 交换。
    • 交换次数: 3
    • 新序列: \(\{1, 3, 4, 9, 7, 7, 6, 5, 20\}\)
  4. 第四轮: 找到最小元素 \(5\)，与第四个元素 \(9\) 交换。
    • 交换次数: 4
    • 新序列: \(\{1, 3, 4, 5, 7, 7, 6, 9, 20\}\)
  5. 第五轮: 找到最小元素 \(6\)，与第五个元素 \(7\) 交换。
    • 交换次数: 5
    • 新序列: \(\{1, 3, 4, 5, 6, 7, 7, 9, 20\}\)
  6. 第六轮: 此时，第六个元素 \(7\) 已经在正确的位置，因此无需交换。
    • 新序列: \(\{1, 3, 4, 5, 6, 7, 7, 9, 20\}\)
  7. 第七轮: 第七个元素 \(9\) 也已在正确的位置，因此无需交换。
    • 新序列: \(\{1, 3, 4, 5, 6, 7, 7, 9, 20\}\)
  8. 第八轮: 第八个元素 \(20\) 也是正确的位置，因此无需交换。
    • 最终序列: \(\{1, 3, 4, 5, 6, 7, 7, 9, 20\}\)

最小交换次数

经过以上步骤，最小交换次数为 5。

问题02

问题: 设顺序表用数组 $ A[] $ 表示，表中元素存储在数组下标 $ 1 $ 到 $ m+n $ 的范围内，前 $ m $ 个元素递增有序，后 $ n $ 个元素递增有序，设计一个算法，使得整个顺序表有序。

1. 算法的基本设计思想

算法的基本思想是将已经有序的前 $ m $ 个元素和后 $ n $ 个元素进行合并。可以使用插入排序的方法，将后 $ n $ 个元素逐一插入到前 $ m $ 个元素中。对于每一个后面的元素，从后向前遍历前面的有序部分，找到合适的位置进行插入。

2. 算法的实现（C/C++ 代码）

以下是将后 $ n $ 个元素插入到前 $ m $ 个元素的代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <iostream>
using namespace std;

typedef int ElemType;

void InsertSort(ElemType A[], int m, int n) {
    // 将后 n 个元素依次插入到前 m 个有序元素中
    for (int i = m + 1; i <= m + n; i++) { // 从 A[m + 1] 到 A[m + n]
        ElemType temp = A[i]; // 记录待插入元素
        int j = i - 1; // 从 i - 1 开始向前查找
        // 从后往前移动元素
        while (j > 0 && A[j] > temp) { // 找到合适的位置
            A[j + 1] = A[j]; // 元素后移
            j--; // 移动到前一个位置
        }
        A[j + 1] = temp; // 插入元素
    }
}

int main() {
    ElemType A[] = {0, 1, 3, 5, 7, 0, 2, 4, 6, 8}; // 0 是哨兵，后续为前 m 和 n 个元素
    int m = 5; // 前 m 个元素
    int n = 4; // 后 n 个元素

    InsertSort(A, m, n); // 调用排序函数

    // 输出排序后的数组
    for (int i = 1; i <= m + n; i++) {
        cout << A[i] << " ";
    }
    return 0;
}

3. 时间复杂度与空间复杂度分析

  • 时间复杂度:
    • 在最坏情况下（即后 $ n $ 个元素逆序插入），每个元素都需要与前面的所有元素比较，比较次数为 $ O(m+n) $（每个元素最多比较 $ m $ 次）。
    • 因此，时间复杂度为 $ O(mn) $。
  • 空间复杂度:
    • 该算法只使用了常数个辅助变量（如 temp 和 j），因此空间复杂度为 $ O(1) $。

问题03

问题: 设计计数排序算法，分析关键码比较次数，并与简单选择排序比较其优劣。

1. 计数排序算法的实现

计数排序是一种基于计数的排序算法，适用于待排序数组中关键码互不相同的情况。其基本步骤如下：

  • 对于每个元素，统计关键字比它小的元素个数。
  • 将每个元素放入新数组的对应位置。

以下是 C++ 的实现代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <iostream>
#include <vector>
using namespace std;

void CountSort(int A[], int n) {
    // 创建一个新数组B，用于存放排序结果
    vector<int> B(n); // 输出数组，大小与输入数组相同
    // 计数数组，用于统计每个元素前面有多少个元素比它小
    vector<int> count(n, 0); // 初始化为0

    // 对每个元素进行计数
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (A[j] < A[i]) {
                count[i]++; // 统计比A[i]小的元素个数
            }
        }
    }

    // 根据计数数组构建输出数组B
    for (int i = 0; i < n; i++) {
        B[count[i]] = A[i]; // 将元素放入对应位置
    }

    // 将排序结果拷贝回原数组
    for (int i = 0; i < n; i++) {
        A[i] = B[i];
    }
}

int main() {
    int A[] = {3, 6, 2, 8, 4, 5, 1, 7};
    int n = sizeof(A) / sizeof(A[0]);

    CountSort(A, n);

    // 输出排序后的数组
    cout << "Sorted array: ";
    for (int i = 0; i < n; i++) {
        cout << A[i] << " ";
    }
    cout << endl;

    return 0;
}

2. 关键码比较次数分析

对于有 $ n $ 个记录的表，计数排序中的每个关键码都要与其他 $ n $ 个记录（包括自身）进行比较。因此，关键码的比较次数为 $ O(n^2) $，这是因为对于每个元素 $ A[i] $，我们都需要遍历整个数组 $ A $ 来统计有多少个元素的关键码小于 $ A[i] $。

3. 与简单选择排序的比较

  • 时间复杂度:
    • 计数排序的比较次数为 $ O(n^2) $，尽管在每个元素上只扫描一遍待排序数组。
    • 简单选择排序的比较次数为 $ O(n^2) $，具体比较次数为 $ n(n-1)/2 $，即在最坏情况下比较次数也为 $ O(n^2) $。
  • 空间复杂度:
    • 计数排序需要额外的空间存放结果数组 $ B $ 和计数数组 $ count $，因此空间复杂度为 $ O(n) $。
    • 简单选择排序只使用了常数个辅助空间（交换的临时变量），其空间复杂度为 $ O(1) $。

问题04

问题: 编写一个算法，将无序数组中的一个关键字 $ K $ 放置到排序后数组的正确位置，要求比较关键字的次数不超过 $ n $。

1. 算法基本思想

我们可以使用一种基于快速排序的策略，将目标关键字 $ K $ 插入到其正确位置。具体地，我们可以将数组视为一个待排序的序列，然后将 $ K $ 作为枢轴（pivot），通过一趟分区（partition）来确定 $ K $ 的最终位置。在这趟分区过程中，我们只需要对关键字进行一次遍历，符合比较次数不超过 $ n $ 的要求。

2. 算法实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include <iostream>
#include <vector>
using namespace std;

// Partition函数，将K放在正确的位置
int Partition(vector<int>& K, int n, int pivot) {
    int i = 0, j = n - 1;

    // 将目标元素pivot放到数组末尾
    K.push_back(pivot);  // 将pivot添加到数组末尾

    // 分区操作
    while (i < j) {
        // 从前向后找比pivot大的元素
        while (i < n && K[i] <= pivot) {
            i++;
        }
        // 从后向前找比pivot小的元素
        while (j >= 0 && K[j] >= pivot) {
            j--;
        }
        // 交换找到的元素
        if (i < j) {
            swap(K[i], K[j]);
        }
    }

    // 交换pivot到最终位置
    int pivotIndex = (i < n) ? i : n; // 确定pivot最终位置
    swap(K[pivotIndex], K[n]); // 将pivot放到它的最终位置

    return pivotIndex; // 返回pivot最终位置
}

int main() {
    vector<int> K = {3, 1, 5, 7, 2}; // 无序数组
    int pivot = 4; // 要插入的关键字
    int n = K.size(); // 数组大小

    // 调用Partition函数
    int position = Partition(K, n, pivot);

    // 输出结果
    cout << "The correct position of " << pivot << " is: " << position << endl;
    cout << "Array after placing pivot: ";
    for (int i = 0; i < n; i++) {
        cout << K[i] << " ";
    }
    cout << pivot << endl; // 输出包括插入的pivot

    return 0;
}

问题05

问题: 已知排序算法 cmpCountSort，请回答以下问题：

  1. 若有 int a[]={25,-10,25,10,11,19}, b[6];，则调用 cmpCountSort(a,b,6) 后数组 b 中的内容是什么？
  2. 若 a 中含有 n 个元素，则算法执行过程中，元素之间的比较次数是多少？
  3. 该算法是稳定的吗？若不是，请修改为稳定排序算法。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include <stdio.h>
#include <stdlib.h>

void cmpCountSort(int a[], int b[], int n) {
    int i, j;
    int *count = (int *)malloc(sizeof(int) * n);

    // 初始化计数数组
    for (i = 0; i < n; i++) {
        count[i] = 0;
    }

    // 计算每个元素有多少个元素比它小
    for (i = 0; i < n - 1; i++) {
        for (j = i + 1; j < n; j++) {
            if (a[i] <= a[j]) { // 修改为<=以保证稳定性
                count[j]++;
            } else {
                count[i]++;
            }
        }
    }

    // 根据计数数组将元素放入输出数组
    for (i = 0; i < n; i++) {
        b[count[i]] = a[i];
    }

    // 释放动态分配的内存
    free(count);
}

// 测试代码
int main() {
    int a[] = {25, -10, 25, 10, 11, 19};
    int n = sizeof(a) / sizeof(a[0]);
    int b[6];

    cmpCountSort(a, b, n);

    // 输出排序结果
    printf("排序结果: ");
    for (int i = 0; i < n; i++) {
        printf("%d ", b[i]);
    }
    printf("\n");

    return 0;
}

解答

1. 排序结果

给定数组 a 为 {25, -10, 25, 10, 11, 19}，算法的目的是根据每个元素的大小进行排序。调用 cmpCountSort(a, b, 6) 后，数组 b 的内容是：

1
b[6] = {-10, 10, 11, 19, 25, 25}

解释:

  • 算法遍历数组 a 中的元素，通过 count 数组记录有多少个元素比当前元素大，最后根据这些计数值将元素放到数组 b 的正确位置。
  • 在这里，-10 是最小的，10, 11, 19, 25 是其他元素，其中 25 出现两次，所以在 b 中也出现两次。

2. 比较次数

在算法执行过程中，比较次数由两个嵌套循环决定：

1
2
for(i=0;i<n-1;i++)
    for(j=i+1;j<n;j++)
  • 外层循环迭代 n-1 次，内层循环从 i+1 到 n 进行迭代。
  • 因此，比较次数的总和是： $ (n-1) + (n-2) + ... + 1 = $

因此，总比较次数是 $ $。

3. 稳定性分析

该算法不是稳定的。在排序中，如果两个相等的元素在原数组中的相对顺序在排序后仍然保持相同，则该排序是稳定的。由于代码中使用了以下条件：

1
2
if(a[i] < a[j]) count[j]++;
else count[i]++;

当 a[i] 和 a[j] 相等时，count[j] 不会更新，导致前面的相等元素在排序后的数组中可能会后置。

修改为稳定排序算法: 要使得 cmpCountSort 算法变得稳定，需要在比较时使用小于等于的符号，以确保相等元素的顺序不变。修改后的代码如下：

1
2
3
4
if(a[i] <= a[j]) 
    count[j]++;
else 
    count[i]++;