我已为您将上述关于“非比较类排序算法”的讲义内容进行了整理与深度优化。

在本次整理中，我完成了以下工作： 1. 消除了复制杂质：去除了所有代码块末尾残留的网页行号，并移除了文章尾部的页面导航链接（如 Pager, Previous page 等）。 2. 规范化数学公式：使用标准 LaTeX 语法重新渲染了所有的渐进复杂度符号（例如 $O(n + k)$、$\frac{n}{k}$ 等）、数学公式以及变量名。 3. 优化了代码的可移植性： * 原“桶排序”代码中使用了 vector<float> b[n]; 这种动态大小数组（VLA），这属于 GCC 编译器的非标准扩展，在 MSVC 等其他编译器上会报错。我已将其优化为标准且安全的二重容器 vector<vector<float>> b(n);，从而保证代码在任何支持 C++11 的编译器中都能顺利运行。 4. 统一并美化了全套排序复杂度总结大表：将所有 10 种排序算法（7 种基于比较的算法 + 3 种非比较算法）整合成了结构清晰的对照大表，方便查阅。

以下是整理后的完整 Markdown 内容：

非比较类排序算法

比较类排序算法的时间复杂度理论下限是 $O(n \log n)$。而非比较类排序算法不通过比较来确定元素的相对顺序，而是利用元素自身的特性（如数值范围、位数、分布规律等）进行分治与归纳。

这类算法在特定数据条件下（例如数据均为非负整数、范围可控、分布均匀等）可以突破 $O(n \log n)$ 的下限，达到线性时间复杂度 $O(n)$。

一、 计数排序 (Counting Sort)

1.1 核心思想

计数排序通过统计每个不同整数出现的次数，来确定每个元素在输出序列中的最终位置。它适用于待排序数据是整数且数值范围（极大值与极小值的差值）不大的场景（例如对学生的百分制成绩进行排序）。

1.2 算法步骤

1. 找出范围：找到待排序数组中的最大值 $max$ 和最小值 $min$。
2. 计数：创建一个大小为 $k = max - min + 1$ 的计数数组 $C$。遍历原数组，统计每个元素出现的次数。若元素 $v$ 出现了 $x$ 次，则 $C[v - min] = x$。
3. 前缀和（累加）：修改计数数组 $C$，使其每一项 $C[i]$ 记录的是小于等于 $i + min$ 的元素的总个数。这通过从前向后累加 $C$ 的相邻项实现。
4. 稳定排序：创建一个与原数组等长的临时数组 $B$ 用于存放结果。从后向前反向遍历原数组 $A$，对于元素 $A[i]$，它在排序后数组中的合理位置是 $C[A[i] - min] - 1$。放入后将对应的 $C[A[i] - min]$ 减 $1$。
5. 注：从后向前遍历是确保算法稳定性的关键。

1.3 复杂度与性质

• 时间复杂度：$O(n + k)$，其中 $n$ 是待排序元素的数量，$k$ 是元素的数值范围大小（$k = max - min + 1$）。
• 空间复杂度：$O(n + k)$，需要一个大小为 $k$ 的辅助计数数组以及一个大小为 $n$ 的结果临时输出数组。
• 稳定性：稳定。

1.4 C++ 代码实现

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

