基数排序

基数排序（Radix Sort）详解

一、基数排序简介

基数排序（Radix Sort）是一种非比较型整数排序算法，适用于整数或者字符串的排序。它的基本思想是：按照“位”进行排序，先排低位，再排高位，直到所有位都排好。它通常配合计数排序（Counting Sort）在每一位上进行稳定排序。

二、算法原理（以十进制整数为例）

假设我们要排序一组整数：

[170, 45, 75, 90, 802, 24, 2, 66]

我们按照如下步骤排序：

1. 个位排序：对每个数字的个位数排序
   → [170, 90, 802, 2, 24, 45, 75, 66]
2. 十位排序：对每个数字的十位排序
   → [802, 2, 24, 45, 66, 170, 75, 90]
3. 百位排序：对每个数字的百位排序
   → [2, 24, 45, 66, 75, 90, 170, 802]

最终得到有序序列。

三、C++ 程序实例（含详细注释）

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

// 获取数组中的最大值，用来决定排序的轮数（最大位数）
int getMax(const vector<int>& arr) {
    return *max_element(arr.begin(), arr.end());
}

// 对数组按位数进行计数排序
void countingSort(vector<int>& arr, int exp) {
    int n = arr.size();
    vector<int> output(n); // 输出数组
    int count[10] = {0};   // 计数数组（十进制 0~9）

    // 统计每个数字在该位（exp）上的出现次数
    for (int i = 0; i < n; i++) {
        int digit = (arr[i] / exp) % 10;
        count[digit]++;
    }

    // 将 count 数组转化为前缀和数组，确定每个数字在 output 中的位置
    for (int i = 1; i < 10; i++) {
        count[i] += count[i - 1];
    }

    // 从后向前遍历，保持排序稳定性
    for (int i = n - 1; i >= 0; i--) {
        int digit = (arr[i] / exp) % 10;
        output[count[digit] - 1] = arr[i];
        count[digit]--;
    }

    // 将排序结果拷贝回原数组
    for (int i = 0; i < n; i++) {
        arr[i] = output[i];
    }
}

// 基数排序主函数
void radixSort(vector<int>& arr) {
    int maxVal = getMax(arr); // 获取最大数，确定最大位数

    // 从个位开始，对每一位进行排序（exp: 1, 10, 100, ...）
    for (int exp = 1; maxVal / exp > 0; exp *= 10) {
        countingSort(arr, exp);
    }
}

// 打印数组的辅助函数
void printArray(const vector<int>& arr) {
    for (int num : arr) {
        cout << num << " ";
    }
    cout << endl;
}

// 测试程序
int main() {
    vector<int> arr = {170, 45, 75, 90, 802, 24, 2, 66};

    cout << "原始数组: ";
    printArray(arr);

    radixSort(arr);

    cout << "排序后数组: ";
    printArray(arr);

    return 0;
}

四、输出示例

原始数组: 170 45 75 90 802 24 2 66 
排序后数组: 2 24 45 66 75 90 170 802 

五、适用范围与特点

• 适用场景：整数、固定长度字符串
• 时间复杂度：O(nk)，其中 n 是元素个数，k 是位数
• 空间复杂度：O(n + k)
• 稳定性：是稳定排序
• 缺点：对大数或变长数字不适合；占用空间较多