C++中如何高效实现基数排序？深入理解算法原理与代码实践

排序算法是计算机科学中的基石，常见的快速排序和归并排序都属于基于比较的排序，理论时间复杂度下限为O(n log n)。当需要处理大规模数据且对性能有极致要求时，非比较排序算法往往能突破这一下限。基数排序正是这样一种经典的非比较排序算法，它通过按数据的各个位进行分配和收集，达到线性时间复杂度的排序效果。在C++中实现基数排序，不仅能加深对数组操作和内存管理的理解，还能在处理特定类型数据时提供显著的性能提升。

基数排序的核心原理与实现步骤

基数排序的核心思想是多关键字排序。它将一个数值按位拆分，从最低位到最高位（或从最高位到最低位）依次进行排序。通常情况下，基数排序会以十进制为基础，将数字按个位、十位、百位等依次处理。每一次针对特定位的排序，都必须使用稳定的排序算法作为子程序，以确保前一次排序的相对顺序在当前位相同时不会被破坏。计数排序因其稳定性和线性时间复杂度，成为了基数排序最常用的子程序。

在C++中实现基数排序，主要分为以下几个步骤。首先需要找出数组中的最大值，以确定最高位数，这决定了需要进行几轮排序。接着，对于每一位（从个位开始），创建十个桶（代表0到9），遍历数组将元素分配到对应的桶中。分配完成后，按顺序将桶中的元素收集回原数组。这个过程重复进行，直到最高位处理完毕。这种从最低位开始的方法被称为最低位优先（LSD）基数排序。

以下是C++中LSD基数排序的基础代码实现。代码中使用了计数排序来对每一位进行排序，避免了显式创建链表桶带来的额外开销，提高了缓存命中率。

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// 获取数字的第d位（从低到高，d=1为个位）
int getDigit(int num, int d) {
    int div = 1;
    for (int i = 1; i < d; i++) {
        div *= 10;
    }
    return (num / div) % 10;
}

// 基数排序主函数
void radixSort(vector<int>& arr) {
    if (arr.empty()) return;

    // 找到最大值以确定最大位数
    int maxVal = *max_element(arr.begin(), arr.end());
    int maxDigit = 0;
    while (maxVal > 0) {
        maxVal /= 10;
        maxDigit++;
    }

    // 临时数组和计数数组
    vector<int> temp(arr.size());
    vector<int> count(10, 0);

    // 从低位到高位进行排序
    for (int d = 1; d <= maxDigit; d++) {
        // 计数数组清零
        fill(count.begin(), count.end(), 0);

        // 统计每个桶中的元素个数
        for (int i = 0; i < arr.size(); i++) {
            int digit = getDigit(arr[i], d);
            count[digit]++;
        }

        // 计算累加频次，确定元素在临时数组中的位置
        for (int i = 1; i < 10; i++) {
            count[i] += count[i - 1];
        }

        // 反向遍历原数组，保证排序稳定性
        for (int i = arr.size() - 1; i >= 0; i--) {
            int digit = getDigit(arr[i], d);
            temp[count[digit] - 1] = arr[i];
            count[digit]--;
        }

        // 将临时数组拷贝回原数组
        for (int i = 0; i < arr.size(); i++) {
            arr[i] = temp[i];
        }
    }
}

int main() {
    vector<int> arr = {170, 45, 75, 90, 802, 24, 2, 66};
    radixSort(arr);
    for (int num : arr) {
        cout << num << " ";
    }
    return 0;
}

LSD与MSD策略的对比与选择

基数排序根据遍历数字的方向不同，分为最低位优先（LSD）和最高位优先（MSD）两种策略。LSD基数排序从最低位开始向最高位推进，要求所有待排序数字的位数对齐。这种策略实现相对简单，通常需要遍历完所有位数才能得到最终结果，适用于长度相近的整数排序。上一节提供的代码示例就是典型的LSD实现。

MSD基数排序则从最高位开始处理。它首先根据最高位将数据分配到各个桶中，如果某个桶内的元素多于一个，则递归地对这个桶内的元素按次高位进行排序。MSD排序的一个显著优点是，当高位已经确定了大小时，低位可能不需要再排序，这在处理字符串前缀匹配时非常高效。然而，MSD的递归实现会带来额外的函数调用开销，并且在处理包含大量重复高位的数据时，可能导致递归深度过大或桶空间分配不均。

