10. 数组排序算法：冒泡排序、选择排序与 qsort 函数
排序，是编程里最基础也最常用的操作之一。我刚开始学 C 语言时，总觉得排序不就是把数字排个序嘛，有什么难的？直到我在项目中处理几十万条日志数据，才发现排序算法的选择直接决定了程序是跑 1 秒还是跑 10 分钟。今天咱们就来聊聊数组排序的三种实现方式：冒泡排序、选择排序，还有 C 标准库自带的 qsort 函数。
10.1 冒泡排序：最直观的排序方法
冒泡排序的思路很简单：从左到右，两两比较相邻元素，如果顺序不对就交换。每一轮下来，最大的元素就像气泡一样「浮」到数组末尾。说白了，就是让大的数慢慢往后挪。
我在项目中遇到过一个小坑：冒泡排序虽然好理解，但数据量一大就慢得让人抓狂。有一次我处理 10 万个订单号排序，冒泡跑了快 10 秒，换成 qsort 后瞬间完成。所以冒泡适合小规模数据，比如几十个元素。
核心要点：冒泡排序的时间复杂度是 O(n²)，空间复杂度是 O(1)。稳定排序（相等元素不交换相对位置）。
#include <stdio.h>
void bubble_sort(int arr[], int n) {
int i, j, temp;
// 外层循环控制轮数
for (i = 0; i < n - 1; i++) {
// 内层循环进行两两比较
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;
}
}
}
}
int main() {
int arr[] = {64, 34, 25, 12, 22, 11, 90};
int n = sizeof(arr) / sizeof(arr[0]);
bubble_sort(arr, n);
printf("排序结果：");
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n");
return 0;
}小技巧：可以加一个标志位 flag，如果某一轮没有发生交换，说明数组已经有序，提前结束循环。我经常用这个优化，能省不少时间。
10.2 选择排序：每次挑最小的
选择排序的思路更直接：每一轮从待排序的元素中选出最小的那个，放到已排序序列的末尾。你想想看，就像打牌时你把手里的牌从小到大整理，每次挑一张最小的放到最左边。
我个人习惯在数据量不大（比如几百个）且对稳定性没要求时用选择排序。它的优点是交换次数少，最多 n-1 次交换。但缺点也很明显——不稳定，而且不管数据是否有序，都得老老实实跑完所有轮次。
核心要点：选择排序的时间复杂度也是 O(n²)，空间复杂度 O(1)。不稳定排序（相等元素可能交换位置）。
#include <stdio.h>
void selection_sort(int arr[], int n) {
int i, j, min_idx, temp;
for (i = 0; i < n - 1; i++) {
// 假设当前元素是最小值
min_idx = i;
// 在剩余元素中找真正的最小值
for (j = i + 1; j < n; j++) {
if (arr[j] < arr[min_idx]) {
min_idx = j;
}
}
// 将最小值放到正确位置
if (min_idx != i) {
temp = arr[i];
arr[i] = arr[min_idx];
arr[min_idx] = temp;
}
}
}
int main() {
int arr[] = {29, 10, 14, 37, 13};
int n = sizeof(arr) / sizeof(arr[0]);
selection_sort(arr, n);
printf("排序结果：");
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n");
return 0;
}注意：选择排序在每一轮只做一次交换，而冒泡排序可能做多次。所以当交换操作代价很大（比如交换的是大型结构体）时，选择排序反而更优。我曾经在嵌入式项目中就因为这个原因选了选择排序。
10.3 qsort 函数：C 标准库的排序利器
说实话，在实际项目中，我很少自己手写排序算法。C 标准库提供的 qsort 函数又快又稳，底层用的是快速排序（平均 O(n log n)），而且支持自定义比较规则。你只需要提供一个比较函数，剩下的交给它。
qsort 的原型在 <stdlib.h> 中：
void qsort(void *base, size_t num, size_t size,
int (*compar)(const void *, const void *));参数说明：
base：数组首地址num：元素个数size：每个元素的大小（用 sizeof 获取）compar：比较函数指针
比较函数的写法有固定套路：返回负数表示第一个参数小于第二个，返回正数表示大于，返回 0 表示相等。嗯，这里要注意，参数类型必须是 const void *，需要强制转换。
#include <stdio.h>
#include <stdlib.h>
// 比较函数：升序
int cmp_asc(const void *a, const void *b) {
return (*(int *)a - *(int *)b);
}
// 比较函数：降序
int cmp_desc(const void *a, const void *b) {
return (*(int *)b - *(int *)a);
}
int main() {
int arr[] = {45, 12, 78, 34, 23, 56, 89};
int n = sizeof(arr) / sizeof(arr[0]);
// 升序排序
qsort(arr, n, sizeof(int), cmp_asc);
printf("升序：");
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n");
// 降序排序
qsort(arr, n, sizeof(int), cmp_desc);
printf("降序：");
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n");
return 0;
}避坑指南：我曾经在比较函数里直接返回 *(int *)a - *(int *)b，结果遇到大整数相减时溢出了，导致排序结果错误。建议用 if-else 或 return (a > b) - (a < b); 这种安全写法。
10.4 三种排序方式对比
| 排序方式 | 时间复杂度 | 空间复杂度 | 稳定性 | 适用场景 |
|---|---|---|---|---|
| 冒泡排序 | O(n²) | O(1) | 稳定 | 小规模数据，教学演示 |
| 选择排序 | O(n²) | O(1) | 不稳定 | 小规模数据，交换代价高 |
| qsort | O(n log n) | O(log n) | 不稳定 | 通用场景，大规模数据 |
10.5 知识体系图
下面这张图帮你理清本章的核心逻辑：
10.6 实战建议
最后说说我的个人经验。如果你在写作业或做小工具，冒泡和选择排序完全够用，还能帮你理解算法思想。但如果你在写真正的项目——尤其是处理大量数据——请直接上 qsort。它经过了无数人的测试和优化，比自己手写的快排要可靠得多。
我曾经在一个数据采集项目中，需要排序几万个传感器读数。一开始我用冒泡，结果程序卡死。换成 qsort 后，排序时间从几秒降到了几十毫秒。从那以后，我养成了一个习惯：除非有特殊需求，否则排序一律用 qsort。
一句话总结：冒泡和选择排序是「练手」的，qsort 是「干活」的。两者都要会，但干活时选对的工具。
公众号:蓝海资料掘金营，微信deep3321