各种排序算法剖析

一、排序算法基础

1. 核心概念

排序 (Sorting) 排序是将一组杂乱无章的数据元素，按照某个关键字（例如数值大小、字典顺序）调整为有序序列的过程。排序的目标是让数据更易于查找和处理。

稳定性 (Stability) 稳定性是指在待排序的序列中，若存在多个具有相同关键字的元素，经过排序后，这些元素的原有相对顺序保持不变。

例如，序列中有两个元素 $a$ 和 $b$，它们的关键字相同 ($key(a) = key(b)$)，且 $a$ 在 $b$ 前面。如果排序后 $a$ 仍然在 $b$ 的前面，则称该排序算法是稳定的；反之，如果它们的相对位置可能发生改变，则该算法是不稳定的。判断题中经常会考察各种算法的稳定性。

时间复杂度 (Time Complexity) 时间复杂度是衡量算法执行效率的度量，它描述了算法的执行时间随输入数据规模 $n$ 增大的变化趋势。通常使用大O表示法（$O$）来表示。在笔试中，时间复杂度的分析至关重要。

• 最坏情况 (Worst Case): 算法在任何输入下，执行时间最长的情况。
• 平均情况 (Average Case): 算法在所有可能输入下，执行时间的期望值。
• 最好情况 (Best Case): 算法在特定输入下，执行时间最短的情况。

空间复杂度 (Space Complexity) 空间复杂度衡量算法在运行过程中临时占用的存储空间大小。如果算法只需要常数级别的额外空间（即不随数据规模 $n$ 变化），则其空间复杂度为 $O(1)$，也称为原地排序 (in-place sorting)。

2. 排序分类

排序算法可以分为两大类：

• 比较类排序：通过比较元素之间的关键字大小来决定元素的相对次序。其时间复杂度的理论下限是 $O(n \log n)$。常见的比较类排序有冒泡排序、选择排序、插入排序、希尔排序、归并排序、快速排序和堆排序。
• 非比较类排序：不通过比较来确定元素顺序，而是利用元素自身的特性（如数值范围、位数等）来进行排序。它们可以突破比较排序的时间复杂度下限，达到线性时间 $O(n)$。常见的非比较类排序有计数排序、基数排序和桶排序。

二、比较类排序算法

1. 冒泡排序 (Bubble Sort)

核心思想 重复地遍历待排序序列，每次比较相邻的两个元素，如果顺序错误就交换它们。这个过程就像气泡一样，每一轮都会将当前未排序部分的最大（或最小）元素“冒泡”到序列的末尾。

步骤

1. 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
2. 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
3. 针对所有的元素重复以上的步骤，除了最后一个。
4. 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

复杂度与稳定性

• 时间复杂度:
  • 平均情况: $O(n^2)$
  • 最坏情况: $O(n^2)$ (序列逆序)
  • 最好情况: $O(n)$ (序列已基本有序，只需一轮遍历确认)
• 空间复杂度: $O(1)$，是原地排序算法。
• 稳定性: 稳定。因为只有当相邻元素的顺序错误时才交换，相等的元素不会触发交换，它们的相对位置不变。

代码示例

#include<bits/stdc++.h>
using namespace std;
using ll = long long;

// 题意概括: 对一个整型数组进行升序排序。
void bub(int a[], int n) {
    bool flg; // 交换标志
    for (int i = 0; i < n - 1; i++) {
        flg = false;
        // 每一轮将一个最大值冒泡到末尾
        for (int j = 0; j < n - 1 - i; j++) {
            if (a[j] > a[j + 1]) {
                swap(a[j], a[j + 1]);
                flg = true; // 发生交换
            }
        }
        if (!flg) break; // 若一轮没有发生交换，说明已有序
    }
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int a[] = {5, 2, 8, 1, 9, 4};
    int n = sizeof(a) / sizeof(a[0]);
    bub(a, n);
    for (int i = 0; i < n; i++) cout << a[i] << " ";
    cout << endl;
    return 0;
}
// 时间复杂度: O(n^2)
// 空间复杂度: O(1)

