排序算法：冒泡排序、选择排序、插入排序的原理与C语言实现
排序，是编程里最基础也最常碰到的操作之一。我刚开始学C语言那会儿，总觉得排序不就是把数字排个序嘛，有啥难的？后来真到项目里才发现，选错排序算法，数据量一大，程序直接卡死。今天咱们就把三种最经典的排序算法——冒泡、选择、插入——彻底讲透。
一、排序算法概览
这三种排序都属于比较排序，也就是通过比较元素大小来决定顺序。它们的时间复杂度在最坏情况下都是O(n²)，但适用场景和性能表现差别很大。
核心要点：没有绝对最好的排序算法，只有最适合当前场景的排序算法。
下面这张图帮你快速建立整体认知：
二、冒泡排序
冒泡排序的思路特别直观：从头到尾，相邻两个元素比较，如果前面比后面大，就交换。这样每轮下来，最大的元素就像气泡一样"浮"到最后面。
我记得刚入行时，有个同事写冒泡排序，内层循环每次都遍历到数组末尾，白白浪费了很多比较次数。其实优化一下，每轮结束后，末尾的元素已经排好了，下一轮就不用再碰它。
代码实现
#include <stdio.h>
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 == 0) {
break;
}
}
}
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;
}我的经验：冒泡排序的优化标志位swapped很实用。我曾经在一个嵌入式项目中，数据大部分时间已经有序，加上这个标志后，排序时间从平均2ms降到了0.3ms。
三、选择排序
选择排序的思路是：每一轮从待排序的元素中选出最小的，放到已排序部分的末尾。说白了，就是"矮子里拔将军"，一轮一个。
你想想看，选择排序和冒泡排序最大的区别是什么？冒泡排序每轮可能交换很多次，而选择排序每轮只交换一次。所以虽然两者时间复杂度一样，但选择排序的实际交换次数少得多。
注意：选择排序是不稳定的排序。举个例子，数组[5a, 5b, 3]排序后，两个5的相对顺序可能改变。我曾经在排序学生成绩时踩过这个坑——相同分数的学生，顺序被打乱了。
代码实现
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;
}
}
}四、插入排序
插入排序的思路，说白了就像你打扑克牌时理牌：把新摸到的牌，插入到手中已经排好序的牌里。
我个人特别喜欢插入排序。为什么？因为它在数据基本有序的情况下，效率高得吓人，时间复杂度能降到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;
// 将比key大的元素往后移
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j--;
}
// 插入到正确位置
arr[j + 1] = key;
}
}关键理解：插入排序的核心操作是移动元素，而不是交换。移动比交换效率高，因为移动只需要一次赋值，而交换需要三次。
五、三种排序对比总结
| 算法 | 最好情况 | 最坏情况 | 平均情况 | 空间复杂度 | 稳定性 |
|---|---|---|---|---|---|
| 冒泡排序 | O(n) | O(n²) | O(n²) | O(1) | 稳定 |
| 选择排序 | O(n²) | O(n²) | O(n²) | O(1) | 不稳定 |
| 插入排序 | O(n) | O(n²) | O(n²) | O(1) | 稳定 |
六、避坑指南与实用建议
我在项目中遇到过不少排序相关的坑，这里分享几个最典型的：
- 数组越界：写冒泡排序时，内层循环条件写成
j < n - i而不是j < n - 1 - i，会导致访问越界。我曾经因为这个bug排查了整整一个下午。 - 忘记处理边界情况：当数组长度为0或1时，排序函数应该直接返回。很多新手没考虑这个，导致程序崩溃。
- 过度优化：对于小规模数据（比如几十个元素），这三种排序差别不大。我见过有人为了省几个比较次数，把代码写得极其复杂，反而降低了可读性。
我的选择建议：
- 数据量小（<50）且基本有序 → 插入排序
- 数据量小且要求稳定 → 冒泡排序
- 数据量小且交换成本高 → 选择排序
- 数据量大 → 别用这三种，上快速排序或归并排序
嗯，这三种排序算法就讲到这里。它们虽然简单，但理解透彻了，后面学更高级的排序算法会轻松很多。记住：写代码时多想想数据的特点，选对算法比写好代码更重要。
公众号:蓝海资料掘金营，微信deep3321