排序算法（三）：基数排序、桶排序、外部排序概念、各种排序算法比较
聊完了快速排序、归并排序这些“内卷王”，咱们今天来点不一样的。基数排序、桶排序，还有外部排序，它们解决问题的思路完全不同。我个人习惯把前两种叫做“非比较排序”，因为它们不靠元素之间比大小来干活。而外部排序，说白了就是内存装不下数据时，我们怎么硬着头皮把数据排好。
嗯，这一章内容有点多，但都很实用。咱们一个一个来。
一、基数排序（Radix Sort）
基数排序的思路很朴素：按位排。比如排整数，先按个位排，再按十位排，最后按百位排。每次排序都是稳定的，这样高位排完，低位的有序性不会被破坏。
你想想看，这就像整理一堆发票。先按月份分，再按日期分。月份大的放后面，月份相同的，日期小的放前面。是不是很直观？
基数排序有两种实现方式：
- LSD（Least Significant Digit）：从低位到高位。最常用。
- MSD（Most Significant Digit）：从高位到低位。需要递归，实现稍复杂。
我一般在项目中用LSD，配合计数排序作为内层排序。为什么？因为计数排序是稳定的，而且处理小范围整数时效率极高。
来看代码：
// 基数排序 - LSD版本
// 假设数据范围是0-999，三位数
void radix_sort(int arr[], int n) {
// 找最大值，确定位数
int max = arr[0];
for (int i = 1; i < n; i++) {
if (arr[i] > max) max = arr[i];
}
// 按每一位排序
for (int exp = 1; max / exp > 0; exp *= 10) {
counting_sort_by_digit(arr, n, exp);
}
}
// 按某一位进行计数排序
void counting_sort_by_digit(int arr[], int n, int exp) {
int output[n];
int count[10] = {0};
// 统计当前位出现次数
for (int i = 0; i < n; i++) {
int digit = (arr[i] / exp) % 10;
count[digit]++;
}
// 累加，得到位置索引
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];
}
}我曾经在一个嵌入式项目里处理传感器采集的整数数据，数据量上万，范围固定。用基数排序比快速排序还快，因为避免了大量的比较和递归调用。嗯，嵌入式环境里递归有时候挺奢侈的。
二、桶排序（Bucket Sort）
桶排序的思路更直接：把数据分到几个桶里，每个桶内部再排序，最后把桶合并起来。
说白了，就是“分而治之”的另一种形式。但这里的分不是二分，而是根据数据范围均匀划分。
适用场景：数据分布比较均匀的时候。如果数据全挤在一个桶里，那就退化成普通排序了。
// 桶排序 - 假设数据范围[0, 1)的浮点数
void bucket_sort(float arr[], int n) {
// 创建n个桶
float** buckets = (float**)malloc(n * sizeof(float*));
int* bucket_sizes = (int*)calloc(n, sizeof(int));
for (int i = 0; i < n; i++) {
buckets[i] = (float*)malloc(n * sizeof(float));
}
// 将元素放入桶中
for (int i = 0; i < n; i++) {
int bucket_index = n * arr[i]; // 映射到桶
buckets[bucket_index][bucket_sizes[bucket_index]++] = arr[i];
}
// 对每个桶内部排序（这里用插入排序）
for (int i = 0; i < n; i++) {
insertion_sort(buckets[i], bucket_sizes[i]);
}
// 合并所有桶
int index = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < bucket_sizes[i]; j++) {
arr[index++] = buckets[i][j];
}
}
// 释放内存
for (int i = 0; i < n; i++) free(buckets[i]);
free(buckets);
free(bucket_sizes);
}我记得有一次处理GPS坐标数据，数据量不大但分布很散。用桶排序，每个桶里就几个点，插入排序几下就搞定了。比调快速排序的递归栈舒服多了。
三、外部排序（External Sort）
外部排序，说白了就是数据太大，内存装不下，得借助磁盘来排。
你想想看，一个文件有10GB，内存只有1GB，你怎么排？
经典做法是“归并排序”的变种——多路归并。
- 分割阶段：把大文件分成若干个小块，每块能装进内存。对每块内部排序，写回磁盘。这些排好序的小块叫“归并段”。
- 归并阶段：同时打开多个归并段文件，用最小堆或败者树选出当前最小的元素，写入输出文件。
这里有个关键点：归并的路数越多，需要的磁盘I/O次数越少。但路数多了，内存里维护的堆就大了。这是个权衡。
我曾经在一个日志分析项目里处理过几十GB的文本数据。当时用C语言写了个外部排序工具，归并路数选了16路，缓冲区大小调了几次才找到最优值。嗯，调优的过程挺折磨人的，但跑起来那一刻很爽。
四、各种排序算法比较
好了，咱们把常见的排序算法拉出来遛遛。我整理了一张表，方便你对比：
| 算法 | 平均时间复杂度 | 最坏时间复杂度 | 空间复杂度 | 稳定性 | 适用场景 |
|---|---|---|---|---|---|
| 冒泡排序 | O(n²) | O(n²) | O(1) | 稳定 | 几乎不用，教学意义 |
| 选择排序 | O(n²) | O(n²) | O(1) | 不稳定 | 数据量极小 |
| 插入排序 | O(n²) | O(n²) | O(1) | 稳定 | 小规模或基本有序 |
| 希尔排序 | O(n^1.3) | O(n²) | O(1) | 不稳定 | 中等规模 |
| 归并排序 | O(n log n) | O(n log n) | O(n) | 稳定 | 大规模、需要稳定 |
| 快速排序 | O(n log n) | O(n²) | O(log n) | 不稳定 | 通用，最常用 |
| 堆排序 | O(n log n) | O(n log n) | O(1) | 不稳定 | 内存受限、需要最坏保证 |
| 计数排序 | O(n + k) | O(n + k) | O(k) | 稳定 | 整数、范围小 |
| 基数排序 | O(d(n + k)) | O(d(n + k)) | O(n + k) | 稳定 | 整数、固定位数 |
| 桶排序 | O(n + k) | O(n²) | O(n + k) | 稳定 | 数据分布均匀 |
怎么选？我个人的经验是：
- 数据量小（几百以内）：插入排序就够，代码简单，没有额外开销。
- 数据量大、内存够：快速排序，注意选好基准值，避免退化。
- 需要稳定性：归并排序，或者用稳定的基数排序（如果数据合适）。
- 内存非常紧张：堆排序，空间O(1)，最坏也是O(n log n)。
- 数据有特殊规律：比如整数、范围小，用计数或基数排序，能快一个数量级。
五、知识体系总览
下面这张图把本章的核心内容串起来了。你可以看到排序算法的分类、各自的特点，以及它们之间的关联。
从图上可以看得很清楚：比较排序家族人丁兴旺，但非比较排序在某些特定场景下能实现线性时间复杂度。外部排序则是一个独立的领域，处理的是内存装不下的情况。
好了，这一章的内容就到这里。排序算法这块，理论是一回事，真正用到项目里又是另一回事。我建议你多动手写代码，多跑测试数据，慢慢就会有自己的“手感”。