2. 选择排序 (Selection Sort)

核心思想 每一轮在未排序的序列中找到最小（或最大）的元素，然后将其放置到已排序序列的末尾。

步骤

1. 在未排序序列 $a[0...n-1]$ 中找到最小的元素，将其与 $a$ 交换。
2. 在未排序序列 $a[1...n-1]$ 中找到最小的元素，将其与 $a$ 交换。
3. 以此类推，直到所有元素都排序完毕。

复杂度与稳定性

• 时间复杂度: $O(n^2)$。选择排序的比较次数与初始序列的排列无关，始终是 $O(n^2)$。
• 空间复杂度: $O(1)$，是原地排序算法。
• 稳定性: 不稳定。 考虑序列 {5, 8, 5, 2, 9}，第一轮找到最小的2，与第一个5交换，序列变为 {2, 8, 5, 5, 9}。两个5的相对位置发生了改变。

代码示例

#include<bits/stdc++.h>
using namespace std;
using ll = long long;

// 题意概括: 对一个整型数组进行升序排序。
void sel(int a[], int n) {
    for (int i = 0; i < n - 1; i++) {
        int min = i; // 记录最小元素的索引
        for (int j = i + 1; j < n; j++) {
            if (a[j] < a[min]) {
                min = j;
            }
        }
        if (min != i) {
            swap(a[i], a[min]);
        }
    }
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int a[] = {5, 2, 8, 1, 9, 4};
    int n = sizeof(a) / sizeof(a[0]);
    sel(a, n);
    for (int i = 0; i < n; i++) cout << a[i] << " ";
    cout << endl;
    return 0;
}
// 时间复杂度: O(n^2)
// 空间复杂度: O(1)

3. 插入排序 (Insertion Sort)

核心思想 将待排序序列分为“已排序”和“未排序”两部分。每次从未排序部分取出一个元素，插入到已排序部分的正确位置，直到所有元素都插入完毕。

步骤

1. 将第一个元素视为已排序序列。
2. 从第二个元素开始，作为待插入元素。
3. 将待插入元素与已排序序列中的元素从后向前比较。
4. 如果已排序元素大于待插入元素，则将该已排序元素向后移动一位。
5. 重复步骤4，直到找到一个小于或等于待插入元素的已排序元素，或已到达序列头部。
6. 将待插入元素插入该位置。
7. 重复上述过程，直到处理完所有元素。

复杂度与稳定性

• 时间复杂度:
  • 平均情况: $O(n^2)$
  • 最坏情况: $O(n^2)$ (序列逆序)
  • 最好情况: $O(n)$ (序列已基本有序)
• 空间复杂度: $O(1)$，是原地排序算法。
• 稳定性: 稳定。因为插入时，只有当已排序元素严格大于待插入元素时才移动，遇到相等的元素会停止移动并插入其后，不会改变相等元素的相对顺序。

代码示例

#include<bits/stdc++.h>
using namespace std;
using ll = long long;

// 题意概括: 对一个整型数组进行升序排序。
void ins(int a[], int n) {
    for (int i = 1; i < n; i++) {
        int cur = a[i]; // 当前待插入元素
        int j = i - 1;
        // 在已排序部分 a[0...i-1] 中寻找插入位置
        while (j >= 0 && a[j] > cur) {
            a[j + 1] = a[j]; // 元素后移
            j--;
        }
        a[j + 1] = cur; // 插入
    }
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int a[] = {5, 2, 8, 1, 9, 4};
    int n = sizeof(a) / sizeof(a[0]);
    ins(a, n);
    for (int i = 0; i < n; i++) cout << a[i] << " ";
    cout << endl;
    return 0;
}
// 时间复杂度: O(n^2)
// 空间复杂度: O(1)

