基数排序是一种非比较型的整数排序算法,它的基本思想是：将整数按位数切割成不同的数字，然后按每个位数分别进行比较排序。
（图片来源网络，侵删）
核心思想
基数排序的原理和“计数排序”非常相似，但它是从数字的最低位（个位）开始，到最高位进行排序的，它是一种“分配-收集”的过程。
关键步骤：
- 确定最大位数：我们需要知道数组中最大的数字有多少位，这决定了我们需要进行多少轮“分配-收集”。
- 按位排序：从最低位（个位）到最高位，对每一位进行排序。
- 分配：创建一个“桶”（通常是0-9的数组），遍历原始数组，根据当前位的数字，将元素放入对应的桶中。
- 收集：按照桶的顺序（0号桶到9号桶），将桶中的元素依次放回原始数组。
- 重复：对更高的一位重复“分配-收集”过程，直到所有位都处理完毕。
基数排序 vs 计数排序
很多人会混淆基数排序和计数排序,它们的核心区别在于：
- 计数排序：一次性根据整个元素值的范围来分配位置，它适用于元素值范围不大的情况。
- 基数排序：是多次使用计数排序（或类似的分配方法），但每次只针对数字的某一位进行排序，它适用于数字位数较多，但每一位的范围（0-9）固定的情况。
C 语言实现
下面是一个完整的 C 语言实现，包含了详细的注释。
（图片来源网络，侵删）
#include <stdio.h>
#include <stdlib.h> // 用于 malloc 和 free
// 辅助函数：获取数字的第 exp 位上的数字
// (num / exp) % 10 的作用：
// 1. num / exp：将目标数字移动到个位。
// 当 exp=1 (个位) 时，578 / 1 = 578
// 当 exp=10 (十位) 时，578 / 10 = 58
// 当 exp=100 (百位) 时，578 / 100 = 5
// 2. % 10：取个位上的数字。
// 58 % 10 = 8，5 % 10 = 5
int get_digit(int num, int exp) {
return (num / exp) % 10;
}
// 基数排序主函数
void radix_sort(int arr[], int n) {
// 1. 找出数组中的最大值，以确定排序的轮数（即数字的位数）
int max_val = arr[0];
for (int i = 1; i < n; i++) {
if (arr[i] > max_val) {
max_val = arr[i];
}
}
// 2. 从个位开始，对每一位进行计数排序
// exp 是 10 的幂次方，用于表示当前是哪一位
// 1 (exp^0), 10 (exp^1), 100 (exp^2), ...
for (int exp = 1; max_val / exp > 0; exp *= 10) {
// 创建一个计数数组，大小为10（0-9）
int count[10] = {0};
// --- 分配阶段 ---
// 统计每个桶（0-9）中元素的个数
for (int i = 0; i < n; i++) {
int digit = get_digit(arr[i], exp);
count[digit]++;
}
// --- 计算位置阶段 ---
// 计算每个元素的最终位置
// count[i] 现在存储的是数字 i 的最后一个位置在输出数组中的索引
for (int i = 1; i < 10; i++) {
count[i] += count[i - 1];
}
// --- 收集阶段 ---
// 创建一个临时数组来存放排序结果
int *output = (int *)malloc(n * sizeof(int));
if (output == NULL) {
printf("内存分配失败!\n");
return;
}
// 为了保证排序的稳定性，必须从后向前遍历原始数组
for (int i = n - 1; i >= 0; i--) {
int digit = get_digit(arr[i], exp);
// 将 arr[i] 放到 output 数组的正确位置
output[count[digit] - 1] = arr[i];
// 更新 count[digit]，指向下一个更小的位置
count[digit]--;
}
// --- 将排序结果复制回原数组 ---
for (int i = 0; i < n; i++) {
arr[i] = output[i];
}
// 释放临时数组
free(output);
}
}
// 打印数组的辅助函数
void print_array(int arr[], int size) {
for (int i = 0; i < size; i++) {
printf("%d ", arr[i]);
}
printf("\n");
}
int main() {
int arr[] = {170, 45, 75, 90, 802, 24, 2, 66};
int n = sizeof(arr) / sizeof(arr[0]);
printf("原始数组: \n");
print_array(arr, n);
radix_sort(arr, n);
printf("排序后数组: \n");
print_array(arr, n);
return 0;
}
代码解析
get_digit函数：这是一个核心的辅助函数，巧妙地利用整数除法和取模运算来获取任意指定位的数字。radix_sort函数：- 找最大值：首先遍历数组找到
max_val。max_val的位数决定了外层循环的次数。 - 外层循环：
for (int exp = 1; max_val / exp > 0; exp *= 10)，这个循环控制着排序的轮数。exp从 1 开始（个位），每次乘以 10（十位、百位...），直到max_val / exp变为 0，说明所有位都已处理完毕。 - 内层排序（计数排序思想）：对于
exp的每一位，我们都执行一次完整的计数排序过程。count数组：int count[10] = {0};用于统计 0-9 这十个数字出现的次数。- 统计次数：遍历原数组，用
get_digit获取当前位的数字，并更新count数组。 - 计算位置：
for (int i = 1; i < 10; i++) { count[i] += count[i - 1]; }，这一步是计数排序的关键，它将count数组从“出现次数”转换为“每个数字的最后一个位置索引”，如果count[5]是 12，表示所有个位数为 5 的数字应该放在output数组的索引 11 和 10 上。 - 收集到临时数组：必须从后向前遍历原数组 (
for (int i = n - 1; i >= 0; i--))，这是为了保证排序的稳定性，如果两个数字的当前位相同，后遍历到的数字（在原数组中位置靠后）会被放在临时数组的更后面位置，这样在最终结果中，它们的相对顺序就和原始数组中的一致了。 - 复制回原数组：排序完成后，将
output数组的内容复制回arr，为下一轮排序做准备。 - 内存管理：使用
malloc动态分配output数组的内存，并在使用后用free释放，这是一个良好的编程习惯。
- 找最大值：首先遍历数组找到
算法分析
- 时间复杂度：O(d * (n + k))
d：数字的最大位数。n：待排序元素的数量。k：桶的数量（在十进制中，k=10）。- 当
d是一个常数时（所有数字都是32位或64位整数），时间复杂度可以简化为 O(n)。
- 空间复杂度：O(n + k)
- 主要用于存储
count数组（O(k)）和output临时数组（O(n)）。
- 主要用于存储
- 稳定性：稳定，由于我们在收集阶段是从后向前遍历原数组的，所以相同值的元素的相对顺序会被保留。
- 适用场景：
- 适合整数,特别是位数较多但范围不大的整数。
- 也可以用于字符串、浮点数（需要额外处理）等。
- 不适合小范围或元素数量很少的情况,因为其实现比快速排序等比较排序算法更复杂，有额外的开销。
优点和缺点
优点：
- 时间复杂度为线性：当数字的位数
d固定时，排序速度非常快，比 O(n log n) 的算法（如快速排序、归并排序）在理论上更优。 - 稳定排序：可以保持相等元素的原始相对顺序。
缺点：
- 空间开销大：需要额外的 O(n) 空间来存储临时数组。
- 只适用于整数或特定格式数据：对于字符串或浮点数，需要额外的转换逻辑。
- 对负数的处理：上述代码无法直接处理负数，处理负数的一种常见方法是：先找到最小值，将所有数加上这个最小值的绝对值，使其全部变为非负数，排序完成后再减回去，但这会增加一次额外的遍历。
（图片来源网络，侵删）
