排序基础：从混乱到有序的工程艺术
各位同学，今天我们来聊聊排序。说实话，排序这个话题，我在刚入行时觉得它太基础了——不就是把数据排个序吗？直到后来在嵌入式项目中，因为排序算法选型不当，导致系统响应超时，我才真正意识到：排序不是简单的「排排坐」，而是一门权衡时间、空间、稳定性的工程艺术。
我个人习惯把排序比作整理书架。你想想看，同样是整理，你是随手一插（插入排序），还是两两交换（冒泡排序），或者先分堆再合并（归并排序）？不同的场景，选择完全不同。
一、排序的概念与分类
排序，说白了就是让一组数据按照某种规则（升序或降序）重新排列。但这里有几个关键概念，我建议你刻在脑子里：
- 稳定性：相等的元素在排序后，相对顺序是否保持不变。比如按成绩排序，同分的学生，原来张三在前，排序后张三还在前，这就是稳定排序。
- 内排序 vs 外排序：数据全在内存里叫内排序；数据太大需要借助磁盘，叫外排序。嵌入式开发中，绝大多数情况是内排序。
- 时间复杂度与空间复杂度：这是选型的核心指标。时间换空间，还是空间换时间？没有银弹。
核心分类：排序算法大致可以分为——插入排序（直接插入、希尔）、交换排序（冒泡、快速）、选择排序（简单选择、堆排序）、归并排序、基数排序。今天我们重点讲前两类。
二、插入排序：像打牌一样整理数据
1. 直接插入排序
直接插入排序的思路，跟你打扑克牌时理牌一模一样。你摸到一张新牌，从右往左看，找到合适的位置插进去。嗯，就是这么朴素。
我在项目中遇到过这样一个场景：一个传感器数据采集系统，每次只新增一条记录，需要保持整个数组有序。这时候直接插入排序就是最优解——因为每次只处理一个新元素，时间复杂度接近O(n)。
// 直接插入排序 —— 升序
void insertion_sort(int arr[], int n) {
int i, j, key;
for (i = 1; i < n; i++) {
key = arr[i]; // 摸到的新牌
j = i - 1;
// 从右往左找位置
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j]; // 往后挪
j--;
}
arr[j + 1] = key; // 插入
}
}我的小技巧：当数据量小于50时，直接插入排序往往比快速排序还快。因为它的常数极小，没有递归开销。别小看这个「小数据量优势」，我在做嵌入式GUI菜单排序时就用过这招。
2. 希尔排序
希尔排序是直接插入排序的「升级版」。它先把数据分成若干组，每组内做插入排序，然后逐步缩小分组，直到整个数组有序。
为什么会这样设计？你想想看，直接插入排序在数据基本有序时效率很高（接近O(n)），但数据完全乱序时就很慢。希尔排序通过「分组预排序」，让数据先变得「基本有序」，最后再做一次完整的插入排序。
// 希尔排序 —— 升序
void shell_sort(int arr[], int n) {
int gap, i, j, key;
// 初始步长取 n/2，每次减半
for (gap = n / 2; gap > 0; gap /= 2) {
// 对每个分组做插入排序
for (i = gap; i < n; i++) {
key = arr[i];
j = i - gap;
while (j >= 0 && arr[j] > key) {
arr[j + gap] = arr[j];
j -= gap;
}
arr[j + gap] = key;
}
}
}我曾经踩过的坑：希尔排序的步长选择很关键。我早期用 n/2 作为初始步长，在某个项目中数据量较大时性能很差。后来改用 Hibbard 步长（2^k - 1），性能提升了约30%。记住：步长序列不是随便选的，它直接影响时间复杂度。
三、交换排序：两两比较，该换就换
1. 冒泡排序
冒泡排序，名字很形象——就像水里的气泡，大的先浮上来。每次遍历，把最大的元素「冒」到最后面。
说实话，冒泡排序在实际工程中用得不多，因为效率确实低。但它的教学价值很高，而且在小数据量（比如几十个元素）时，代码简单、不易出错。我偶尔会在调试阶段用它来快速验证数据是否正确。
// 冒泡排序 —— 升序（带优化）
void bubble_sort(int arr[], int n) {
int i, j, temp;
int swapped; // 优化标志
for (i = 0; i < n - 1; i++) {
swapped = 0;
for (j = 0; j < n - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
swapped = 1;
}
}
// 如果没发生交换，说明已经有序
if (!swapped) break;
}
}优化要点：加上 swapped 标志后，如果某次遍历没有发生交换，说明数组已经有序，直接退出。这在数据基本有序时能大幅提升性能。我曾经在一个温度监控系统中，数据大部分时间已经有序，这个优化让排序时间从2ms降到了0.1ms。
2. 快速排序
快速排序，这才是工程界的「大杀器」。C标准库的 qsort() 用的就是它。它的核心思想是分治：选一个基准值，把小于基准的放左边，大于基准的放右边，然后递归处理左右两边。
我个人习惯把快速排序比作「选班长」——选一个人当基准，比他矮的站左边，比他高的站右边，然后两边各自再选班长。递归下去，队伍就排好了。
// 快速排序 —— 升序
int partition(int arr[], int low, int high) {
int pivot = arr[high]; // 选最后一个元素为基准
int i = low - 1;
int j, temp;
for (j = low; j < high; j++) {
if (arr[j] < pivot) {
i++;
// 交换 arr[i] 和 arr[j]
temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
// 把基准放到正确位置
temp = arr[i + 1];
arr[i + 1] = arr[high];
arr[high] = temp;
return i + 1;
}
void quick_sort(int arr[], int low, int high) {
if (low < high) {
int pi = partition(arr, low, high);
quick_sort(arr, low, pi - 1);
quick_sort(arr, pi + 1, high);
}
}避坑指南：快速排序最怕「有序数据」。如果数组已经有序，而你每次都选最后一个元素做基准，那递归深度就是n，时间复杂度退化成O(n²)。我曾经在项目中就吃过这个亏——一个已经排好序的列表，用快速排序反而比冒泡还慢。解决方案：选基准时用「三数取中法」（取首、中、尾三个元素的中间值），或者随机选基准。
四、四种排序算法对比
| 算法 | 平均时间复杂度 | 最坏时间复杂度 | 空间复杂度 | 稳定性 | 适用场景 |
|---|---|---|---|---|---|
| 直接插入排序 | O(n²) | O(n²) | O(1) | 稳定 | 小数据量（<50）、数据基本有序 |
| 希尔排序 | O(n^1.3~2) | O(n²) | O(1) | 不稳定 | 中等数据量，对稳定性无要求 |
| 冒泡排序 | O(n²) | O(n²) | O(1) | 稳定 | 教学、极少量数据 |
| 快速排序 | O(n log n) | O(n²) | O(log n) | 不稳定 | 大数据量，通用场景 |
我的选型建议：在嵌入式系统中，如果内存紧张（比如只有几KB RAM），优先选插入排序或希尔排序，因为它们空间复杂度是O(1)。如果数据量大且内存够用，快速排序是首选。记住：没有最好的算法，只有最合适的算法。
好了，排序基础就讲到这里。四种算法各有千秋，关键是要理解它们的核心思想——插入排序的「逐步构建」、希尔排序的「分组预排」、冒泡排序的「两两交换」、快速排序的「分治递归」。下次写代码时，多想想你的数据特点，选对了排序算法，程序性能能上一个台阶。