引言
在前面的博客中，我们学习了栈、队列等基础数据结构，它们解决的是“如何组织数据”的问题。而今天要聊的排序算法，解决的是“如何让数据有序”的问题。排序看似简单，却暗藏着一场效率与稳定的博弈：有的算法跑得快但“喜新厌旧”，有的算法四平八稳却要付出额外空间。两者看似矛盾，却在不同的业务场景下各显神通。
这篇博客将从三个角度展开：
- 评价指标：先弄清时间复杂度、空间复杂度和稳定性这些“裁判标准”。
- 过程演示：用状态图直观展示每种排序的“舞步”。
- C 语言实现：给出完整可运行的代码，边看边练。
一、排序算法的评价指标
学习排序之前，先明确几个概念：
1. 思路
排序算法的好坏，主要看三个评价指标：
- 时间复杂度：算法执行时间随数据规模增长的变化趋势。
- 空间复杂度：算法运行过程中额外需要的存储空间。
- 稳定性：如果排序前两个相等元素的相对顺序，在排序后保持不变，那么这个排序算法就是稳定的。
举个例子：
排序前：5(a), 3, 5(b), 1 排序后：1, 3, 5(a), 5(b)如果5(a)仍然在5(b)前面，就是稳定排序；如果两者位置互换，就是不稳定排序。
2. 过程演示
常见复杂度一览：
O(n²) ：冒泡、选择、插入 O(n log n)：归并、快速、堆排序 O(n + k) ：计数排序3. C 语言实现
这里先给出一个通用的交换函数，后续所有排序都会用到：
/* ====== 通用交换函数 ====== */ void swap(int *a, int *b) { int temp = *a; *a = *b; *b = temp; }二、冒泡排序：相邻元素的“擂台赛”
1. 思路
冒泡排序就像一场相邻元素的擂台赛：每次比较相邻两个元素，如果顺序错误就交换。每一轮结束后，最大的元素会像气泡一样“冒泡”到末尾。
- 每一轮从第一个元素开始，两两比较相邻元素。
- 如果前一个比后一个大，就交换它们。
- 一轮结束后，最大的元素“沉底”。
- 如果某一轮没有发生任何交换，说明已经有序，可以提前结束。
2. 过程演示
以数组[5, 3, 8, 1]为例：
初始状态：[5, 3, 8, 1] 第 1 轮： 比较 5 和 3 -> 交换 -> [3, 5, 8, 1] 比较 5 和 8 -> 不交换 -> [3, 5, 8, 1] 比较 8 和 1 -> 交换 -> [3, 5, 1, 8] （8 冒泡到末尾） 第 2 轮： 比较 3 和 5 -> 不交换 -> [3, 5, 1, 8] 比较 5 和 1 -> 交换 -> [3, 1, 5, 8] （5 冒泡到倒数第二） 第 3 轮： 比较 3 和 1 -> 交换 -> [1, 3, 5, 8] （3 冒泡到位） 结果状态：[1, 3, 5, 8]3. C 语言实现
这里复用上面的swap函数：
/* ====== 冒泡排序 ====== */ void bubbleSort(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]) { swap(&arr[j], &arr[j + 1]); swapped = 1; } } // 如果本轮没有发生交换，说明已经有序 if (!swapped) { break; } } }三、选择排序：每轮挑出“最靓的仔”
1. 思路
选择排序的思路很直白：每一轮从未排序区间中选择最小元素，放到已排序区间的末尾。就像每次从一堆牌里挑出最小的一张，依次排好。
- 把数组分成已排序区和未排序区。
- 每一轮在未排序区中找到最小元素的下标。
- 如果最小元素不在未排序区开头，就把它交换到开头。
- 重复 n-1 轮，数组就有序了。
2. 过程演示
以数组[5, 3, 8, 1]为例：
初始状态：[5, 3, 8, 1] 第 1 轮：未排序区 [5, 3, 8, 1]，最小是 1（下标 3） 交换 5 和 1 -> [1, 3, 8, 5] （1 归位） 第 2 轮：未排序区 [3, 8, 5]，最小是 3（下标 1） 已在开头，不交换 -> [1, 3, 8, 5] （3 归位） 第 3 轮：未排序区 [8, 5]，最小是 5（下标 3） 交换 8 和 5 -> [1, 3, 5, 8] （5 归位） 结果状态：[1, 3, 5, 8]3. C 语言实现
这里复用上面的swap函数：
/* ====== 选择排序 ====== */ void selectionSort(int arr[], int n) { for (int i = 0; i < n - 1; i++) { int minIndex = i; // 记录最小元素下标 for (int j = i + 1; j < n; j++) { if (arr[j] < arr[minIndex]) { minIndex = j; } } if (minIndex != i) { swap(&arr[i], &arr[minIndex]); } } }四、插入排序：像整理扑克牌一样
1. 思路
插入排序就像整理手中的扑克牌：每次从未排序区取出一张牌，插入到已排序区的正确位置。数据量小或基本有序时，它效率极高。
- 把数组分成已排序区和未排序区。
- 每次从未排序区取出第一个元素
key。 - 从后往前扫描已排序区，把比
key大的元素依次后移。 - 找到合适位置后，把
key插入。
2. 过程演示
以数组[5, 3, 8, 1]为例：
初始状态：[5, 3, 8, 1] 第 1 轮：key = 3，已排序区 [5] 5 > 3，后移 -> [5, 5, 8, 1] 插入 3 -> [3, 5, 8, 1] 第 2 轮：key = 8，已排序区 [3, 5] 5 < 8，不移动 -> [3, 5, 8, 1] 插入 8 -> [3, 5, 8, 1] 第 3 轮：key = 1，已排序区 [3, 5, 8] 8 > 1，后移 -> [3, 5, 8, 8] 5 > 1，后移 -> [3, 5, 5, 8] 3 > 1，后移 -> [3, 3, 5, 8] 插入 1 -> [1, 3, 5, 8] 结果状态：[1, 3, 5, 8]3. C 语言实现
/* ====== 插入排序 ====== */ void insertionSort(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; } }五、希尔排序：插入排序的“跳跃升级”
1. 思路
希尔排序是插入排序的改进版。它通过设置一个增量gap，先对间隔为gap的元素进行插入排序，再逐渐缩小gap，最终当gap = 1时完成排序。这样可以让元素“大步跳跃”到接近最终位置，减少后续移动次数。
- 初始
gap = n / 2，每次循环gap /= 2。 - 对每个间隔为
gap的子序列做插入排序。 - 当
gap = 1时，就是普通的插入排序，但此时数组已基本有序。
2. 过程演示
以数组[5, 3, 8, 1]为例：
初始状态：[5, 3, 8, 1] gap = 2： 子序列1：[5, 8]（下标 0, 2）-> 已有序 子序列2：[3, 1]（下标 1, 3）-> 排序后 [1, 3] 结果：[5, 1, 8, 3] gap = 1： 普通插入排序 -> [1, 3, 5, 8] 结果状态：[1, 3, 5, 8]3. C 语言实现
/* ====== 希尔排序 ====== */ void shellSort(int arr[], int n) { for (int gap = n / 2; gap > 0; gap /= 2) { for (int i = gap; i < n; i++) { int temp = arr[i]; int j = i; while (j >= gap && arr[j - gap] > temp) { arr[j] = arr[j - gap]; j -= gap; } arr[j] = temp; } } }六、归并排序：分而治之的“合纵连横”
1. 思路
归并排序采用分治法，把大问题拆成小问题，再合并结果：
- 把数组分成左右两部分。
- 分别对左右两部分排序（递归）。
- 合并两个有序数组，得到整体有序。
归并排序是稳定的，但需要额外空间。
2. 过程演示
以数组[5, 3, 8, 1]为例：
初始状态：[5, 3, 8, 1] 拆分： [5, 3] 和 [8, 1] [5] [3] 和 [8] [1] 合并： [3, 5] 和 [1, 8] [1, 3, 5, 8] 结果状态：[1, 3, 5, 8]3. C 语言实现
#include <stdlib.h> /* ====== 合并两个有序区间 ====== */ void merge(int arr[], int temp[], int left, int mid, int right) { int i = left; int j = mid + 1; int k = left; while (i <= mid && j <= right) { if (arr[i] <= arr[j]) { temp[k++] = arr[i++]; } else { temp[k++] = arr[j++]; } } while (i <= mid) { temp[k++] = arr[i++]; } while (j <= right) { temp[k++] = arr[j++]; } for (i = left; i <= right; i++) { arr[i] = temp[i]; } } /* ====== 归并排序（递归） ====== */ void mergeSort(int arr[], int temp[], int left, int right) { if (left >= right) { return; } int mid = left + (right - left) / 2; mergeSort(arr, temp, left, mid); mergeSort(arr, temp, mid + 1, right); merge(arr, temp, left, mid, right); } /* ====== 归并排序入口 ====== */ void mergeSortWrapper(int arr[], int n) { int *temp = (int *)malloc(n * sizeof(int)); if (temp == NULL) { return; } mergeSort(arr, temp, 0, n - 1); free(temp); }七、快速排序：选个“基准”当裁判
1. 思路
快速排序也采用分治法，但思路更“霸道”：
- 选择一个基准值
pivot。 - 把小于等于基准值的元素放到左边，大于基准值的放到右边。
- 对左右区间递归排序。
快速排序平均性能极佳，但不稳定，最坏情况会退化到 O(n²)。
2. 过程演示
以数组[5, 3, 8, 1]为例（选最后一个元素为基准）：
初始状态：[5, 3, 8, 1]，pivot = 1 分区： 5 > 1，不动；3 > 1，不动；8 > 1，不动 把 1 换到开头 -> [1, 5, 3, 8] 递归左区间：[1]（已有序） 递归右区间：[5, 3, 8]，pivot = 8 5 < 8，不动；3 < 8，不动 8 已在末尾 -> [5, 3, 8] 递归左区间：[5, 3]，pivot = 3 5 > 3，不动 把 3 换到开头 -> [3, 5] 结果状态：[1, 3, 5, 8]3. C 语言实现
这里复用上面的
