📘 基数排序模板（Radix Sort）
动画演示：https://www.bilibili.com/video/BV1zN4y1e73F
核心思路
基数排序是按位排序的，它从最低位到最高位依次对数据进行排序。它采用的是多次稳定排序（比如计数排序）来处理每一位上的数字。比如对于整数，首先按个位进行排序，然后按十位、百位依次排序，直到最高位。
- 找到数组中的最大值，确定需要循环多少位。
- 对每一位执行一次 稳定的计数排序。
- 从最低位开始循环处理，直到最高位。
✅ C++ 模板代码
#include <bits/stdc++.h>
using namespace std;const int MAXN = 1000005; // 最大数据规模
int n, a[MAXN], tmp[MAXN], cnt[10]; // tmp临时数组，cnt计数数组// 基数排序函数
void radix_sort(int a[], int n) {int maxVal = *max_element(a, a + n); // 找最大值，确定位数int exp = 1; // 当前位数，1=个位，10=十位，100=百位...while (maxVal / exp > 0) { // 直到最高位// 1. 初始化计数数组for (int i = 0; i < 10; i++) cnt[i] = 0;// 2. 统计当前位的出现次数for (int i = 0; i < n; i++) {int digit = (a[i] / exp) % 10; // 取出当前位cnt[digit]++;}// 3. 前缀和，cnt[i] 表示 digit ≤ i 的元素个数for (int i = 1; i < 10; i++) cnt[i] += cnt[i - 1];// 4. 倒序遍历，保持稳定性for (int i = n - 1; i >= 0; i--) {int digit = (a[i] / exp) % 10;tmp[cnt[digit] - 1] = a[i];cnt[digit]--;}// 5. 将结果拷贝回原数组for (int i = 0; i < n; i++) a[i] = tmp[i];exp *= 10; // 进入下一位}
}int main() {ios::sync_with_stdio(false);cin.tie(nullptr);cin >> n;for (int i = 0; i < n; i++) cin >> a[i];radix_sort(a, n);for (int i = 0; i < n; i++) cout << a[i] << " ";cout << "\n";return 0;
}
🎯 示例输入输出
输入：
6
170 45 75 90 802 24
输出：
24 45 75 90 170 802
📌 模板特点
- 使用 计数排序 作为子排序算法，保证稳定性。
- 复杂度：
- 时间复杂度： \(O(n \cdot d)\) ，其中 \(d\) 是最大数的位数。
- 空间复杂度： \(O(n + 10)\) 。
- 适用于 非负整数排序（若要处理负数，可以先把负数和非负数分开，再分别排序）。