C++基数排序详解（从零开始掌握稳定高效的非比较排序算法）

例如，对数组 [170, 45, 75, 90, 2, 802, 24, 66] 进行排序：

• 首先按个位数排序 → [170, 90, 2, 802, 24, 45, 75, 66]
• 再按十位数排序 → [2, 802, 24, 45, 66, 170, 75, 90]
• 最后按百位数排序 → [2, 24, 45, 66, 75, 90, 170, 802]

为什么选择基数排序？

基数排序具有以下优点：

• 时间复杂度稳定：O(d × (n + k))，其中 d 是最大数的位数，k 是基数（通常为10）
• 稳定排序：相等元素的相对顺序不会改变
• 适合大量整数排序：当数据范围不是特别大时效率很高

C++实现基数排序

下面我们用 C++ 实现一个基于 LSD（最低有效位优先）的基数排序算法：

#include <iostream>#include <vector>#include <algorithm>// 获取数组中最大值int getMax(const std::vector<int>& arr) {    return *std::max_element(arr.begin(), arr.end());}// 对数组按照指定位数（exp=1,10,100...）进行计数排序void countSort(std::vector<int>& arr, int exp) {    int n = arr.size();    std::vector<int> output(n); // 输出数组    std::vector<int> count(10, 0); // 计数数组，基数为10    // 统计当前位上各数字出现的次数    for (int i = 0; i < n; i++) {        count[(arr[i] / exp) % 10]++;    }    // 将count[i]变为实际位置（前缀和）    for (int i = 1; i < 10; i++) {        count[i] += count[i - 1];    }    // 从后往前构建输出数组（保证稳定性）    for (int i = n - 1; i >= 0; i--) {        output[count[(arr[i] / exp) % 10] - 1] = arr[i];        count[(arr[i] / exp) % 10]--;    }    // 将排序结果复制回原数组    for (int i = 0; i < n; i++) {        arr[i] = output[i];    }}// 基数排序主函数void radixSort(std::vector<int>& arr) {    // 找到最大值以确定最大位数    int maxVal = getMax(arr);    // 对每一位进行计数排序    for (int exp = 1; maxVal / exp > 0; exp *= 10) {        countSort(arr, exp);    }}// 测试函数int main() {    std::vector<int> arr = {170, 45, 75, 90, 2, 802, 24, 66};        std::cout << "排序前: ";    for (int x : arr) std::cout << x << " ";    std::cout << std::endl;    radixSort(arr);    std::cout << "排序后: ";    for (int x : arr) std::cout << x << " ";    std::cout << std::endl;    return 0;}

代码解析

上述代码包含三个核心函数：

1. getMax()：获取数组最大值，用于确定循环次数（即最大位数）
2. countSort()：对某一位进行计数排序，这是基数排序的核心子过程
3. radixSort()：主函数，依次对每一位调用 countSort()

注意：countSort() 中我们从后往前遍历原数组，这是为了保证排序的稳定性——相同位数的元素保持原有相对顺序。

适用场景与限制

虽然 C++基数排序 高效且稳定，但它也有使用限制：

• 仅适用于整数、字符串等可按位分解的数据
• 需要额外空间（O(n + k)）
• 当数值范围极大（如 64 位整数）时，效率可能不如快速排序

总结

通过本教程，你已经掌握了 基数排序算法 的原理与 C++ 实现。作为一种稳定排序算法，它在处理特定类型数据时具有显著优势。建议你在实际项目中根据数据特点选择合适的排序方法。动手试试吧，相信你能轻松驾驭这个强大的工具！

掌握 C++排序教程，从基础到进阶，编程之路更顺畅！