4. 希尔排序 (Shell Sort)

核心思想 希尔排序是插入排序的一种更高效的改进版本。它通过将待排序序列按某个“增量”gap 分成若干个子序列，对每个子序列分别进行插入排序。然后逐步减小增量 gap，重复此过程，直到增量为1。当增量为1时，整个序列基本有序，此时再进行一次插入排序效率会非常高。

步骤

1. 选择一个增量序列，例如 n/2, n/4, ..., 1。
2. 对于第一个增量 gap，将序列分为 gap 个子序列，每个子序列的元素索引相差 gap (例如，a[0], a[gap], a[2*gap], ... 构成一个子序列)。
3. 对这 gap 个子序列分别进行插入排序。
4. 缩小增量 gap，重复步骤2和3。
5. 直到增量 gap = 1，此时对整个序列进行最后一次插入排序。

复杂度与稳定性

• 时间复杂度: 依赖于增量序列的选择，不是一个固定的值。
  • 平均情况: 通常认为在 $O(n \log n)$ 到 $O(n^{1.5})$ 之间。
  • 最坏情况: $O(n^2)$ (例如使用 n/2, n/4, ... 的增量序列)
• 空间复杂度: $O(1)$，是原地排序算法。
• 稳定性: 不稳定。在分子序列排序时，相同关键字的元素可能被分到不同的子序列中，它们的相对顺序可能会改变。

代码示例

#include<bits/stdc++.h>
using namespace std;
using ll = long long;

// 题意概括: 对一个整型数组进行升序排序。
void shl(int a[], int n) {
    // 增量 gap 从 n/2 开始，每次减半
    for (int gap = n / 2; gap > 0; gap /= 2) {
        // 对每个子序列进行插入排序
        for (int i = gap; i < n; i++) {
            int cur = a[i];
            int j = i - gap;
            while (j >= 0 && a[j] > cur) {
                a[j + gap] = a[j];
                j -= gap;
            }
            a[j + gap] = cur;
        }
    }
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int a[] = {5, 2, 8, 1, 9, 4, 3, 7, 6};
    int n = sizeof(a) / sizeof(a[0]);
    shl(a, n);
    for (int i = 0; i < n; i++) cout << a[i] << " ";
    cout << endl;
    return 0;
}
// 时间复杂度: O(n log n) ~ O(n^2)，取决于增量序列
// 空间复杂度: O(1)

5. 归并排序 (Merge Sort)

核心思想 归并排序是分治法 (Divide and Conquer) 的一个典型应用。 它将一个大问题分解为多个小问题来解决。其核心在于“先递归分解，再合并结果”。

步骤

1. 分解 (Divide): 将当前序列递归地从中间对半切分，直到每个子序列只包含一个元素。单个元素的序列自然是有序的。
2. 合并 (Combine): 将相邻的两个有序子序列合并成一个更大的有序序列。合并时，使用两个指针分别指向两个子序列的开头，比较指针所指元素的大小，将较小的元素放入一个临时数组中，并移动相应的指针。重复此过程，直到一个子序列遍历完，再将另一个子序列剩余的元素全部复制到临时数组末尾。最后将临时数组中的结果拷回原数组的对应位置。

复杂度与稳定性

• 时间复杂度: $O(n \log n)$。分解过程是对数级的 ($O(\log n)$)，每层合并过程是线性的 ($O(n)$)。其性能不受输入数据初始顺序的影响。
• 空间复杂度: $O(n)$。合并操作需要一个与当前待合并序列等长的临时数组。
• 稳定性: 稳定。 在合并过程中，如果两个元素相等，可以规定先将被比较的第一个序列中的元素放入临时数组，这样就能保证它们的相对顺序不变。

代码示例

#include<bits/stdc++.h>
using namespace std;
using ll = long long;

