排序算法 — 从冒泡到快排
C语言学习教程
排序算法 — 从冒泡到快排
排序是计算机科学中最基础的操作之一。你将学到五种经典排序算法，理解它们的思路、实现和适用场景。
为什么需要学排序？
你可能想问：C 标准库不是有 qsort 吗，为什么还要手写排序？
原因有三：
- 面试必考：排序是最常见的算法面试题
- 理解思想：分治、递归、双指针等核心算法思想都在排序中体现
- 实际问题：有时候你需要对自定义结构排序，或者在不分配额外内存的场景下排序
五种排序算法全景
┌──────────────────────────────────────────────────────────────────────┐
│ 五种排序算法对比 │
├──────────┬──────────┬──────────┬──────────┬──────────┬───────────────┤
│ 算法 │ 最好 │ 平均 │ 最坏 │ 空间 │ 稳定？ │
├──────────┼──────────┼──────────┼──────────┼──────────┼───────────────┤
│ 冒泡排序 │ 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(nlogn) │ O(nlogn) │ O(n²) │ O(logn) │ 否 ✗ │
│ 归并排序 │ O(nlogn) │ O(nlogn) │ O(nlogn) │ O(n) │ 是 ✓ │
└──────────┴──────────┴──────────┴──────────┴──────────┴───────────────┘
稳定 = 相等的元素保持原来的相对顺序不变基础知识：时间复杂度怎么算？
大 O 表示法描述的是”当数据量 n 趋向无穷大时，操作次数增长的趋势”。常数项和低阶项都被忽略。
例子：冒泡排序的比较次数 = n(n-1)/2
当 n=100：比较 4950 次
当 n=1000：比较 499500 次
当 n=10000：比较 49995000 次
n 每增大 10 倍 → 约增大 100 倍 → O(n²)常见复杂度直观感受：
n = 1,000,000 (100 万) 时
┌──────────────┬───────────────────┐
│ O(log n) │ ~20 次 │ ← 二分查找级别
│ O(n) │ 1,000,000 次 │ ← 线性遍历
│ O(n log n) │ ~20,000,000 次 │ ← 快排/归并
│ O(n²) │ 1,000,000,000,000 │ ← 冒泡/选择/插入
└──────────────┴───────────────────┘算法一：冒泡排序（Bubble Sort）
思路：像气泡从水底浮到水面一样，每轮把当前最大的元素”冒”到最后。
逐步可视化
初始数组：[5, 3, 8, 1, 2]
第1轮（把最大值8"冒"到最后）：
┌───┬───┬───┬───┬───┐
│ 5 │ 3 │ 8 │ 1 │ 2 │ 比较 5 和 3 → 5>3 → 交换
└───┴───┴───┴───┴───┘
↓
┌───┬───┬───┬───┬───┐
│ 3 │ 5 │ 8 │ 1 │ 2 │ 比较 5 和 8 → 5<8 → 不动
└───┴───┴───┴───┴───┘
↓
┌───┬───┬───┬───┬───┐
│ 3 │ 5 │ 8 │ 1 │ 2 │ 比较 8 和 1 → 8>1 → 交换
└───┴───┴───┴───┴───┘
↓
┌───┬───┬───┬───┬───┐
│ 3 │ 5 │ 1 │ 8 │ 2 │ 比较 8 和 2 → 8>2 → 交换
└───┴───┴───┴───┴───┘
↓
┌───┬───┬───┬───┬───┐
│ 3 │ 5 │ 1 │ 2 │ 8 │ ← 8 到达最终位置 ✓
└───┴───┴───┴───┴───┘
第2轮（把 5 "冒"到倒数第二）：
┌───┬───┬───┬───┬───┐
│ 3 │ 5 │ 1 │ 2 │ 8 │ 比较 3 和 5 → 不动
└───┴───┴───┴───┴───┘
↓
┌───┬───┬───┬───┬───┐
│ 3 │ 5 │ 1 │ 2 │ 8 │ 比较 5 和 1 → 交换
└───┴───┴───┴───┴───┘
↓
┌───┬───┬───┬───┬───┐
│ 3 │ 1 │ 5 │ 2 │ 8 │ 比较 5 和 2 → 交换
└───┴───┴───┴───┴───┘
↓
┌───┬───┬───┬───┬───┐
│ 3 │ 1 │ 2 │ 5 │ 8 │ ← 5 到达最终位置 ✓ (8已就位，不参与比较)
└───┴───┴───┴───┴───┘
第3轮：
┌───┬───┬───┬───┬───┐
│ 3 │ 1 │ 2 │ 5 │ 8 │ → ┌───┬───┬───┬───┬───┐
└───┴───┴───┴───┴───┘ │ 1 │ 3 │ 2 │ 5 │ 8 │ → ┌───┬───┬───┬───┬───┐
└───┴───┴───┴───┴───┘ │ 1 │ 2 │ 3 │ 5 │ 8 │
└───┴───┴───┴───┴───┘
第4轮：确认 1,2,3 已有序，排序完成。基础实现
void bubble_sort(int arr[], int n) {
for (int i = 0; i < n - 1; i++) {
// 每轮把第 n-1-i 大的元素放到 arr[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)（只遍历一轮）适用场景： 教学入门、极小的数组（n < 50）、需要稳定性且数据量小。
算法二：选择排序（Selection Sort）
思路：每轮找到未排序部分中的最小元素，放到已排序部分的末尾。
逐步可视化
初始数组：[64, 25, 12, 22, 11]
第1轮：在 [64, 25, 12, 22, 11] 中找最小 → 11 (位置4)
把 11 和 64 交换：
┌────┬────┬────┬────┬────┐
│ 11 │ 25 │ 12 │ 22 │ 64 │ ← 11 就位 ✓
└────┴────┴────┴────┴────┘
第2轮：在 [25, 12, 22, 64] 中找最小 → 12 (位置2)
把 12 和 25 交换：
┌────┬────┬────┬────┬────┐
│ 11 │ 12 │ 25 │ 22 │ 64 │ ← 12 就位 ✓
└────┴────┴────┴────┴────┘
第3轮：在 [25, 22, 64] 中找最小 → 22 (位置3)
把 22 和 25 交换：
┌────┬────┬────┬────┬────┐
│ 11 │ 12 │ 22 │ 25 │ 64 │ ← 22 就位 ✓
└────┴────┴────┴────┴────┘
第4轮：在 [25, 64] 中找最小 → 25 (位置3，恰好不需交换)
┌────┬────┬────┬────┬────┐
│ 11 │ 12 │ 22 │ 25 │ 64 │ ← 全部就位！
└────┴────┴────┴────┴────┘实现
void selection_sort(int arr[], int n) {
for (int i = 0; i < n - 1; i++) {
// 在 arr[i..n-1] 中找最小元素的位置
int min_idx = i;
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[min_idx]) {
min_idx = j;
}
}
// 把最小元素交换到位置 i
if (min_idx != i) {
int temp = arr[i];
arr[i] = arr[min_idx];
arr[min_idx] = temp;
}
}
}特点： 无论数据如何，始终做 n(n-1)/2 次比较（总是 O(n²)），但交换次数最少（最多 n-1 次交换）。
适用场景： 交换成本很高（如排序大结构体）、只需要前 k 个最小的元素。
算法三：插入排序（Insertion Sort）
思路：像打扑克牌时整理手牌——每次拿一张新牌，插入到已经排好序的牌中。
逐步可视化
想象你在整理一手扑克牌：
已有的手牌（有序） 新抽到的牌
↓ ↓
┌───┐ ┌───┐
│ 3 │ 7 │ 9 │ │ 5 │ ← 把 5 插入到 3 和 7 之间
└───┘ └───┘
插入过程（从右往左比较）：
┌───┬───┬───┬───┐
│ 3 │ 7 │ 9 │ │ 5 < 9 → 9 右移 → ┌───┬───┬───┬───┐
└───┴───┴───┴───┘ │ 3 │ 7 │ │ 9 │
└───┴───┴───┴───┘
5 < 7 → 7 右移 → ┌───┬───┬───┬───┐
│ 3 │ │ 7 │ 9 │
└───┴───┴───┴───┘
5 > 3 → 插入在 3 后面 → ┌───┬───┬───┬───┐
│ 3 │ 5 │ 7 │ 9 │ ← 有序！
└───┴───┴───┴───┘
完整排序过程：
初始: [5, 2, 4, 6, 1, 3]
i=1: [5 | 2, 4, 6, 1, 3] 2<5 → 5右移 → [2, 5 | 4, 6, 1, 3]
i=2: [2, 5 | 4, 6, 1, 3] 4<5 → 5右移, 4>2 → [2, 4, 5 | 6, 1, 3]
i=3: [2, 4, 5 | 6, 1, 3] 6>5 → 不动 → [2, 4, 5, 6 | 1, 3]
i=4: [2, 4, 5, 6 | 1, 3] 1<6,1<5,1<4,1<2 → 全部右移 → [1, 2, 4, 5, 6 | 3]
i=5: [1, 2, 4, 5, 6 | 3] 3<6,3<5,3<4,3>2 → [1, 2, 3, 4, 5, 6]实现
void insertion_sort(int arr[], int n) {
for (int i = 1; i < n; i++) {
int key = arr[i]; // 当前要插入的"牌"
int j = i - 1;
// 在 arr[0..i-1] 中找到 key 的插入位置
// 比 key 大的元素都向右移动一格
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j]; // 右移
j--;
}
arr[j + 1] = key; // 插入到正确位置
}
}最好情况： 数组已经有序 → O(n)（每轮只比较一次，不需要移动） 最坏情况： 数组逆序 → O(n²) 关键优势： 在几乎有序的数组上表现极好
适用场景： 数据量小（n < 100）、数据几乎有序、在线排序（数据逐个到达）、作为快排的小数组”底”。
算法四：快速排序（Quick Sort）— 最常用的通用排序
思路：分治法。选一个”基准值”（pivot），把数组分为”小于 pivot”和”大于 pivot”两部分，然后递归排序这两部分。
核心操作：分区（Partition）
分区是快排的灵魂。选最后一个元素作为 pivot，用两个指针把数组分成三区。
分区过程详解（Lomuto 分区方案）：
初始：[..., ..., ..., ..., pivot]
↑
arr[high]
目标：找到 pivot 的正确位置，使得：
[小于 pivot 的] [pivot] [大于 pivot 的]
i = low - 1 (指向"小于区"的右边界)
j 遍历数组
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
例：[3, 7, 1, 8, 2, 5]，pivot = 5 (最后一个)
初始状态：
[3, 7, 1, 8, 2, 5]
↑ ↑
i=-1 pivot=5
j=0: arr[0]=3 < 5 → i++ → i=0 → 交换 arr[0]和arr[0] → 不变
[3, 7, 1, 8, 2, 5]
↑i ↑pivot
j=1: arr[1]=7 > 5 → 不动
[3, 7, 1, 8, 2, 5]
↑i ↑pivot
j=2: arr[2]=1 < 5 → i++ → i=1 → 交换 arr[1]⇔arr[2]
[3, 1, 7, 8, 2, 5]
↑i ↑pivot
j=3: arr[3]=8 > 5 → 不动
[3, 1, 7, 8, 2, 5]
↑i ↑pivot
j=4: arr[4]=2 < 5 → i++ → i=2 → 交换 arr[2]⇔arr[4]
[3, 1, 2, 8, 7, 5]
↑i ↑pivot
遍历结束，把 pivot 放到 i+1 位置（arr[3]=8 的位置）：
交换 arr[3]⇔arr[5]:
[3, 1, 2, 5, 7, 8]
↑i+1
分区完成！
[3,1,2] < 5 < [7,8] ← 左半区都小于5，右半区都大于5
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━完整递归过程
[3, 7, 1, 8, 2, 5]
│
分区: pivot=5
┌───────────┴───────────┐
[3, 1, 2] 5 [7, 8]
│ │
分区: pivot=2 分区: pivot=8
┌─────┴─────┐ ┌─────┴─────┐
[1] 2 [3] [7] 8 []
│ │ │
返回 返回 返回
│ │
└───────────┬───────────┘
↓
[1, 2, 3, 5, 7, 8] 排序完成基础实现
// 分区函数：返回 pivot 的最终位置
int partition(int arr[], int low, int high) {
int pivot = arr[high]; // 选最后一个元素作为基准
int i = low - 1; // "小于区"的右边界
for (int j = low; j < high; j++) {
if (arr[j] < pivot) {
i++; // 扩展"小于区"
// 交换 arr[i] 和 arr[j]
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
// 把 pivot 放到正确位置（i+1）
int temp = arr[i + 1];
arr[i + 1] = arr[high];
arr[high] = temp;
return i + 1; // pivot 的最终位置
}
void quick_sort(int arr[], int low, int high) {
if (low >= high) return; // 0或1个元素 → 已经有序
int pi = partition(arr, low, high); // 分区
quick_sort(arr, low, pi - 1); // 排序左半区
quick_sort(arr, pi + 1, high); // 排序右半区
}优化版：三数取中 + 小数组切换插入排序
// 三数取中：避免在已排序/逆序数组上退化到 O(n²)
int median_of_three(int arr[], int low, int high) {
int mid = low + (high - low) / 2;
if (arr[low] > arr[mid]) {
int t = arr[low]; arr[low] = arr[mid]; arr[mid] = t;
}
if (arr[low] > arr[high]) {
int t = arr[low]; arr[low] = arr[high]; arr[high] = t;
}
if (arr[mid] > arr[high]) {
int t = arr[mid]; arr[mid] = arr[high]; arr[high] = t;
}
// 现在 arr[mid] 是中间值，放到 high-1 位置作为 pivot
int t = arr[mid];
arr[mid] = arr[high - 1];
arr[high - 1] = t;
return arr[high - 1];
}
void insertion_sort_range(int arr[], int low, int high) {
for (int i = low + 1; i <= high; i++) {
int key = arr[i];
int j = i - 1;
while (j >= low && arr[j] > key) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
}
}
#define INSERTION_THRESHOLD 10
void quick_sort_optimized(int arr[], int low, int high) {
// 小数组直接用插入排序（减少递归开销）
if (high - low < INSERTION_THRESHOLD) {
insertion_sort_range(arr, low, high);
return;
}
if (low >= high) return;
// 三数取中选 pivot，放到 high-1
median_of_three(arr, low, high);
// partition 使用 high-1 作为 pivot
// ... (与基础版本类似，但使用 high-1 而不是 high)
int pi = partition(arr, low, high);
quick_sort_optimized(arr, low, pi - 1);
quick_sort_optimized(arr, pi + 1, high);
}适用场景： 通用排序的首选、大数组、需要原地排序。
算法五：归并排序（Merge Sort）
思路：也是分治法。把数组分成两半，分别排序，然后合并两个有序数组。
合并过程可视化
假设左右两半已经有序：
左: [2, 5, 8] 右: [1, 3, 7, 9]
合并过程（双指针）：
┌───┬───┬───┐ ┌───┬───┬───┬───┐
│ 2 │ 5 │ 8 │ │ 1 │ 3 │ 7 │ 9 │
└───┴───┴───┘ └───┴───┴───┴───┘
↑L ↑R
比较 2 和 1 → 1 更小 → 放入结果，R++
结果: [1]
┌───┬───┬───┐ ┌───┬───┬───┬───┐
│ 2 │ 5 │ 8 │ │ . │ 3 │ 7 │ 9 │
└───┴───┴───┘ └───┴───┴───┴───┘
↑L ↑R
比较 2 和 3 → 2 更小 → 放入结果，L++
结果: [1, 2]
┌───┬───┬───┐ ┌───┬───┬───┬───┐
│ . │ 5 │ 8 │ │ . │ 3 │ 7 │ 9 │
└───┴───┴───┘ └───┴───┴───┴───┘
↑L ↑R
比较 5 和 3 → 3 更小 → 放入结果，R++
结果: [1, 2, 3]
...
最终结果: [1, 2, 3, 5, 7, 8, 9]递归分解示意
[5, 2, 4, 7, 1, 3, 6, 2]
│
┌────────────────┴────────────────┐
[5, 2, 4, 7] [1, 3, 6, 2]
│ │
┌─────┴─────┐ ┌─────┴─────┐
[5, 2] [4, 7] [1, 3] [6, 2]
│ │ │ │
┌──┴──┐ ┌──┴──┐ ┌──┴──┐ ┌──┴──┐
[5] [2] [4] [7] [1] [3] [6] [2]
│ │ │ │ │ │ │ │
└─合并─┘ └─合并─┘ └─合并─┘ └─合并─┘
[2,5] [4,7] [1,3] [2,6]
│ │ │ │
└────合并──┘ └────合并──┘
[2,4,5,7] [1,2,3,6]
│ │
└──────────合并──────────┘
[1,2,2,3,4,5,6,7]实现
#include <stdlib.h>
#include <string.h>
// 合并两个有序子数组 arr[left..mid] 和 arr[mid+1..right]
void merge(int arr[], int left, int mid, int right) {
int n1 = mid - left + 1; // 左半区长度
int n2 = right - mid; // 右半区长度
// 创建临时数组（这是空间 O(n) 的来源）
int *L = malloc(n1 * sizeof(int));
int *R = 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; // 0 或 1 个元素
int mid = left + (right - left) / 2; // 防止溢出
merge_sort(arr, left, mid);
merge_sort(arr, mid + 1, right);
merge(arr, left, mid, right);
}
// 包装函数
void merge_sort_wrapper(int arr[], int n) {
merge_sort(arr, 0, n - 1);
}适用场景： 链表排序（不需要随机访问）、外部排序（处理大文件）、需要稳定排序的场景。
排序算法决策树
你需要对数据排序
│
├── 数据量很小（n < 50）？
│ ├── 是 → 插入排序（最简单、常数因子小）
│ └── 否 →
│ ├── 需要稳定排序？
│ │ ├── 是 → 归并排序
│ │ └── 否 →
│ │ ├── 需要原地排序（O(1) 额外空间）？
│ │ │ ├── 是 → 快速排序
│ │ │ └── 否 → 归并排序（最坏情况也是 O(nlogn)）
│ │ └── ...
│ └── 数据几乎有序？
│ └── 是 → 插入排序（近乎 O(n)）
│
├── 不需要自己写 → 用 C 标准库的 qsort()！
│ #include <stdlib.h>
│ int compare(const void *a, const void *b) {
│ return (*(int*)a - *(int*)b);
│ }
│ qsort(arr, n, sizeof(int), compare);完整演示程序
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
// 拷贝前面定义的五个排序函数...
// bubble_sort, selection_sort, insertion_sort,
// quick_sort, merge_sort_wrapper
void print_array(int arr[], int n) {
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n");
}
// 复制数组
void copy_array(int src[], int dest[], int n) {
memcpy(dest, src, n * sizeof(int));
}
// 测试所有排序算法
int main() {
int original[] = {64, 34, 25, 12, 22, 11, 90, 45, 33, 77};
int n = sizeof(original) / sizeof(original[0]);
int arr[10];
printf("原始数组: ");
print_array(original, n);
printf("\n======== 各种排序算法测试 ========\n");
// 冒泡排序
copy_array(original, arr, n);
bubble_sort(arr, n);
printf("冒泡排序: ");
print_array(arr, n);
// 选择排序
copy_array(original, arr, n);
selection_sort(arr, n);
printf("选择排序: ");
print_array(arr, n);
// 插入排序
copy_array(original, arr, n);
insertion_sort(arr, n);
printf("插入排序: ");
print_array(arr, n);
// 快速排序
copy_array(original, arr, n);
quick_sort(arr, 0, n - 1);
printf("快速排序: ");
print_array(arr, n);
// 归并排序
copy_array(original, arr, n);
merge_sort_wrapper(arr, n);
printf("归并排序: ");
print_array(arr, n);
return 0;
}要点总结
| 算法 | 核心思想 | 一句话 | 最适合 |
|---|---|---|---|
| 冒泡 | 相邻比较交换 | ”大气泡浮上来” | 教学、极小数组 |
| 选择 | 每次选最小 | ”挑最小的放前面” | 交换成本高 |
| 插入 | 像整理扑克牌 | ”新牌插入有序牌” | 小/几乎有序 |
| 快排 | 分治 + 分区 | ”小的归左边，大的归右边” | 通用首选 |
| 归并 | 分治 + 合并 | ”分成两半，排序后合并” | 需要稳定 |
最终建议：
- 日常使用 →
qsort()（C 标准库） - 面试手写 → 快排（最常考）、归并（稳定）
- 理解算法思维 → 五种都学一遍