使用C++实现基数排序算法

基数排序算法的C++实现¶

什么是基数排序？¶

基数排序（Radix Sort）是一种非比较型整数排序算法，它通过按位排序的方式实现。与冒泡排序、快速排序等基于比较的排序不同，基数排序不需要比较元素的大小，而是根据数字的每一位（如个位、十位、百位等）进行排序，最终达到整体有序的效果。

基数排序的基本思想¶

基数排序通常采用最低有效位优先（LSD） 的方式，即从数字的最低位（个位）开始，依次向最高位（如百位、千位）进行排序。每一位排序时，使用稳定的排序算法（如计数排序）来处理当前位上的数字分布，确保低位排序的结果在高位排序时不被破坏。

实现步骤¶

找出最大数：确定数组中最大数的位数，例如数组中的最大数是802（3位数），则需要处理个位、十位、百位共3位。
按位排序：对每一位（从低位到高位）进行计数排序：
- 统计当前位上每个数字（0-9）出现的次数。
- 根据次数计算每个数字在临时数组中的位置。
- 从后往前遍历原数组，将元素按当前位数字放入临时数组的正确位置，保证稳定性。
- 将临时数组复制回原数组，完成当前位的排序。

C++代码实现¶

#include <iostream>
using namespace std;

// 辅助函数：计数排序（按当前位排序）
void countingSort(int arr[], int n, int exp) {
    int output[n];  // 临时数组存储排序结果
    int count[10] = {0};  // 计数数组，统计0-9出现的次数

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

    // 2. 计算前缀和，确定每个数字的位置
    for (int i = 1; i < 10; i++) {
        count[i] += count[i - 1];
    }

    // 3. 从后往前遍历原数组，稳定地放入临时数组
    for (int i = n - 1; i >= 0; i--) {
        int digit = (arr[i] / exp) % 10;
        output[count[digit] - 1] = arr[i];  // 放置到正确位置
        count[digit]--;  // 保证后续元素位置不冲突
    }

    // 4. 将临时数组结果复制回原数组
    for (int i = 0; i < n; i++) {
        arr[i] = output[i];
    }
}

// 基数排序主函数
void radixSort(int arr[], int n) {
    // 1. 找到数组中的最大数
    int max_num = arr[0];
    for (int i = 1; i < n; i++) {
        if (arr[i] > max_num) {
            max_num = arr[i];
        }
    }

    // 2. 对每一位（从低位到高位）进行计数排序
    for (int exp = 1; max_num / exp > 0; exp *= 10) {
        countingSort(arr, n, exp);
    }
}

// 测试函数
void printArray(int arr[], int n) {
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;
}

int main() {
    int arr[] = {170, 45, 75, 90, 802, 24, 2, 66};
    int n = sizeof(arr) / sizeof(arr[0]);

    cout << "排序前数组：";
    printArray(arr, n);

    radixSort(arr, n);

    cout << "排序后数组：";
    printArray(arr, n);

    return 0;
}

代码解释¶

countingSort函数：
- 统计当前位（由exp决定，如exp=1对应个位）上每个数字（0-9）的出现次数。
- 通过前缀和计算每个数字在临时数组中的位置，确保排序稳定性。
- 从后往前遍历原数组，将元素按当前位数字放入临时数组，避免覆盖已排序元素。
- 将临时数组结果复制回原数组，完成当前位排序。
radixSort函数：
- 找到数组中的最大数，确定需要处理的最高位。
- 按位（从低位到高位）调用countingSort，处理每一位的排序。

测试结果¶

运行上述代码，输出如下：

排序前数组：170 45 75 90 802 24 2 66 
排序后数组：2 24 45 66 75 90 170 802

总结¶

基数排序通过按位分解和计数排序实现，时间复杂度为 O(d×(n+k))（d为最大位数，n为数组长度，k为基数，通常k=10），适用于整数范围较大的场景。其核心是利用计数排序的稳定性，确保低位排序结果在高位排序中保持有序。初学者可通过逐步理解每一位的处理过程，掌握基数排序的设计思想。