34、排序算法（一）：冒泡排序、选择排序、插入排序——原理、实现与时间复杂度分析
排序，是编程里最基础也最常碰到的操作之一。我刚开始学C语言那会儿，觉得排序不就是把数字排个序嘛，有啥难的？后来在项目中处理百万级数据时才发现，选错排序算法，程序能慢到让你怀疑人生。今天咱们就来聊聊三种最经典的排序算法：冒泡、选择和插入。
这三种算法，说白了就是排序界的“三原色”。你搞懂了它们，后面再学快排、归并什么的，就会轻松很多。而且面试时，面试官特别喜欢让你手写这些算法，再问一句“时间复杂度是多少？”——嗯，咱们今天就把它彻底讲透。
核心要点：这三种排序都属于“比较排序”，时间复杂度都是 O(n²)。但它们的实际表现和适用场景，差别还挺大的。
冒泡排序：最直观的“泡泡”
冒泡排序的原理，你想想看，就像水里的气泡一样——轻的往上浮，重的往下沉。在数组里，我们让大的元素慢慢“冒”到数组末尾。
具体怎么做呢？从数组第一个元素开始，依次比较相邻的两个元素。如果前一个比后一个大，就交换它们。这样一轮下来，最大的元素就“冒”到最后了。然后重复这个过程，只是每轮少处理一个元素（因为末尾已经排好了）。
void bubble_sort(int arr[], int n) {
for (int i = 0; i < n - 1; i++) {
// 每轮比较 n-1-i 次
for (int j = 0; j < n - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
// 交换相邻元素
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}优化小技巧：加一个标志位。如果某一轮没有发生任何交换，说明数组已经有序了，直接跳出循环。我在项目中处理近乎有序的数据时，这个优化能让冒泡排序跑得飞快。
void bubble_sort_optimized(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]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
swapped = 1;
}
}
if (!swapped) break; // 没交换，提前结束
}
}时间复杂度分析：
- 最好情况（数组已有序）：O(n) —— 优化后只需一轮比较
- 最坏情况（数组逆序）：O(n²) —— 每轮都要交换
- 平均情况：O(n²)
空间复杂度是 O(1)，因为只用了几个临时变量。冒泡排序是稳定的——相等元素不会交换相对位置。
选择排序：简单粗暴的“选秀”
选择排序的思路更直接：每一轮从待排序的元素中，选出最小的那个，放到已排序序列的末尾。说白了，就是“矮子里拔将军”，一轮拔一个。
我刚开始写代码时，觉得选择排序比冒泡好理解。但后来发现一个坑——它是不稳定的。举个例子，数组 [5a, 5b, 3]，第一轮会把 3 和 5a 交换，结果变成 [3, 5b, 5a]，两个 5 的相对顺序变了。这在某些场景下会出问题。
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) {
int temp = arr[i];
arr[i] = arr[min_idx];
arr[min_idx] = temp;
}
}
}时间复杂度分析：
- 最好情况：O(n²) —— 即使数组已有序，也要比较 n²/2 次
- 最坏情况：O(n²)
- 平均情况：O(n²)
注意：选择排序的交换次数很少，最多 n-1 次。如果交换元素的代价很大（比如交换的是大型结构体），选择排序反而有优势。我曾经在嵌入式项目中，因为交换结构体开销大，特意选了选择排序。
插入排序：像整理扑克牌
插入排序，你想想看，就像你打扑克时整理手牌——摸到一张新牌，把它插到手里已经排好序的牌中合适的位置。
具体到数组里，我们把数组分成两部分：左边是已排序的，右边是未排序的。每次从右边取一个元素，在左边找到合适的位置插入。插入时，需要把比它大的元素都往后挪一位。
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) —— 只需比较 n-1 次，无需移动
- 最坏情况（数组逆序）：O(n²) —— 每次都要挪动所有已排序元素
- 平均情况：O(n²)
我的经验：插入排序在处理“几乎有序”的数据时，表现非常好。实际项目中，很多数据都是部分有序的，这时候插入排序比冒泡和选择都快。而且它是稳定的，这也是一个加分项。
三种排序对比
| 特性 | 冒泡排序 | 选择排序 | 插入排序 |
|---|---|---|---|
| 最好时间复杂度 | O(n) | O(n²) | O(n) |
| 最坏时间复杂度 | O(n²) | O(n²) | O(n²) |
| 平均时间复杂度 | O(n²) | O(n²) | O(n²) |
| 空间复杂度 | O(1) | O(1) | O(1) |
| 稳定性 | 稳定 | 不稳定 | 稳定 |
| 交换次数 | 多（O(n²)） | 少（O(n)） | 中等（O(n²)） |
| 对有序数据友好 | 是（优化后） | 否 | 是 |
实际应用中的选择
这三种排序，时间复杂度都是 O(n²)，所以数据量大的时候（比如超过 1000 个元素），基本不会用它们。但它们的价值在于：
- 教学意义：它们是理解更复杂排序算法的基础
- 小规模数据：数据量小于 50 时，插入排序的实际表现甚至比快排还好
- 混合排序：很多高级排序（如快排、归并排序）在数据量小的时候，会切换到插入排序
一句话总结：数据基本有序，用插入排序；数据量小且不在意稳定性，用选择排序；想写代码简单且数据量极小，用冒泡排序。但说实话，实际项目中我用的最多的是插入排序——因为它对“几乎有序”的数据太友好了。
嗯，这三种排序就讲到这里。记住它们的原理、代码实现和时间复杂度，面试时手写排序算法，基本不会翻车。下一章咱们聊更快的排序算法——希尔排序和快速排序，那才是真正拉开差距的地方。