在C++中，选择LSD还是MSD取决于具体的应用场景。如果是对整型数组进行排序，LSD通常是更好的选择，因为其循环结构在现代CPU上的分支预测和缓存利用方面表现更优。如果是对变长字符串进行字典序排序，MSD则更为合适。下面是一个针对字符串的MSD基数排序的简要思路展示，通过递归调用实现。

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

// MSD基数排序的递归辅助函数
void msdSortHelper(vector<string>& arr, int left, int right, int d) {
    if (left >= right) return;

    // 256个桶对应ASCII字符，外加一个处理短字符串的桶
    vector<int> count(257, 0);
    vector<string> temp(right - left + 1);

    // 统计字符频次
    for (int i = left; i <= right; i++) {
        int idx = (d < arr[i].length()) ? (unsigned char)arr[i][d] + 1 : 0;
        count[idx]++;
    }

    // 累加频次
    for (int i = 1; i < 257; i++) {
        count[i] += count[i - 1];
    }

    // 分配到临时数组
    for (int i = right; i >= left; i--) {
        int idx = (d < arr[i].length()) ? (unsigned char)arr[i][d] + 1 : 0;
        temp[count[idx] - 1] = arr[i];
        count[idx]--;
    }

    // 拷贝回原数组
    for (int i = 0; i < temp.size(); i++) {
        arr[left + i] = temp[i];
    }

    // 递归处理各个桶
    int start = left;
    for (int i = 0; i < 256; i++) {
        int end = left + count[i + 1] - 1;
        if (end > start) {
            msdSortHelper(arr, start, end, d + 1);
        }
        start = left + count[i + 1];
    }
}

void msdRadixSort(vector<string>& arr) {
    msdSortHelper(arr, 0, arr.size() - 1, 0);
}

基数排序的性能分析与优化策略

基数排序的时间复杂度为O(d * (n + k))，其中d是最大数字的位数，n是元素个数，k是基数（如十进制的k为10）。当d为常数时，时间复杂度退化为O(n)。这使得基数排序在处理大规模数据时，速度远超O(n log n)的比较排序算法。然而，空间复杂度是基数排序的一个短板，它需要额外的O(n + k)空间来存放临时数据和计数数组。在内存受限的嵌入式系统中，这可能成为一个需要权衡的因素。

为了提升C++中基数排序的实际运行效率，可以考虑对基数进行优化。传统的十进制基数意味着对于32位整数，需要进行最多10轮排序。如果将基数提升到256（即按字节排序），则只需要4轮（32位整数占4字节）。更大的基数减少了排序轮数，但增加了计数数组的大小和缓存失效的可能。通常，选择2的幂次方作为基数可以利用位运算代替除法，进一步提升性能。下面展示了按字节（基数为256）进行排序的核心逻辑片段。

// 按字节进行排序的基数排序（仅适用于非负整数）
void radixSortByByte(vector<unsigned int>& arr) {
    if (arr.empty()) return;

    vector<unsigned int> temp(arr.size());
    // 4个字节，循环4次
    for (int byteIndex = 0; byteIndex < 4; byteIndex++) {
        vector<int> count(256, 0);
        int shift = byteIndex * 8;

        // 统计频次
        for (int i = 0; i < arr.size(); i++) {
            unsigned char byteVal = (arr[i] >> shift) & 0xFF;
            count[byteVal]++;
        }

        // 累加频次
        for (int i = 1; i < 256; i++) {
            count[i] += count[i - 1];
        }

        // 反向填充保证稳定性
        for (int i = arr.size() - 1; i >= 0; i--) {
            unsigned char byteVal = (arr[i] >> shift) & 0xFF;
            temp[count[byteVal] - 1] = arr[i];
            count[byteVal]--;
        }

        // 交换指针，避免拷贝
        arr.swap(temp);
    }
}

此外，处理包含负数的数组是基数排序的一个常见痛点。由于补码的存在，负数的最高位符号位为1，在无符号比较下会被判定为大于正数。为了在C++中正确处理负数，可以在排序前将所有数据映射到无符号空间，例如通过将每个整数与0x80000000进行异或操作，将带符号整数转换为无符号整数序列，排序完成后再转换回去。这种预处理方式能够保证整个排序过程依然保持线性时间复杂度，同时正确处理正负数的大小关系。

C++基数排序基数排序算法非比较排序修改时间：2026-08-24 06:54:09