基数排序（Radix Sort）

基数排序是一种非比较型排序算法，它通过按位对数字进行排序，通常用于对整数进行排序。它将所有数字看成是按位数划分的，每一位上的数字单独参与排序。基数排序分为两类：LSD（Least Significant Digit First，最小有效位优先）和 MSD（Most Significant Digit First，最大有效位优先）。一般来说，基数排序使用 LSD 方法实现。

基数排序的基本思想是：从最低有效位（即数字的个位）开始，将数组中的数字按每一位的大小进行排序，然后依次处理高位，最终得到一个有序的数组。

实现原理

分组按位排序：
- 假设待排序的数字是非负整数，我们从个位开始，将所有数字按个位的数字分类；然后按十位排序，依此类推，直到最大的位。
- 每一位的排序都采用稳定的排序方法（例如桶排序），稳定排序的特点是相同的元素不会改变它们在原始序列中的相对顺序。
步骤：
- 对于每一位，使用一个稳定的排序算法（如计数排序）将数字按该位排序。
- 从最低有效位开始排序，一直排序到最高有效位。
- 排序完成后，所有的元素都会根据每一位数值被排好序。
时间复杂度：
- 时间复杂度为
  
  O(d * (n + k))，其中：
  - d 是数字的位数，n 是待排序的元素个数，k 是基数（桶的大小，通常是 10）。
- 对于每一位数的排序，使用的是稳定的排序算法（通常选择计数排序），时间复杂度为 O(n + k)，而位数 d 是数字的位数。

代码实现

#include <iostream>
using namespace std;

// 计数排序，用于按某一位排序
void countingSort(int arr[], int n, int exp) {
    int *output = new int[n];  // 存储排序结果
    int count[10] = { 0 };  // 计数数组，基数排序的基数为10

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

    // 计算每个元素的最终位置
    for (int i = 1; i < 10; i++) {
        count[i] += count[i - 1];
    }

    // 构建输出数组
    for (int i = n - 1; i >= 0; i--) {
        int index = (arr[i] / exp) % 10;
        output[count[index] - 1] = arr[i];
        count[index]--;
    }

    // 将输出数组复制到原数组
    for (int i = 0; i < n; i++) {
        arr[i] = output[i];
    }
}

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

    // 从个位开始，一直到最大数的最高位
    for (int exp = 1; maxVal / 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）：
- countingSort 用来对数组中根据某一位数的值进行排序。exp 代表当前排序的位数（个位、十位等）。
- 通过取 arr[i] / exp % 10 来获取当前数字的某一位上的值，这个值决定了该数字应该在计数数组 count 中的哪个位置。
- 然后，我们使用计数数组来确定每个数字在排序结果中的位置，并将其填充到 output 数组中，最后更新原始数组。
基数排序（radixSort）：
- radixSort 函数通过多次调用 countingSort 来对数组进行排序。每次排序时，exp 表示当前排序的位数。exp 从个位开始，逐渐增大，直到处理完最大数字的最高位。
- maxVal 是数组中的最大值，它决定了排序的位数。
主函数：
- 创建一个整数数组并打印原始数组。
- 调用 radixSort 函数进行排序。
- 打印排序后的数组。