// 题意概括: 对一个整型数组的指定区间 [l, r] 进行升序排序。
void mrg(int a[], int l, int m, int r) {
    int n1 = m - l + 1;
    int n2 = r - m;
    vector<int> L(n1), R(n2); // 创建临时数组

    for (int i = 0; i < n1; i++) L[i] = a[l + i];
    for (int j = 0; j < n2; j++) R[j] = a[m + 1 + j];

    int i = 0, j = 0, k = l;
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            a[k++] = L[i++];
        } else {
            a[k++] = R[j++];
        }
    }
    while (i < n1) a[k++] = L[i++];
    while (j < n2) a[k++] = R[j++];
}

void srt(int a[], int l, int r) {
    if (l >= r) return;
    int m = l + (r - l) / 2; // 分解
    srt(a, l, m);
    srt(a, m + 1, r);
    mrg(a, l, m, r); // 合并
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int a[] = {5, 2, 8, 1, 9, 4};
    int n = sizeof(a) / sizeof(a[0]);
    srt(a, 0, n - 1);
    for (int i = 0; i < n; i++) cout << a[i] << " ";
    cout << endl;
    return 0;
}
// 时间复杂度: O(n log n)
// 空间复杂度: O(n)

6. 快速排序 (Quick Sort)

核心思想 快速排序同样是基于分治法的排序算法。 它通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。

步骤

1. 选择基准 (Pivot): 从序列中选择一个元素作为“基准”。
2. 分区 (Partition): 重新排列序列，所有比基准值小的元素摆放在基准前面，所有比基准值大的元素摆在基准的后面。分区结束后，基准元素就位于其最终的排序位置。
3. 递归 (Recurse): 递归地对基准左右两边的子序列重复步骤1和2。

复杂度与稳定性

• 时间复杂度:
  • 平均情况: $O(n \log n)$。
  • 最坏情况: $O(n^2)$。当每次选择的基准都是当前序列的最大或最小元素时发生（例如，对一个已经有序的序列进行排序）。
  • 最好情况: $O(n \log n)$。当每次划分都尽可能均匀时。
• 空间复杂度: $O(\log n)$ (平均情况) 到 $O(n)$ (最坏情况)，主要取决于递归深度。
• 稳定性: 不稳定。 在分区过程中，与基准相等的元素的相对位置可能会因为交换操作而改变。

代码示例

#include<bits/stdc++.h>
using namespace std;
using ll = long long;

// 题意概括: 对一个整型数组的指定区间 [l, r] 进行升序排序。
// par 函数用于分区，并返回基准元素的最终位置
int par(int a[], int l, int r) {
    int piv = a[r]; // 选择最后一个元素作为基准
    int i = l - 1;
    for (int j = l; j < r; j++) {
        if (a[j] < piv) {
            i++;
            swap(a[i], a[j]);
        }
    }
    swap(a[i + 1], a[r]);
    return i + 1;
}

void srt(int a[], int l, int r) {
    if (l >= r) return;
    int p = par(a, l, r); // 分区
    srt(a, l, p - 1); // 递归排序左子序列
    srt(a, p + 1, r); // 递归排序右子序列
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int a[] = {5, 2, 8, 1, 9, 4};
    int n = sizeof(a) / sizeof(a[0]);
    srt(a, 0, n - 1);
    for (int i = 0; i < n; i++) cout << a[i] << " ";
    cout << endl;
    return 0;
}
// 时间复杂度: 平均 O(n log n)，最坏 O(n^2)
// 空间复杂度: 平均 O(log n)，最坏 O(n)

7. 堆排序 (Heap Sort)

核心思想 堆排序利用了“堆”这种数据结构的特性。堆是一棵完全二叉树，且满足堆性质：父节点的值总是大于等于（大顶堆）或小于等于（小顶堆）其子节点的值。 堆排序就是通过构建大顶堆（用于升序排序）或小顶堆（用于降序排序）来实现的。

步骤 (以升序排序为例，使用大顶堆)

