排序大概是编程里最"老少咸宜"的算法主题:入门时用它理解循环和交换,进阶时用它理解递归和分治,面试时它又是最高频的考点之一。这篇文章我们用 C 语言从零实现冒泡、选择、插入、快排、归并五种经典排序,每段代码都能直接编译运行,最后再写一个计时器让它们同场竞技,亲眼看看 O(n²) 和 O(n log n) 的差距到底有多大。
1. 先备好两个工具
所有排序都要交换元素,先写一个 swap 函数;为了验证结果,再写一个打印数组的函数。注意 swap 必须传指针,否则只是交换了副本,数组纹丝不动——这是新手最容易踩的坑。
#include <stdio.h>
void swap(int *a, int *b) {
int t = *a;
*a = *b;
*b = t;
}
void print_array(int arr[], int n) {
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n");
}C 语言的数组参数会自动退化成指针,所以 int arr[] 和 int *arr 在形参里是等价的,函数内部对 arr[i] 的修改会直接作用到外面的数组。数组长度没法在函数里用 sizeof 拿到,必须由调用者传进来,这也是所有排序函数都带 int n 参数的原因。
2. 冒泡排序:让最大的泡泡浮上去
冒泡排序的思路很直白:每一轮从左到右扫描,相邻两个元素如果顺序不对就交换,这样一轮下来最大的元素就像泡泡一样"浮"到末尾。下一轮的范围缩小一格,重复 n-1 轮就排好了。
void bubble_sort(int arr[], int n) {
for (int i = 0; i < n - 1; i++) {
int swapped = 0; /* 本轮有没有发生交换 */
for (int j = 0; j < n - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
swap(&arr[j], &arr[j + 1]);
swapped = 1;
}
}
if (!swapped) {
break; /* 一轮没交换 = 已经有序 */
}
}
}内层循环的边界 n - 1 - i 很关键:每完成一轮,末尾就多一个已就位的最大元素,不需要再碰它。加一个 swapped 标志是冒泡的经典优化——如果某一轮完全没有交换,说明数组已经有序,提前结束,这时最好情况退化成 O(n)。
3. 选择排序与插入排序
选择排序的思路是"每次挑最小的放前面":第 i 轮在 [i, n) 区间里找到最小元素的下标,和位置 i 交换。它最大的特点是不管数据长什么样,比较次数永远是 n(n-1)/2 次,稳定 O(n²)。
void selection_sort(int arr[], int n) {
for (int i = 0; i < n - 1; i++) {
int min_idx = i;
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[min_idx]) {
min_idx = j;
}
}
if (min_idx != i) {
swap(&arr[i], &arr[min_idx]);
}
}
}插入排序则像整理扑克牌:把当前这张牌往左边已经排好的序列里插,比它大的牌依次右移一位给它腾地方。它对"基本有序"的数据非常友好,也常被用作快排在小数组时的兜底策略。
void insertion_sort(int arr[], int n) {
for (int i = 1; i < n; i++) {
int key = arr[i];
int j = i - 1;
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j]; /* 右移腾位 */
j--;
}
arr[j + 1] = key;
}
}插入排序有个隐藏优点:稳定——相等的元素不会交换相对顺序,这在按多个字段排序时很重要。它和选择排序同为 O(n²),但插入排序的交换(移动)次数往往远少于选择排序,实际跑起来通常更快。
4. 快速排序:分而治之
快排是实践中用得最多的排序:选一个"基准"(pivot),把比它小的都放左边、比它大的都放右边,然后递归地对左右两半重复这个过程。下面用 Lomuto 分区法,选最后一个元素当基准。
int partition(int arr[], int low, int high) {
int pivot = arr[high];
int i = low - 1; /* i 左边都是 <= pivot 的 */
for (int j = low; j < high; j++) {
if (arr[j] < pivot) {
i++;
swap(&arr[i], &arr[j]);
}
}
swap(&arr[i + 1], &arr[high]); /* 基准归位 */
return i + 1;
}
void quick_sort(int arr[], int low, int high) {
if (low < high) {
int p = partition(arr, low, high);
quick_sort(arr, low, p - 1);
quick_sort(arr, p + 1, high);
}
}分区是快排的灵魂:i 指针始终指向"已确定小于基准"的最后一个位置,扫描指针 j 每遇到一个小于基准的元素,就把它换到 i+1 处。扫描结束后基准元素已经在正确位置,且它左边的都小于它、右边的都大于它,接下来递归处理两边即可。要小心:如果输入本身有序而基准总选最后一个,快排会退化成 O(n²) 并且递归深度达到 n 可能爆栈,工程上常用"三数取中"来选基准规避这个问题。
5. 归并排序:先拆再合
归并排序同样用分治,但它"无脑对半分,合并时保证有序":先把数组拆到只剩一个元素(天然有序),再两两合并。合并过程需要一块临时空间,所以它是空间换时间的典型——稳定且任何情况都是 O(n log n)。
#include <stdlib.h>
void merge(int arr[], int left, int mid, int right) {
int n1 = mid - left + 1;
int n2 = right - mid;
int *L = (int *)malloc(n1 * sizeof(int));
int *R = (int *)malloc(n2 * sizeof(int));
for (int i = 0; i < n1; i++) L[i] = arr[left + i];
for (int j = 0; j < n2; j++) R[j] = arr[mid + 1 + j];
int i = 0, j = 0, k = left;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) arr[k++] = L[i++];
else arr[k++] = R[j++];
}
while (i < n1) arr[k++] = L[i++];
while (j < n2) arr[k++] = R[j++];
free(L);
free(R);
}
void merge_sort(int arr[], int left, int right) {
if (left >= right) return;
int mid = left + (right - left) / 2;
merge_sort(arr, left, mid);
merge_sort(arr, mid + 1, right);
merge(arr, left, mid, right);
}合并时用 <= 而不是 < 是为了保证稳定性:左边相等元素先入列,相对顺序不变。注意 mid 用 left + (right - left) / 2 而不是 (left + right) / 2,后者在 left+right 很大时可能溢出。临时数组用 malloc 申请、用完 free,避免在递归里反复分配,更高效的做法是只分配一次缓冲区,通过下标复用。
6. 同场竞技:跑分对比
光看复杂度不如亲手跑一次。下面的程序生成 20000 个随机数,分别用五种排序跑一遍并计时。把前面所有排序函数粘贴到 main 之前,用 gcc sorting.c -O2 -o sort 编译运行。
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
/* 前面五种排序函数都放到这里 */
int main(void) {
const int N = 20000;
int *base = (int *)malloc(N * sizeof(int));
int *tmp = (int *)malloc(N * sizeof(int));
clock_t start, end;
srand((unsigned)time(NULL));
for (int i = 0; i < N; i++) {
base[i] = rand() % 1000000;
}
memcpy(tmp, base, N * sizeof(int));
start = clock();
bubble_sort(tmp, N);
end = clock();
printf("bubble: %.3f s\n", (double)(end - start) / CLOCKS_PER_SEC);
memcpy(tmp, base, N * sizeof(int));
start = clock();
selection_sort(tmp, N);
end = clock();
printf("selection: %.3f s\n", (double)(end - start) / CLOCKS_PER_SEC);
memcpy(tmp, base, N * sizeof(int));
start = clock();
insertion_sort(tmp, N);
end = clock();
printf("insertion: %.3f s\n", (double)(end - start) / CLOCKS_PER_SEC);
memcpy(tmp, base, N * sizeof(int));
start = clock();
quick_sort(tmp, 0, N - 1);
end = clock();
printf("quick: %.3f s\n", (double)(end - start) / CLOCKS_PER_SEC);
memcpy(tmp, base, N * sizeof(int));
start = clock();
merge_sort(tmp, 0, N - 1);
end = clock();
printf("merge: %.3f s\n", (double)(end - start) / CLOCKS_PER_SEC);
free(base);
free(tmp);
return 0;
}关键细节:每次排序前都用 memcpy 从 base 复制一份完全相同的数组,保证五个选手面对的是同一份数据,结果才公平。在我的机器上冒泡大约 1 秒多,选择和插入零点几秒,快排和归并只有几毫秒——当数据量翻倍,这个差距会指数级拉大。
7. 复杂度对比
| 算法 | 最好 | 平均 | 最坏 | 额外空间 | 稳定 |
|---|---|---|---|---|---|
| 冒泡 | O(n) | O(n²) | O(n²) | O(1) | 是 |
| 选择 | O(n²) | O(n²) | O(n²) | O(1) | 否 |
| 插入 | O(n) | O(n²) | O(n²) | O(1) | 是 |
| 快排 | O(n log n) | O(n log n) | O(n²) | O(log n) | 否 |
| 归并 | O(n log n) | O(n log n) | O(n log n) | O(n) | 是 |
看懂这张表你就知道怎么选:数据量小或者基本有序,插入排序最实用;追求平均速度且不要求稳定,快排是默认答案;要求稳定或数据存储在链表上,归并排序更合适。顺便说一句,标准库的 qsort 就是快排的工业级实现,自己写完这些算法后,记得学会用它。
8. 总结与练习
五种排序看似多,其实就两类思路:一类是"挨个比较交换"的 O(n²) 家族(冒泡、选择、插入),一类是"分治递归"的 O(n log n) 家族(快排、归并)。理解它们的关键是抓住每个算法的核心不变量:冒泡的"末尾已就位"、选择的"前缀已最小"、插入的"左侧已有序"、快排的"基准已归位"、归并的"子序列已有序"。
练习建议:
- 把选择排序改成"每次挑最大放末尾",验证结果仍然正确;
- 给快排加"三数取中"选基准,然后对一组完全有序的输入测试,观察它不再退化;
- 把 N 从 20000 改成 100000 再跑一遍计时,记录五种算法的时间,亲手验证 O(n²) 与 O(n log n) 的差距。
💡 学习排序的终极心法:不要背代码,而是背"每一轮之后数组处于什么状态"。能准确说出任何时刻数组的样子,你才算真正理解了这个算法。