一、为什么需要非比较排序？
基于比较的排序（快排、归并、堆排）有一个理论下界：Ω(n log n)。
但如果数据满足特定条件（范围有限、均匀分布），可以突破这个下界，达到 O(n) 的线性时间。
| 算法 | 时间 | 空间 | 稳定 | 适用条件 |
|---|---|---|---|---|
| 计数排序 | O(n + k) | O(k) | ✅ | 整数，范围 k 不大 |
| 基数排序 | O(d·n) | O(n + k) | ✅ | 整数/定长字符串 |
| 桶排序 | O(n + k) 平均 | O(n + k) | ✅ | 数据均匀分布 |
k = 值域范围，d = 最大位数。
二、计数排序（Counting Sort）
2.1 思想
统计每个值出现的次数，然后按顺序输出。
2.2 模板
public void countingSort(int[] arr) {
if (arr.length <= 1) return;
int min = arr[0], max = arr[0];
for (int x : arr) { min = Math.min(min, x); max = Math.max(max, x); }
int range = max - min + 1;
int[] count = new int[range];
// 1. 计数
for (int x : arr) count[x - min]++;
// 2. 前缀和（确定每个元素的最终位置）
for (int i = 1; i < range; i++) count[i] += count[i - 1];
// 3. 逆序填充（保证稳定性）
int[] output = new int[arr.length];
for (int i = arr.length - 1; i >= 0; i--) {
int idx = --count[arr[i] - min];
output[idx] = arr[i];
}
System.arraycopy(output, 0, arr, 0, arr.length);
}- 时间：O(n + k)，空间：O(n + k)
- 稳定：✅（逆序遍历保证）
2.3 适用场景
- 学生成绩排序（0~100）
- 年龄排序（0~150）
- 字符排序（ASCII 0~127）
当 k >> n 时（如范围是 10⁹），计数排序空间爆炸，不适用。
三、基数排序（Radix Sort）
3.1 思想
将整数按位（个位、十位、百位...）分别排序，每一位使用稳定的计数排序。
Mermaid · 渲染中（下方为源码）
graph LR A[原始数组] --> B[按个位排序] B --> C[按十位排序] C --> D[按百位排序] D --> E[最终有序]
3.2 模板（LSD，从最低位开始）
public void radixSort(int[] arr) {
if (arr.length <= 1) return;
int max = arr[0];
for (int x : arr) max = Math.max(max, x);
for (int exp = 1; max / exp > 0; exp *= 10) {
countingSortByDigit(arr, exp);
}
}
private void countingSortByDigit(int[] arr, int exp) {
int n = arr.length;
int[] output = new int[n];
int[] count = new int[10]; // 0~9
for (int x : arr) count[(x / exp) % 10]++;
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]] = arr[i];
}
System.arraycopy(output, 0, arr, 0, n);
}- 时间：O(d × n)，d 为最大位数
- 空间：O(n + 10)
- 稳定：✅
3.3 LSD vs MSD
| 方式 | 方向 | 特点 |
|---|---|---|
| LSD（Least Significant Digit） | 从低位到高位 | 实现简单，适合等长数据 |
| MSD（Most Significant Digit） | 从高位到低位 | 可递归，适合变长字符串 |
3.4 处理负数
将所有数加上偏移量 offset = -min，排序后再减回：
int min = Arrays.stream(arr).min().getAsInt();
for (int i = 0; i < arr.length; i++) arr[i] -= min;
radixSort(arr); // 对非负数排序
for (int i = 0; i < arr.length; i++) arr[i] += min;四、桶排序（Bucket Sort）
4.1 思想
- 将值域分成 k 个桶。
- 将每个元素放入对应的桶。
- 桶内分别排序（插入排序/快排）。
- 按桶顺序合并。
4.2 模板
public void bucketSort(int[] arr) {
if (arr.length <= 1) return;
int min = arr[0], max = arr[0];
for (int x : arr) { min = Math.min(min, x); max = Math.max(max, x); }
int bucketCount = arr.length;
List<List<Integer>> buckets = new ArrayList<>();
for (int i = 0; i < bucketCount; i++) buckets.add(new ArrayList<>());
// 分配
for (int x : arr) {
int idx = (int)((long)(x - min) * bucketCount / (max - min + 1));
buckets.get(idx).add(x);
}
// 桶内排序 + 合并
int k = 0;
for (List<Integer> bucket : buckets) {
Collections.sort(bucket);
for (int x : bucket) arr[k++] = x;
}
}- 平均时间：O(n + k)，最坏：O(n²)（所有元素落入同一桶）
- 空间：O(n + k)
4.3 适用场景
- 数据均匀分布在某个范围
- 浮点数排序（如 [0, 1) 区间）
- 外部排序的预处理
五、排序算法全景对比
| 算法 | 平均时间 | 最坏时间 | 空间 | 稳定 | 类型 |
|---|---|---|---|---|---|
| 冒泡排序 | 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²) |
六、面试常见题
- 🟢 排序数组（各排序实现）、最大间距（桶排序/基数排序）
- 🟡 前 K 个高频元素（计数 + 桶）、H 指数
- 🟠 数组中的第 K 大元素（QuickSelect）、颜色分类（计数排序思想）
- 🔴 最小差值 II、员工空闲时间（区间排序）
七、如何选择排序算法？
Mermaid · 渲染中（下方为源码）
graph TD
Q1{数据规模?} -->|小 n<50| I[插入排序]
Q1 -->|大| Q2{需要稳定?}
Q2 -->|是| Q3{内存充足?}
Q3 -->|是| M[归并排序]
Q3 -->|否| T[TimSort]
Q2 -->|否| Q4{数据是整数且范围小?}
Q4 -->|是| C[计数/基数排序]
Q4 -->|否| Q[快速排序]
八、调试技巧
- 验证稳定性：用
(value, id)对排序，检查相同 value 的 id 顺序。 - 边界：数组为空、只有一个元素、所有元素相同。
- 计数排序范围：先求 min/max，避免数组越界。
- 基数排序位数：
max / exp > 0作为循环条件。