1. 建堆 (Build Heap): 将无序的初始序列构建成一个大顶堆。此时，堆顶元素（根节点）是整个序列的最大值。
2. 排序 (Sort): a. 将堆顶元素与序列的最后一个元素交换。此时，最大值被放到了正确的位置。 b. 将序列的长度减1，然后对堆顶元素进行一次“下沉” (heapify) 操作，以维护剩余 $n-1$ 个元素的大顶堆性质。 c. 重复步骤a和b，直到序列中只剩一个元素。

复杂度与稳定性

• 时间复杂度: $O(n \log n)$。建堆的时间复杂度是 $O(n)$，之后进行 $n-1$ 次调整，每次调整的时间复杂度是 $O(\log n)$。
• 空间复杂度: $O(1)$，是原地排序算法。
• 稳定性: 不稳定。 在建堆和调整堆的过程中，元素的交换可能会改变相等元素的相对顺序。

代码示例

#include<bits/stdc++.h>
using namespace std;
using ll = long long;

// 题意概括: 对一个整型数组进行升序排序。
// hpf 函数用于调整以 i 为根的子树，使其成为大顶堆
void hpf(int a[], int n, int i) {
    int lrg = i; // 初始化最大值为根节点
    int l = 2 * i + 1; // 左孩子
    int r = 2 * i + 2; // 右孩子

    if (l < n && a[l] > a[lrg]) lrg = l;
    if (r < n && a[r] > a[lrg]) lrg = r;

    if (lrg != i) {
        swap(a[i], a[lrg]);
        hpf(a, n, lrg); // 递归调整受影响的子树
    }
}

void srt(int a[], int n) {
    // 1. 构建大顶堆
    for (int i = n / 2 - 1; i >= 0; i--) {
        hpf(a, n, i);
    }

    // 2. 逐个提取元素
    for (int i = n - 1; i > 0; i--) {
        swap(a[0], a[i]); // 将当前最大值移到末尾
        hpf(a, i, 0); // 重新调整堆
    }
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int a[] = {5, 2, 8, 1, 9, 4};
    int n = sizeof(a) / sizeof(a[0]);
    srt(a, 0, n - 1); // 修正：应传入数组和大小
    srt(a, n);
    for (int i = 0; i < n; i++) cout << a[i] << " ";
    cout << endl;
    return 0;
}
// 时间复杂度: O(n log n)
// 空间复杂度: O(1)

三、非比较类排序算法

这类算法通常对输入数据有特定要求，例如必须是整数，或分布在有限范围内。

1. 计数排序 (Counting Sort)

核心思想 计数排序是一种非比较排序，它通过统计每个不同整数出现的次数，来确定每个元素在输出序列中的位置。它适用于待排序数据是整数且范围不大（例如，对学生的百分制成绩进行排序）的情况。

步骤

1. 找出范围: 找到待排序数组中的最大值 max 和最小值 min。
2. 计数: 创建一个大小为 max - min + 1 的计数数组 C。遍历原数组，统计每个元素出现的次数。例如，元素 v 出现了 k 次，则 C[v - min] = k。
3. 累加: 修改计数数组 C，使其每一项 C[i] 记录的是小于等于 i + min 的元素的总个数。这通过从 C 的第二项开始，每一项都加上前一项的值来实现。
4. 排序: 创建一个临时数组 B 用于存放排序结果。反向遍历原数组 A，对于每个元素 A[i]，它在排序后数组中的位置是 C[A[i] - min] - 1。将 A[i] 放入 B 的这个位置，然后将 C[A[i] - min] 的值减1。反向遍历是确保算法稳定性的关键。

复杂度与稳定性

• 时间复杂度: $O(n+k)$，其中 $n$ 是待排序元素的数量，$k$ 是元素的范围 ($k = max - min + 1$)。
• 空间复杂度: $O(k)$，需要一个额外的计数数组。
• 稳定性: 稳定。通过从后向前遍历原数组并将元素放入正确位置，可以保证相等元素的原始相对顺序。

