排序算法分析
1. 冒泡排序（Bubble Sort）
原理图
@startuml
title 冒泡排序：相邻比较，大的往后"冒"
start
: 总共需要扫描 n-1 趟;
: i = 0;
while (i < len - 1 ?) is (是)
: 假设这一趟没有交换;
: swapped = false;
while (j < len - 1 - i ?) is (是)
if (相邻的左边 > 右边 ?) then (是)
: 交换这两个数;
note right: 大的数往后冒
: swapped = true;
endif
: j++;
endwhile (否)
if (这一趟没有发生交换 ?) then (是)
note right: 已经有序，提前结束
stop
endif
: i++;
endwhile (否)
stop
@enduml
通俗解释
从头开始，相邻两个数比较，大的往后移。每一轮扫下来，最大的数就"冒"到了末尾。如果某一轮没有发生任何交换，说明已经有序，提前结束。
指标
| 指标 | 值 |
|---|---|
| 时间复杂度（最好） | O(n) —— 已有序，一趟扫完无交换即结束 |
| 时间复杂度（平均） | O(n²) |
| 时间复杂度（最差） | O(n²) —— 完全倒序 |
| 空间复杂度 | O(1) |
| 稳定性 | 稳定 |
代码
VOID bubble_sort(INT32 *nums, INT32 len)
{
for (INT32 i = 0; i < len - 1; i++) {
BOOL swapped = FALSE;
for (INT32 j = 0; j < len - 1 - i; j++) {
if (nums[j] > nums[j + 1]) {
SWAP_TWO_NUMS(nums[j], nums[j + 1]);
swapped = TRUE;
}
}
if (!swapped) break;
}
}
2. 插入排序（Insertion Sort）
原理图
@startuml
title 插入排序：像打扑克摸牌一样，新牌插到合适位置
start
: 手里已经有第 0 张牌（认为它已排好序）;
: 摸下一张牌 i = 1;
while (还有没摸完的牌吗？) is (是)
: 看看新牌该插到哪里;
: j = i;
while (还没到头 且 新牌小于前面的牌？) is (是)
: 把前面的牌往后挪一位;
note right: 给新牌腾出位置
: j--;
endwhile (否)
: 新牌落位;
note right: 现在手里的牌又是从小到大了
: 摸下一张牌;
endwhile (否)
stop
@enduml
通俗解释
就像打扑克摸牌。左手已经拿了几张排好序的牌，新摸一张，从右往左比，找到合适的位置插进去。数组左侧是"手里的牌"，右侧是"还没摸的牌"。
指标
| 指标 | 值 |
|---|---|
| 时间复杂度（最好） | O(n) —— 已经有序时每次只比一下就结束 |
| 时间复杂度（平均） | O(n²) |
| 时间复杂度（最差） | O(n²) —— 倒序，每次都要挪一堆 |
| 空间复杂度 | O(1) |
| 稳定性 | 稳定 |
代码
VOID insertion_sort(INT32 *nums, INT32 len)
{
for (INT32 i = 1; i < len; i++) {
for (INT32 j = i; j > 0; j--) {
if (nums[j] < nums[j - 1]) {
SWAP_TWO_NUMS(nums[j], nums[j - 1]);
} else {
break;
}
}
}
}
3. 选择排序（Selection Sort）
原理图
@startuml
title 选择排序：每轮挑出最小的，放到前面去
start
: 从第 0 个位置开始;
while (还有没排好的位置吗？) is (是)
: 假设当前位置就是最小的;
: 记录它的位置 minIdx = i;
while (往后找还有更小的吗？) is (是)
if (发现更小的数 ?) then (是)
: 更新 minIdx;
note right: 记住这个更小的位置
endif
: 继续往后看;
endwhile (否)
: 把找到的最小值和当前位置交换;
note right: 现在这个位置就是正确的数了
: 去下一个位置;
endwhile (否)
stop
@enduml
通俗解释
每次从剩下的数里"挑"出最小的那个，放到最前面。就像从一堆苹果里挑出最小的放第一个，再从剩下的里面挑最小的放第二个……以此类推。
指标
| 指标 | 值 |
|---|---|
| 时间复杂度 | O(n²) —— 无论什么情况，都要完整扫一遍找最小值 |
| 空间复杂度 | O(1) |
| 稳定性 | 不稳定 —— 挑最小值时可能把相等的数换到后面去 |
代码
VOID selection_sort(INT32 *nums, INT32 len)
{
for (INT32 i = 0; i < len; i++) {
INT32 min = i;
for (INT32 j = i + 1; j < len; j++) {
if (nums[j] < nums[min]) {
min = j;
}
}
SWAP_TWO_NUMS(nums[i], nums[min]);
}
}
4. 快速排序（Quick Sort）
原理图
@startuml
title 快速排序：选个班长，小的站左边，大的站右边
start
: 处理数组 fragment (left ~ right);
if (这个片段是不是只有 0 或 1 个人？) then (是)
: 已经有序，不用再排了;
stop
else (否)
: 选第一个数当"班长"（pivot）;
: i = left, j = left + 1;
while (还有没看过的同学吗？) is (是)
if (这个同学比班长小 ?) then (是)
: i 往前走一步;
: 把这位同学换到 i 的位置;
endif
: j 往后看下一个;
endwhile (否)
: 把班长放到 i 位置;
note right: 现在左边都是比班长小的\n右边都是比班长大的
: 对左边小组(比班长小的) 重复此流程;
: 对右边小组(比班长大的) 重复此流程;
endif
stop
@enduml
通俗解释
选第一个人当"基准"，把比它小的都挪到左边，比它大的都挪到右边。然后左右两边各自再选基准、再分组……直到每组只剩一个人。这就是"分而治之"的思想。
指标
| 指标 | 值 |
|---|---|
| 时间复杂度（平均） | O(n log n) |
| 时间复杂度（最差） | O(n²) —— 每次选的基准都是最大或最小 |
| 空间复杂度（平均） | O(log n) —— 递归栈 |
| 空间复杂度（最差） | O(n) —— 数组完全有序时递归深度为 n |
| 稳定性 | 不稳定 |
代码
VOID quick_sort_proc(INT32 *nums, INT32 left, INT32 right)
{
if (left < right) {
INT32 cur = left;
INT32 i = cur, j = i + 1;
while (j <= right) {
if (nums[j] < nums[cur]) {
i++;
SWAP_TWO_NUMS(nums[i], nums[j]);
}
j++;
}
if (cur != i) SWAP_TWO_NUMS(nums[cur], nums[i]);
quick_sort_proc(nums, left, i - 1);
quick_sort_proc(nums, i + 1, right);
}
}
VOID quick_sort(INT32 *nums, INT32 len)
{
quick_sort_proc(nums, 0, len - 1);
}
5. 堆排序（Heap Sort）
原理图
@startuml
title 堆排序：先把数组搭成"金字塔"，再从塔顶取最大值
start
partition "第一步：搭成最大堆" {
: 从最后一个"有孩子"的节点开始;
while (还有没处理过的节点？) is (是)
: 把这个节点和它的孩子比较;
note right: 检查父节点 >= 两个孩子
: 如果父节点不是最大的，就和孩子中大的那个交换;
: 交换后继续检查被换下去的孩子;
: 处理下一个节点;
endwhile (否)
note right: 现在数组像个金字塔\n塔顶（nums[0]）就是最大值
}
partition "第二步：逐个取最大值" {
: i = 数组末尾;
while (还没取完？) is (是)
: 把塔顶（最大值）和位置 i 交换;
note right: 最大值"上岸"了
: 对剩余部分重新搭成堆;
note right: 让新的塔顶也满足条件
: i 往前移一位;
endwhile (否)
}
stop
@enduml
堆化过程
@startuml
title 堆化：让一个节点满足"父 >= 子"
start
: 把 root 记为"最大";
: 左孩子 = root × 2 + 1;
: 右孩子 = root × 2 + 2;
if (左孩子存在 且 比"最大"还大？) then (是)
: "最大" = 左孩子;
endif
if (右孩子存在 且 比"最大"还大？) then (是)
: "最大" = 右孩子;
endif
if (最大不是 root ?) then (是)
: root 和 max 交换;
: 对 max 位置继续堆化;
note right: 保证调整后下面也一样满足条件
endif
stop
@enduml
通俗解释
把数组想象成一个"金字塔"（堆）：顶点最大，每个节点都比它的孩子大。搭好这个金字塔后，每次把顶点的最大值取走放到数组末尾，然后重新调整金字塔。不断重复，就排好序了。
指标
| 指标 | 值 |
|---|---|
| 时间复杂度 | O(n log n) —— 建堆一次，取每个数都要调整 |
| 空间复杂度 | O(1) —— 直接在数组上操作 |
| 稳定性 | 不稳定 |
代码
VOID heap_create(INT32 *nums, INT32 len, INT32 root)
{
INT32 max = root;
INT32 leftChild = root * 2 + 1;
INT32 rightChild = root * 2 + 2;
if (leftChild < len && nums[leftChild] > nums[max]) {
max = leftChild;
}
if (rightChild < len && nums[rightChild] > nums[max]) {
max = rightChild;
}
if (max != root) {
SWAP_TWO_NUMS(nums[root], nums[max]);
heap_create(nums, len, max);
}
}
VOID heap_sort(INT32 *nums, INT32 len)
{
for (INT32 i = len / 2 - 1; i >= 0; i--)
heap_create(nums, len, i);
for (INT32 i = len - 1; i > 0; i--) {
SWAP_TWO_NUMS(nums[i], nums[0]);
heap_create(nums, i, 0);
}
}
6. 归并排序（Merge Sort）
原理图
@startuml
title 归并排序：先把数组拆成单个，再两两合并成有序
start
: 处理数组片段 (begin ~ end);
if (是不是只剩一个数了？) then (是)
: 一个数不用排;
stop
else (否)
: 从中间切成两半;
: mid = (begin + end) / 2;
partition "分：左右各自排序" {
: 左边一半: merge_sort(begin, mid);
note right: 递归，直到只剩一个数
: 右边一半: merge_sort(mid+1, end);
}
partition "合：把两个有序的片段合并" {
: i 指向左半开头, j 指向右半开头;
while (左右两边都还有人吗？) is (是)
if (左边的数 <= 右边的数 ?) then (是)
: 把左边的数放入辅助数组;
: i 往后走;
else (否)
: 把右边的数放入辅助数组;
: j 往后走;
endif
endwhile (否)
: 左边剩的都放进去;
: 右边剩的都放进去;
: 把辅助数组复制回原数组;
}
endif
stop
@enduml
分治归并过程
@startuml
title 归并排序：拆 → 拆 → 拆 → 合 → 合 → 合
left to right direction
rectangle "[5, 3, 8, 6, 2]" as a0
rectangle " 拆成两半 " as a1
rectangle "[5, 3, 8]" as a2
rectangle "[6, 2]" as a3
rectangle " 再拆 " as a4
rectangle " 再拆 " as a5
rectangle "[5, 3]" as a6
rectangle "[8] 不用拆了" as a7
rectangle "[6]" as a8
rectangle "[2]" as a9
rectangle " 再拆 " as a10
rectangle "[5]" as a11
rectangle "[3]" as a12
rectangle " 合并 [3, 5]" as m1
rectangle " 合并 [3, 5, 8]" as m2
rectangle " 合并 [2, 6]" as m3
rectangle " 最终合并 [2, 3, 5, 6, 8]" as m4
a0 --> a1
a1 --> a2
a1 --> a3
a2 --> a4
a2 --> a7
a3 --> a5
a5 --> a8
a5 --> a9
a4 --> a6
a4 --> "[8] 不…"
a6 --> a10
a10 --> a11
a10 --> a12
a11 --> m1
a12 --> m1
m1 --> m2
a7 --> m2
a8 --> m3
a9 --> m3
m2 --> m4
m3 --> m4
note right of m4: 有序了！
@enduml
通俗解释
把数组不断对半切，直到每个小组只剩一个人（一个人当然是有序的）。然后两两合并：合并的时候，比较两边的数，谁小谁先出来。这样不断合并，最后全部有序。
指标
| 指标 | 值 |
|---|---|
| 时间复杂度 | O(n log n) —— 稳定发挥，不管什么情况都要走完流程 |
| 空间复杂度 | O(n) —— 需要额外一个临时数组来合并 |
| 稳定性 | 稳定 |
代码
VOID merge_sort_proc(INT32 *nums, INT32 begin, INT32 end, INT32 *tempNums)
{
if (begin >= end) return;
INT32 mid = (begin + end) / 2;
merge_sort_proc(nums, begin, mid, tempNums);
merge_sort_proc(nums, mid + 1, end, tempNums);
INT32 i = begin, j = mid + 1, index = begin;
while (i <= mid && j <= end) {
if (nums[i] <= nums[j])
tempNums[index++] = nums[i++];
else
tempNums[index++] = nums[j++];
}
while (i <= mid)
tempNums[index++] = nums[i++];
while (j <= end)
tempNums[index++] = nums[j++];
memcpy(nums + begin, tempNums + begin, sizeof(INT32) * (end - begin + 1));
}
VOID merge_sort(INT32 *nums, INT32 len)
{
INT32 *tempNums = (INT32 *)malloc(sizeof(INT32) * len);
merge_sort_proc(nums, 0, len - 1, tempNums);
free(tempNums);
}
7. 希尔排序（Shell Sort）
原理图
@startuml
title 希尔排序：先跳着排，再挨着排（插入排序的升级版）
start
: gap = len / 2;
while (gap 还没缩小到 0？) is (是)
note right: 当前间隔 = gap（跳着比较）
: 从位置 gap 开始;
: i = gap;
while (还没到数组末尾？) is (是)
: 记下当前位置的值 temp;
: j = i;
while (还能往前跳 gap 步 且 前面那个数比 temp 大？) is (是)
: 把前面的数"挪"到当前位置;
note right: 跳着后移 gap 步
: j 往前跳 gap 步;
endwhile (否)
: 把 temp 放回正确位置;
note right: 跳着排好了一个数
: i 往后走一步;
endwhile (否)
: gap 缩小一半;
note right: 间隔越来越小\n最后一轮 gap=1 就是普通插入排序
endwhile (否)
stop
@enduml
间隔变化
@startuml
title 间隔逐步缩小的过程
skinparam rectangle {
BackgroundColor #FEFEFE
BorderColor #333333
}
rectangle "gap = 数组长度的一半 → 不断减半 → 直到 1" as seq
rectangle "比如长度8: gap=4 → gap=2 → gap=1" as eg
rectangle "gap=4: 位置0和4比、1和5比、2和6比、3和7比" as g4
rectangle "gap=2: 位置0、2、4、6 一组；1、3、5、7 一组" as g2
rectangle "gap=1: 所有数挨个比（普通插入排序）" as g1
seq --> eg
eg --> g4
g4 --> g2
g2 --> g1
note right of g4: 数据快速"大略"有序
note right of g2: 更有序了
note right of g1: 已经接近有序，\n插入排序很快
@enduml
通俗解释
插入排序的升级版。先让相距较远的元素比较交换（比如隔 4 个位置比一比），让数组快速变得"大体有序"。然后不断缩小间隔，直到间隔为 1 时就是普通的插入排序。这时候数组已经基本有序了，插入排序飞快。
指标
| 指标 | 值 |
|---|---|
| 时间复杂度（最好） | O(n) |
| 时间复杂度（平均/最差） | O(n) ~ O(n²) —— 取决于 gap 序列怎么选 |
| 空间复杂度 | O(1) |
| 稳定性 | 不稳定 |
代码
VOID shell_sort(INT32 *nums, INT32 len)
{
for (INT32 gap = len / 2; gap > 0; gap /= 2) {
for (INT32 i = gap; i < len; i++) {
INT32 temp = nums[i];
INT32 j;
for (j = i; j >= gap && nums[j - gap] > temp; j -= gap) {
nums[j] = nums[j - gap];
}
nums[j] = temp;
}
}
}
8. 基数排序（Radix Sort）
原理图
@startuml
title 基数排序：按个位、十位、百位……一次次排队
start
: 找到数组中最大的数（知道最多有几位）;
: exp = 1（先从个位开始）;
while (还有更高位没处理？) is (是)
note right: 当前处理的是"个位"或"十位"……
: 准备 10 个桶（0 ~ 9）;
: 遍历数组，看每个数当前位是几;
note right
比如 exp=1:
数字 12 → 个位是 2 → 丢进 2 号桶
end note
: 统计每个桶里有多少个数;
: 计算每个桶的"截止位置";
note right: 决定每个数应该放到临时数组的哪个位置
: 从右往左遍历，按桶位置放入临时数组;
note right: 从右往左遍历是为了保证"稳定"
: 把临时数组复制回原数组;
: exp ×= 10（升到下一位）;
endwhile (否)
stop
@enduml
按位排序示例
@startuml
title 举例：[12, 43, 38, 25, 7] 的排序过程
skinparam rectangle {
BackgroundColor #FEFEFE
BorderColor #333333
}
rectangle "原始: [12, 43, 38, 25, 7]" as s0
rectangle "先按个位排队: [12, 43, 25, 7, 38]" as s1
rectangle "再按十位排队: [7, 12, 25, 38, 43]" as s2
s0 --> s1 : 第一轮：看个位
s1 --> s2 : 第二轮：看十位
note right of s1
按个位排好后:
个位 2→3→5→7→8
（个位有序了）
end note
note right of s2
按十位排好后:
十位 0→1→2→3→4
（十位也有序了）
最终整体有序
end note
@enduml
通俗解释
不比较大小，而是按"位"来排队。先看个位，把个位是 0 的放一起、是 1 的放一起……个位排好后，再看十位排……直到最高位。就像整理一沓试卷，先按科目分，再按班级分，最后自然就整理好了。
指标
| 指标 | 值 |
|---|---|
| 时间复杂度 | O(n·k) —— n 是数字个数，k 是最大位数 |
| 空间复杂度 | O(n + k) |
| 稳定性 | 稳定 |
k 为最大数字的位数
代码
VOID radix_sort_proc(INT32 *nums, INT32 len, INT32 exp)
{
INT32 *tempNums = (INT32 *)malloc(sizeof(INT32) * len);
INT32 cnt[10] = {0};
for (INT32 i = 0; i < len; i++)
cnt[(nums[i] / exp) % 10]++;
for (INT32 i = 1; i < 10; i++)
cnt[i] += cnt[i - 1];
for (INT32 i = len - 1; i >= 0; i--) {
INT32 digit = (nums[i] / exp) % 10;
tempNums[cnt[digit] - 1] = nums[i];
cnt[digit]--;
}
memcpy(nums, tempNums, sizeof(INT32) * len);
free(tempNums);
}
VOID radix_sort(INT32 *nums, INT32 len)
{
if (len <= 0) return;
INT32 maxNum = nums[0], minNum = nums[0];
for (INT32 i = 1; i < len; i++) {
if (nums[i] > maxNum) maxNum = nums[i];
if (nums[i] < minNum) minNum = nums[i];
}
INT32 offset = (minNum < 0) ? -minNum : 0;
if (offset > 0) {
for (INT32 i = 0; i < len; i++) nums[i] += offset;
maxNum += offset;
}
for (INT32 exp = 1; maxNum / exp > 0; exp *= 10)
radix_sort_proc(nums, len, exp);
if (offset > 0) {
for (INT32 i = 0; i < len; i++) nums[i] -= offset;
}
}
总结对比
一眼看懂选哪个
| 算法 | 一句话概括 | 时间复杂度 | 空间 | 稳定 |
|---|---|---|---|---|
| 冒泡排序 | 相邻比较，大的往后"冒" | O(n)~O(n²) | O(1) | Y |
| 插入排序 | 像打扑克摸牌插牌 | O(n)~O(n²) | O(1) | Y |
| 选择排序 | 每轮挑最小的放前面 | O(n²) | O(1) | N |
| 快速排序 | 选基准，小的左大的右 | O(n log n) | O(log n)~O(n) | N |
| 堆排序 | 搭成堆，取塔顶 | O(n log n) | O(1) | N |
| 归并排序 | 拆成单个，两两合并 | O(n log n) | O(n) | Y |
| 希尔排序 | 先跳着排再挨着排 | O(n)~O(n²) | O(1) | N |
| 基数排序 | 按个十百位排队 | O(n·k) | O(n+k) | Y |
分类
- 比较大小来排序（7种）：冒泡、插入、选择、快排、堆排、归并、希尔
- 不比较大小（1种）：基数排序（靠位运算）
- 在原数组上排（原地）：冒泡、插入、选择、快排、堆排、希尔
- 需要额外空间：归并（需要 O(n) 临时数组）、基数（需要计数数组）
- 稳定的：冒泡、插入、归并、基数
- 不稳定的：选择、快排、堆排、希尔