C 语言综合练习六：三种基础排序
更新时间：2026-08-26。本文是
languages/c/主题入门层第 77 篇。排序是数据结构的第一课，也是面试常客。本篇用 C 实现冒泡、选择、插入三种 O(n²) 排序，对比它们的行为差异，最后看标准库qsort如何一行搞定。三种算法代码量都不大，但"交换、比较、移动"的细微差别，写一遍才能真正懂。代码已入库demos/c-beginner-practice/sorting.c。
本文要回答的问题
- 三种排序各自怎么走？代码差别在哪？
- 谁最快？什么场景用哪个？
- 生产环境为什么直接 qsort？
一、冒泡排序
相邻两两比较，大的往后冒：
c
void bubble_sort(int *a, int n) {
for (int i = 0; i < n - 1; i++) {
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;
}
}
}
}特点：比较相邻元素、交换频繁；每轮把当前最大值送到末尾。
二、选择排序
每轮找剩余部分的最小值，放到前面：
c
void selection_sort(int *a, int n) {
for (int i = 0; i < n - 1; i++) {
int min_idx = i;
for (int j = i + 1; j < n; j++) {
if (a[j] < a[min_idx]) min_idx = j;
}
/* 把最小值交换到位置 i */
int t = a[i]; a[i] = a[min_idx]; a[min_idx] = t;
}
}特点：交换次数少（每轮最多 1 次），比较次数不变。
三、插入排序
像整理扑克牌：把每个元素插到已排好部分的位置：
c
void insertion_sort(int *a, int n) {
for (int i = 1; i < n; i++) {
int key = a[i];
int j = i - 1;
while (j >= 0 && a[j] > key) {
a[j + 1] = a[j]; // 后移腾位置
j--;
}
a[j + 1] = key; // 插入
}
}特点：对近似有序的数组极快（接近 O(n)）；元素移动而非交换。
四、运行与对比
c
#include <stdio.h>
void print_array(const int *a, int n) {
for (int i = 0; i < n; i++) printf("%d ", a[i]);
printf("\n");
}
int main(void) {
int a1[] = {5, 2, 8, 1, 9, 3};
int a2[] = {5, 2, 8, 1, 9, 3};
int a3[] = {5, 2, 8, 1, 9, 3};
int n = 6;
bubble_sort(a1, n); print_array(a1, n); // 1 2 3 5 8 9
selection_sort(a2, n); print_array(a2, n); // 1 2 3 5 8 9
insertion_sort(a3, n); print_array(a3, n); // 1 2 3 5 8 9
return 0;
}| 排序 | 比较次数（最坏） | 交换/移动 | 适合 |
|---|---|---|---|
| 冒泡 | O(n²) | 最多（交换频繁） | 教学 |
| 选择 | O(n²) | 最少（每轮 1 次） | 交换代价高时 |
| 插入 | O(n²) | 移动为主 | 近似有序 |
三者平均/最坏都是 O(n²)，但常数和行为不同。n 到几万以上就该换 O(n log n) 的算法。
五、生产环境：qsort
c
#include <stdlib.h>
int cmp_int(const void *a, const void *b) {
int x = *(const int *)a, y = *(const int *)b;
return (x > y) - (x < y);
}
int arr[] = {5, 2, 8, 1, 9};
qsort(arr, 5, sizeof(int), cmp_int); // O(n log n)，标准库实现工程结论：自己手写 O(n²) 排序只用于学习/小数据；生产环境用 qsort（内部是快速排序等 O(n log n)）。细节见stdlib.h。
六、扩展练习
- 加
-r反向排序（比较函数反转）； - 给结构体按字段排序（学生按成绩，见学生管理系统）；
- 归并/快排的递归实现（进阶）。
七、一句话总结
c
/*
* sorting.c —— C 语言入门综合练习六：三种基础排序
* 文档: languages/c/beginner/77-practice-sorting.md
* 编译: make && ./sorting
*/
#include <stdio.h>
#include <stdlib.h>
/* 冒泡排序：相邻两两比较，大的往后冒 */
void bubble_sort(int *a, int n) {
for (int i = 0; i < n - 1; i++) {
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;
}
}
}
}
/* 选择排序：每轮找剩余最小值放到前面 */
void selection_sort(int *a, int n) {
for (int i = 0; i < n - 1; i++) {
int min_idx = i;
for (int j = i + 1; j < n; j++) {
if (a[j] < a[min_idx]) min_idx = j;
}
int t = a[i]; a[i] = a[min_idx]; a[min_idx] = t;
}
}
/* 插入排序：把元素插到已排好部分 */
void insertion_sort(int *a, int n) {
for (int i = 1; i < n; i++) {
int key = a[i];
int j = i - 1;
while (j >= 0 && a[j] > key) {
a[j + 1] = a[j]; /* 后移腾位置 */
j--;
}
a[j + 1] = key; /* 插入 */
}
}
int cmp_int(const void *a, const void *b) {
int x = *(const int *)a, y = *(const int *)b;
return (x > y) - (x < y);
}
void print_array(const int *a, int n) {
for (int i = 0; i < n; i++) printf("%d ", a[i]);
printf("\n");
}
int main(void) {
int a1[] = {5, 2, 8, 1, 9, 3};
int a2[] = {5, 2, 8, 1, 9, 3};
int a3[] = {5, 2, 8, 1, 9, 3};
int a4[] = {5, 2, 8, 1, 9, 3};
int n = 6;
bubble_sort(a1, n); printf("bubble: "); print_array(a1, n);
selection_sort(a2, n); printf("selection:"); print_array(a2, n);
insertion_sort(a3, n); printf("insertion:"); print_array(a3, n);
qsort(a4, n, sizeof(int), cmp_int);
printf("qsort: "); print_array(a4, n);
return 0;
}