代码示例

#include<bits/stdc++.h>
using namespace std;
using ll = long long;

// 题意概括: 对一个非负整数数组进行升序排序。
void cnt(int a[], int n) {
    if (n == 0) return;
    int mx = a[0];
    for (int i = 1; i < n; i++) mx = max(mx, a[i]);

    vector<int> c(mx + 1, 0); // 计数数组
    vector<int> b(n);

    // 1. 统计频率
    for (int i = 0; i < n; i++) c[a[i]]++;

    // 2. 累加频率
    for (int i = 1; i <= mx; i++) c[i] += c[i - 1];

    // 3. 放置到临时数组 b，保证稳定性
    for (int i = n - 1; i >= 0; i--) {
        b[c[a[i]] - 1] = a[i];
        c[a[i]]--;
    }

    // 4. 将结果拷回原数组
    for (int i = 0; i < n; i++) a[i] = b[i];
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int a[] = {5, 2, 8, 1, 9, 2, 4};
    int n = sizeof(a) / sizeof(a[0]);
    cnt(a, n);
    for (int i = 0; i < n; i++) cout << a[i] << " ";
    cout << endl;
    return 0;
}
// 时间复杂度: O(n + k)
// 空间复杂度: O(k)

2. 桶排序 (Bucket Sort)

核心思想 桶排序是计数排序的升级版。它将待排序数据根据一定的映射规则，均匀地分配到有限数量的“桶”中，然后对每个桶内的数据分别进行排序（可以使用其他排序算法，如插入排序），最后按顺序连接所有桶中的数据得到有序序列。

步骤

1. 建桶: 根据待排序数据的范围和分布，设置一定数量的空桶。
2. 入桶: 遍历原序列，将每个元素通过映射函数分配到对应的桶中。
3. 桶内排序: 对每个非空的桶中的元素进行排序。
4. 合并: 按顺序将所有桶中的元素依次取出，放回原序列。

复杂度与稳定性

• 时间复杂度:
  • 平均情况: $O(n+k)$，其中 $k$ 是桶的数量。当数据均匀分布时，每个桶期望有 $O(n/k)$ 个元素，若桶内排序使用 $O(m)$ 的算法（如插入排序在元素少时近似线性），则总时间为 $O(n) + k \cdot O(n/k) = O(n)$。
  • 最坏情况: $O(n^2)$。当所有数据都落入同一个桶中时，桶排序退化为桶内排序算法的复杂度。
• 空间复杂度: $O(n+k)$，需要存储桶和桶内元素。
• 稳定性: 取决于桶内排序算法的稳定性。如果桶内排序是稳定的（如插入排序），那么桶排序也是稳定的。

代码示例

#include<bits/stdc++.h>
using namespace std;
using ll = long long;

// 题意概括: 对一个浮点数数组进行升序排序。
void bkt(float a[], int n) {
    // 1. 创建桶
    vector<float> b[n];

    // 2. 将元素放入不同的桶
    for (int i = 0; i < n; i++) {
        int bi = n * a[i]; // 映射函数
        b[bi].push_back(a[i]);
    }

    // 3. 对每个桶进行排序
    for (int i = 0; i < n; i++) {
        sort(b[i].begin(), b[i].end());
    }

    // 4. 合并所有桶
    int idx = 0;
    for (int i = 0; i < n; i++) {
        for (float x : b[i]) {
            a[idx++] = x;
        }
    }
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    float a[] = {0.8, 0.2, 0.5, 0.1, 0.9, 0.4};
    int n = sizeof(a) / sizeof(a[0]);
    bkt(a, n);
    for (int i = 0; i < n; i++) cout << a[i] << " ";
    cout << endl;
    return 0;
}
// 时间复杂度: 平均 O(n+k)，最坏 O(n^2)
// 空间复杂度: O(n+k)

