排序算法笔记：从冒泡到基数
排序算法大概是所有人最早接触的一组算法。它们的思路差别很大，但放在一起对照时，最容易记住的反而不是代码，而是「什么时候该用哪一个」。
性质对照
| 算法 | 平均时间 | 最坏时间 | 空间 | 稳定性 |
|---|---|---|---|---|
| 冒泡排序 | O(n²) | O(n²) | O(1) | 稳定 |
| 插入排序 | O(n²) | O(n²) | O(1) | 稳定 |
| 选择排序 | O(n²) | O(n²) | O(1) | 不稳定 |
| 计数排序 | O(n + w) | O(n + w) | O(w) | 稳定 |
| 基数排序 | O(d(n + k)) | O(d(n + k)) | O(n + k) | 稳定 |
表中 n 是元素个数，w 是值域大小，k 是每一位可能的取值数，d 是位数。前三种基于比较，逃脱不了 O(n log n) 的下界；后两种不比较元素大小，用空间换时间，在特定条件下能做得更快。
冒泡排序的 C 实现
相邻元素两两比较，把较大的一路交换到末尾。加一个「本轮是否发生过交换」的标志，可以在已经有序时提前结束。
#include <stdio.h>
void bubble_sort(int a[], int n) {
for (int i = 0; i < n - 1; i++) {
int swapped = 0;
for (int j = 0; j < n - 1 - i; j++) {
if (a[j] > a[j + 1]) {
int t = a[j];
a[j] = a[j + 1];
a[j + 1] = t;
swapped = 1;
}
}
if (!swapped) break;
}
}
int main(void) {
int a[] = {5, 2, 9, 1, 5, 6};
int n = sizeof(a) / sizeof(a[0]);
bubble_sort(a, n);
for (int i = 0; i < n; i++) printf("%d ", a[i]);
return 0;
}什么时候值得用
数据规模很小或者基本有序时，插入排序常数最小，实际跑得比复杂算法快；值域是有限的小整数时，计数排序几乎是线性的；关键字能按位拆分（比如定长整数、日期字符串）时，基数排序很合适，但它要求每一位的排序本身是稳定的。
至于冒泡排序，它现在的主要价值是教学：用最直观的方式说明「一次遍历能确定一个最终位置」这件事。