数据结构之归并排序和基数排序

归并排序

归并排序是一种有效的排序算法，主要思想是将两个或多个已经排序的子表合并为一个新的有序表。其基本步骤如下：

  1. 初始状态：
    • 假定待排序的序列包含 $ n $ 个记录，视为 $ n $ 个长度为 1 的有序子表。
    • 将这些有序子表两两合并，形成 $ n/2 $ 个长度为 2 或 1 的有序表。
    • 继续两两合并，直到最终形成一个长度为 $ n $ 的有序表。
  2. 归并过程：
    • 设有两个有序表 $ A[low..mid] $ 和 $ A[mid+1..high] $，利用辅助数组 $ B $ 来合并它们：
      • 首先将 $ A $ 中的这两段复制到 $ B $ 中。
      • 然后，从 $ B $ 中分别取出当前最小的元素，比较后放入原数组 $ A $ 中，直到一个子表元素处理完。
      • 最后，将另一个子表的剩余元素直接复制到 $ A $ 中。
  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
51
52
53
54
55
56
57
58
59
60
61
62
#include<bits/stdc++.h>
#include <cstdlib>
using namespace std;

typedef int ElemType;

void Merge(ElemType A[], int low, int mid, int high) {
    int i = low, j = mid + 1, k = low;
    ElemType* B = (ElemType*)malloc((high - low + 1) * sizeof(ElemType)); // 辅助数组

    // 将A中所有元素复制到B中
    for (int m = low; m <= high; m++) {
        B[m - low] = A[m];
    }

    // 比较B的左右两段中的元素并合并到A中
    while (i <= mid && j <= high) {
        if (B[i - low] <= B[j - low]) {
            A[k++] = B[i++ - low];
        } else {
            A[k++] = B[j++ - low];
        }
    }

    // 若第一个表未检测完，复制剩余元素
    while (i <= mid) {
        A[k++] = B[i++ - low];
    }

    // 若第二个表未检测完，复制剩余元素
    while (j <= high) {
        A[k++] = B[j++ - low];
    }

    free(B); // 释放辅助数组
}

void MergeSort(ElemType A[], int low, int high) {
    if (low < high) {
        int mid = (low + high) / 2; // 从中间划分两个子序列
        MergeSort(A, low, mid); // 对左侧子序列进行递归排序
        MergeSort(A, mid + 1, high); // 对右侧子序列进行递归排序
        Merge(A, low, mid, high); // 归并
    }
}

int main() {
    ElemType A[] = {0, 27, 49, 38, 65, 97, 76, 13, 65}; // 假设 A[0] 为无效，实际使用从 A[1] 开始
    int len = sizeof(A) / sizeof(A[0]) - 1; // 计算有效长度

    MergeSort(A, 1, len); // 执行归并排序

    // 输出排序结果
    cout << "排序结果: ";
    for (int i = 1; i <= len; i++) {
        cout << A[i] << " ";
    }
    cout << endl;

    return 0;
}

归并排序的性能分析

  1. 时间复杂度：
    • 每趟归并的时间复杂度为 $ O(n) $，共需进行 $ _2 n $ 趟归并。
    • 因此，归并排序的总体时间复杂度为 $ O(n _2 n) $。
  2. 空间复杂度：
    • 归并排序在进行合并时需要使用辅助数组 $ B $，其空间复杂度为 $ O(n) $。
  3. 稳定性：
    • 归并排序是稳定的排序方法，因为在归并过程中，相同关键字的元素相对顺序不会被改变。
  4. 一般化：
    • 对于 $ N $ 个元素进行 $ k $ 路归并排序时，排序的趟数 $ m $ 满足 $ k^m = N $，从而 $ m = _k N $。
    • 这种归并方法的性质与 2 路归并一致。

基数排序

基数排序是一种非比较型排序算法，利用关键字各位的大小进行排序。其主要特征是通过对每个关键字的不同位进行排序，从而实现整个序列的排序。基数排序分为两种主要方法：最高位优先（MSD）和最低位优先（LSD）。本节重点讨论最低位优先（LSD）法。

基本概念

  • 关键字结构：假设长度为 $ n $ 的线性表中每个结点 $ q $ 的关键字由 $ d $ 位元组 $ (k_0, k_1, , k_{d-1}) $ 组成，满足 $ 0 k_j r - 1 $（其中 $ 0 j < n, 0 i < d \(）。\) k_0 $ 为最主位关键字，$ k_{d-1} $ 为最次位关键字。

  • 基数：基数 $ r $ 是每位可能的取值数，通常为 10（十进制）或 256（字节）。

排序过程

基数排序的过程通常分为以下几个步骤：

  1. 分配：
    • 初始化 $ r $ 个空队列 $ Q_0, Q_1, , Q_{r-1} $。
    • 对于线性表中的每个结点 $ q $，根据当前关键字位（个位、十位、百位等）将 $ q $ 放入相应的队列。
  2. 收集：
    • 按照队列的顺序依次将各个队列中的记录收集到新的线性表中，形成新的序列。

具体示例

考虑对以下 10 个记录进行基数排序：

1
278, 109, 063, 930, 589, 184, 505, 269, 008, 083
image-20241009193140842
image-20241009193147697
image-20241009193156676

算法性能分析

  • 时间复杂度：
    • 每趟分配和收集的时间复杂度为 $ O(n) $。
    • 基数排序需要进行 $ d $ 趟分配和收集，因此整体时间复杂度为 $ O(d(n + r)) $。
  • 空间复杂度：
    • 需要 $ r $ 个队列进行分配，空间复杂度为 $ O(r) $。
    • 通常来说，基数排序的空间复杂度为 $ O(n + r) $。
  • 稳定性：
    • 基数排序是稳定的，因为在每一趟分配和收集操作中，记录的相对次序不会改变。