// 计数排序：适用于包含重复元素的非负整数数组
void cnt_sort(int a[], int n) {
    if (n <= 1) return;

    int mx = a[0];
    for (int i = 1; i < n; i++) {
        mx = max(mx, a[i]);
    }

    // 计数数组（大小为最大值 + 1）
    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. 从后往前遍历，保证排序的稳定性
    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() {
    int a[] = {5, 2, 8, 1, 9, 2, 4};
    int n = sizeof(a) / sizeof(a[0]);
    cnt_sort(a, n);
    for (int i = 0; i < n; i++) cout << a[i] << " ";
    cout << endl;
    return 0;
}

二、 桶排序 (Bucket Sort)

2.1 核心思想

桶排序是计数排序的升级版。它利用映射函数将待排序数据均匀地分配到有限数量的“桶”中，然后对每个桶内的数据分别进行排序（通常使用插入排序等快速算法），最后按桶的顺序依次收集所有桶中的数据，合并得到一个完整的有序序列。

2.2 算法步骤

1. 建桶：根据待排序数据的范围和分布规律，设置合理数量的空桶。
2. 入桶：遍历原序列，通过映射函数（如根据数值大小归入对应的区间桶）将每个元素分配到对应的桶中。
3. 桶内排序：对每个非空的桶内的元素进行内部排序（例如利用 std::sort 或插入排序）。
4. 合并：按桶的序号顺序将所有桶中的元素依次取出，重新写回原序列中。

2.3 复杂度与性质

• 时间复杂度：
• 平均情况：$O(n + k)$，其中 $k$ 为桶的数量。若数据分布极为均匀，每个桶期望分到 $O(n/k)$ 个元素。对每个桶进行排序若采用 $O(m \log m)$ 算法，总时间开销为 $O(n) + k \cdot O(\frac{n}{k} \log \frac{n}{k})$。当 $k \approx n$ 时，复杂度逼近线性 $O(n)$。
• 最坏情况：$O(n^2)$。当所有数据被分配到同一个桶中时，算法退化为该桶内的单一排序算法。
• 空间复杂度：$O(n + k)$，需要额外的空间来维护桶的结构及存储桶内的元素。
• 稳定性：稳定。只要桶内排序算法是稳定的（如插入排序或归并排序），桶排序本身就是稳定的。

2.4 C++ 代码实现

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

// 桶排序：适用于在 [0, 1) 区间内均匀分布的浮点数数组
void bkt_sort(float a[], int n) {
    if (n <= 1) return;

    // 1. 创建 n 个桶（使用 vector 嵌套避免静态数组越界和标准兼容问题）
    vector<vector<float>> b(n);

    // 2. 映射元素入桶
    for (int i = 0; i < n; i++) {
        int bi = n * a[i]; // 映射函数：[0, 1) 区间均匀映射到 0 ~ n-1 桶中
        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() {
    float a[] = {0.8, 0.2, 0.5, 0.1, 0.9, 0.4};
    int n = sizeof(a) / sizeof(a[0]);
    bkt_sort(a, n);
    for (int i = 0; i < n; i++) cout << a[i] << " ";
    cout << endl;
    return 0;
}

三、 基数排序 (Radix Sort)

3.1 核心思想

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

3.2 算法步骤（以 LSD 为例）

1. 确定最大位数：找出待排序序列中最大数，并确定其最大位数 $d$。
2. 按位排序：从最低位（个位）开始，对所有元素的当前位执行一次稳定的计数排序。
3. 向高位递进：依次对十位、百位……直到最高第 $d$ 位重复上述稳定的位排序。
4. 当完成所有有效数位的排序后，整个序列即变为有序。

3.3 复杂度与性质

• 时间复杂度：$O(d(n + k))$，其中 $d$ 是最大数的十进制位数，$n$ 是元素个数，$k$ 是每一位数码的取值范围（对于十进制数，$k = 10$）。由于 $d$ 和 $k$ 通常很小，基数排序在处理大整数集合时速度非常快。
• 空间复杂度：$O(n + k)$，主要取决于底层使用的稳定单次排序（计数排序）所占用的辅助数组空间。
• 稳定性：稳定。基数排序的正确性高度依赖于各单次位排序过程中必须保持“稳定性”。

3.4 C++ 代码实现

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

// 基于计数排序的单数位稳定排序
// exp 为当前比较的数位基数（例如：个位 exp=1，十位 exp=10，百位 exp=100）
void count_sort_by_digit(int a[], int n, int exp) {
    vector<int> out(n);
    int cnt[10] = {0}; // 0~9 计数桶

    // 1. 统计当前数位上数字的出现频率
    for (int i = 0; i < n; i++) {
        int digit = (a[i] / exp) % 10;
        cnt[digit]++;
    }

    // 2. 累加频率（计算前缀和）
    for (int i = 1; i < 10; i++) {
        cnt[i] += cnt[i - 1];
    }

    // 3. 从后往前放置元素，保证相同位的数相对位置不乱（稳定性）
    for (int i = n - 1; i >= 0; i--) {
        int digit = (a[i] / exp) % 10;
        out[cnt[digit] - 1] = a[i];
        cnt[digit]--;
    }

    // 4. 将本轮排好序的数据拷回原数组
    for (int i = 0; i < n; i++) {
        a[i] = out[i];
    }
}

// 基数排序主入口
void rdx_sort(int a[], int n) {
    if (n <= 1) return;

    // 找出最大值以确定最高数位
    int mx = a[0];
    for (int i = 1; i < n; i++) {
        mx = max(mx, a[i]);
    }

    // 从个位（exp = 1）开始，对每一位执行稳定的计数排序，每次乘 10 向上移位
    for (int exp = 1; mx / exp > 0; exp *= 10) {
        count_sort_by_digit(a, n, exp);
    }
}

int main() {
    int a[] = {170, 45, 75, 90, 802, 24, 2, 66};
    int n = sizeof(a) / sizeof(a[0]);
    rdx_sort(a, n);
    for (int i = 0; i < n; i++) cout << a[i] << " ";
    cout << endl;
    return 0;
}

四、 全套排序算法复杂度与特性小结

下表对比较类排序算法与非比较类排序算法进行了综合对比：

(表中 $n$ 为待排序数据规模；$k$ 在计数排序中表示数据极差范围，在桶排序和基数排序中表示桶数或字符集数；$d$ 表示数值的最大数位位数)

—— 本文来自火龙信奥（义乌睿码科技）：义乌青少年信息学奥赛与编程教育平台，专注 CSP-J/S、NOIP、GESP 竞赛培训，线上线下融合教学，助力编程升学。网址：hlcoding.com