3. 基数排序 (Radix Sort)

核心思想 基数排序将整数按位数切割成不同的数字，然后从最低位到最高位（LSD, Least Significant Digit first）或从最高位到最低位（MSD, Most Significant Digit first），依次对每一位进行排序。每一位的排序通常使用一种稳定的排序算法，如计数排序。

步骤 (以LSD为例)

1. 确定最大位数: 找到序列中最大数的位数 d。
2. 按位排序: 从最低位（个位）开始，对所有元素的当前位进行一次稳定的排序。
3. 重复步骤2，依次对十位、百位...直到第 d 位进行排序。
4. 完成所有位的排序后，整个序列就有序了。

复杂度与稳定性

• 时间复杂度: $O(d(n+k))$，其中 d 是最大数的位数，n 是元素个数，k 是每一位的取值范围（对于十进制数，k=10）。
• 空间复杂度: $O(n+k)$，取决于内部使用的稳定排序算法（如计数排序）所需的空间。
• 稳定性: 稳定。基数排序的正确性依赖于其内部排序算法的稳定性。

代码示例

#include<bits/stdc++.h>
using namespace std;
using ll = long long;

// 题意概括: 对一个非负整数数组进行升序排序。
// 使用计数排序对数组按指定位 exp 进行排序
void cSort(int a[], int n, int exp) {
    vector<int> out(n);
    int cnt[10] = {0};

    for (int i = 0; i < n; i++) cnt[(a[i] / exp) % 10]++;

    for (int i = 1; i < 10; i++) cnt[i] += cnt[i - 1];

    for (int i = n - 1; i >= 0; i--) {
        out[cnt[(a[i] / exp) % 10] - 1] = a[i];
        cnt[(a[i] / exp) % 10]--;
    }
    for (int i = 0; i < n; i++) a[i] = out[i];
}

void rdx(int a[], int n) {
    if (n == 0) return;
    int mx = a[0];
    for (int i = 1; i < n; i++) mx = max(mx, a[i]);

    // 从个位开始，对每一位进行计数排序
    for (int exp = 1; mx / exp > 0; exp *= 10) {
        cSort(a, n, exp);
    }
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int a[] = {170, 45, 75, 90, 802, 24, 2, 66};
    int n = sizeof(a) / sizeof(a[0]);
    rdx(a, n);
    for (int i = 0; i < n; i++) cout << a[i] << " ";
    cout << endl;
    return 0;
}
// 时间复杂度: O(d(n+k))
// 空间复杂度: O(n+k)

四、算法总结与比较

下表总结了本篇讨论的各种排序算法的关键特性，这对于解答选择题和判断题非常有帮助。

排序算法 (Sorting Algorithm)	平均时间复杂度	最坏时间复杂度	最好时间复杂度	空间复杂度	稳定性
冒泡排序 (Bubble Sort)	$O(n^2)$	$O(n^2)$	$O(n)$	$O(1)$	稳定
选择排序 (Selection Sort)			$O(n^2)$		不稳定
插入排序 (Insertion Sort)			$O(n)$		稳定
希尔排序 (Shell Sort)	$O(n \log n) \sim O(n^{1.5})$		$O(n \log n)$		不稳定
归并排序 (Merge Sort)	$O(n \log n)$	$O(n \log n)$		$O(n)$	稳定
快速排序 (Quick Sort)		$O(n^2)$		$O(\log n)$	不稳定
堆排序 (Heap Sort)		$O(n \log n)$		$O(1)$
计数排序 (Counting Sort)	$O(n+k)$	$O(n+k)$	$O(n+k)$	$O(k)$	稳定
桶排序 (Bucket Sort)		$O(n^2)$		$O(n+k)$
基数排序 (Radix Sort)	$O(d(n+k))$

(表中 $n$ 为数据规模, $k$ 为数据范围或桶的数量, $d$ 为最大值的位数)