七大排序算法全解析：从插入到三路快排，手把手带你掌握核心思想与实战陷阱

排序算法（Sort）

排序是计算机科学中最基础、最经典的算法问题之一，也是面试和实际开发中的高频考点。本文系统性地解析了七大经典排序算法：插入排序、希尔排序、冒泡排序、选择排序、堆排序、快速排序（Hoare版+三数取中）以及三路快速排序。每种算法都配有完整的C语言实现、逐行解释、时间复杂度分析和关键陷阱提示。

目标读者：正在学习数据结构与算法的在校学生、准备技术面试的求职者，以及需要复习排序算法核心思想的开发者。

核心价值：

1. 代码实战导向：每个算法都提供可直接运行的C语言实现，并附有逐行注释，帮助理解每一行代码的作用。
2. 陷阱全解析：特别总结了每个算法最容易出错的地方（如选择排序的maxi修正、快排的end先走原则、三路快排的i前进逻辑），避免踩坑。
3. 工业级优化：不仅讲解基础版本，还引入了三数取中、三路划分等工程优化技巧，提升算法在实际场景中的性能。
4. 对比与选型：通过复杂度总表和适用场景分析，帮助你根据数据规模、有序度、稳定性等需求选择最合适的排序算法。

无论你是为了通过考试、准备面试，还是想在项目中写出更高效的排序代码，这篇文章都将为你提供清晰的思路和实用的代码参考。

排序像整理一手乱牌：有的算法是一张张往手里插（插入），有的是按间隔分组排再合并（希尔），有的是两两比较冒泡（冒泡），有的是挑最大最小放两头（选择），有的是建堆取顶（堆排），有的是分地盘递归（快排）。各有各的脾气和适用场景。

核心思想

排序没有「最好」，只有「最适合」。选择排序算法要看：数据规模、是否基本有序、是否稳定、是否要原地（空间 O(1)）、是否含大量重复元素。

本项目实现了：插入、希尔、冒泡、选择、堆排、快排（Hoare + 三数取中）、三路快排。先讲辅助函数，再逐一拆解每种排序。

辅助函数

交换 Swap

voidSwap(int*a,int*b){intc=*a;*a=*b;*b=c;}

逐行解释：传指针才能修改实参。经典三变量交换。工程提示：现代编译器下，用临时变量的交换往往比「不用临时变量的位运算异或交换」更快（异或交换有数据依赖、不可并行、且a==b时会清零），且可读性好，所以别迷信「不用临时变量更高级」。

向下调整 AdjustDown（堆排用）

voidAdjustDown(int*a,intn,intparent){intchild=2*parent+1;// 左孩子while(child<n){if(child+1<n&&a[child]<a[child+1])// 大根堆：选较大孩子child++;if(a[child]>a[parent])// 孩子比父大就下沉{Swap(&a[child],&a[parent]);parent=child;child=2*parent+1;}elsebreak;}}

逐行解释：注意这里是大根堆的向下调整（a[child] < a[child+1]选大孩子，a[child] > a[parent]才下沉），和堆模块里小根堆的比较符号相反。堆排升序要用大根堆——因为要把最大值换到末尾。child+1 < n防右孩子越界。

1. 插入排序 InsertSort（O(n²)，稳定，小数据王者）

voidInsertSort(int*a,intsz){// 排序[0,end]有序，把 end+1 插入for(inti=0;i<sz-1;i++){intend=i;inttmp=a[end+1];// 待插元素先存起来while(end>=0){if(tmp<a[end])// 比 tmp 大的往后挪{a[end+1]=a[end];end--;}elsebreak;}a[end+1]=tmp;// 找到位置，放下}}

原理：像整理扑克牌——左手中已排好序，从右手抽一张，在左手从右往左找位置，比它大的牌往后挪一格，找到空位插进去。

逐行解释：

• 外层i控制把哪个元素插入（a[i+1]），[0, i]始终有序。
• tmp必须先存——因为a[end+1]会被后面的挪动覆盖，不存就丢了。
• 内层while从end往左扫，比tmp大的就右移一格，直到找到不大于tmp的位置。
• a[end+1] = tmp把待插元素放进空位。

关键点：

• tmp必须提前保存（最高频考点）。
• 最好情况（基本有序）O(n)，最坏 O(n²)。
• 稳定（相等元素不交换，相对顺序不变）。
• 小数据量（<16）时比快排还快，所以快排常在小区间切换到插入排序。

2. 希尔排序 ShellSort（O(n^1.3)，不稳定，插入的升级）

voidShellSort(int*a,intn){intgap=n;while(gap>1){gap=gap/3+1;// 缩小间隔，+1 保证最后 gap=1for(inti=0;i<n-gap;i++){intend=i;inttmp=a[end+gap];// 跨 gap 取待插元素while(end>=0){if(tmp<a[end]){a[end+gap]=a[end];// 跨 gap 挪动end-=gap;}elsebreak;}a[end+gap]=tmp;}}}

原理：插入排序在「基本有序」时很快，但整体乱时慢。希尔先按大间隔gap分组做插入排序（让远的元素快速归位），逐步缩小gap，最后gap=1做一次普通插入排序收尾。因为前面已让数组「基本有序」，最后一次插入排序接近 O(n)。

逐行解释：

• gap = gap/3 + 1：每次缩到约 1/3，+1保证gap最终会变成 1（否则gap可能卡在 2→0 跳出，漏了最后一次完整排序）。
• 内层和插入排序几乎一样，只是步长从 1 变成gap——同一个位置可以同时排多个间隔为 gap 的组（代码里用i从 0 到n-gap，相当于多组并排）。
• a[end+gap] = tmp：放回时也要跨gap。

注释里的笔误：项目代码注释中旧版本写成了a[end+1] = tmp，应该是a[end+gap] = tmp（跨 gap 放回）。当前实际代码已修正为a[end+gap]。

关键点：gap序列影响性能，gap/3+1是常用序列，平均约 O(n^1.3)。不稳定（相同元素可能分到不同组，相对顺序会变）。

3. 冒泡排序 BubbleSort（O(n²)，稳定，教学用）

voidBubbleSort(int*a,intn){for(intj=0;j<n-1;j++)// n-1 趟{for(inti=1;i<n-j;i++)// 每趟把最大冒到末尾{if(a[i-1]>a[i])// 前比后大就交换Swap(&a[i-1],&a[i]);}}}

原理：相邻元素两两比较，前大后小就交换，每趟把当前最大值「冒泡」到末尾。

逐行解释：外层j控制趟数（n-1 趟），内层i扫一遍未排序部分。n-j是因为末尾j个已排好不用再比。

优化点（未实现）：加一个flag，若某趟无任何交换说明已有序，提前结束——最好情况可到 O(n)。当前实现无论是否有序都跑满 O(n²)。

关键点：稳定（相等不交换）。简单但慢，基本只在教学和「几乎有序 + 数据量小」时用。

4. 选择排序 SelectSort（O(n²)，不稳定，每轮选两头）

voidSelectSort(int*a,intn){intbegin=0,end=n-1;while(begin<end){intmaxi=begin,mini=begin;for(inti=mini+1;i<=end;i++)// 一轮同时找最大和最小{if(a[i]>a[maxi])maxi=i;if(a[i]<a[mini])mini=i;}Swap(&a[mini],&a[begin]);// 最小放开头if(maxi==begin)// ⚠️ 关键：maxi 被 mini 换走了maxi=mini;Swap(&a[maxi],&a[end]);// 最大放末尾begin++;end--;}}

原理：每轮在[begin, end]里同时找最小值和最大值，最小放begin，最大放end，两端向中间收拢。比普通「每轮只找最小」的版本少一半轮次。

逐行解释 & 关键陷阱：

• 一轮同时更新maxi和mini。
• Swap(&a[mini], &a[begin])把最小换到开头——但如果maxi恰好等于begin，这一步把a[begin]（即原最大值）换到了mini位置，maxi下标失效！所以下一行if(maxi == begin) maxi = mini;修正：最大值现在在mini处。
• 这是选择排序最经典的坑：先换 mini 可能破坏 maxi 指向，必须判断修正。

关键点：不稳定（交换跨越了相等元素）。虽优化了一半轮次，但比较次数仍是 O(n²)。

5. 堆排序 HeapSort（O(n log n)，不稳定，原地）

voidHeapSort(int*a,intn){// 建大根堆：从最后一个非叶子节点开始向下调整for(inti=(n-2)/2;i>=0;i--)AdjustDown(a,n,i);// 反复取堆顶（最大）放末尾，缩小堆，再调整for(intend=n-1;end>0;end--){Swap(&a[0],&a[end]);// 堆顶（最大）换到末尾AdjustDown(a,end,0);// 对 [0, end) 重新向下调整}}

原理：升序要建大根堆。建堆后堆顶是最大值，交换到末尾，然后对剩余部分（end减小）重新向下调整恢复堆序。重复 n-1 次，数组即升序。

逐行解释：

• 建堆从(n-2)/2（最后一个非叶子节点）开始，往前每个节点向下调整。这是 O(n) 建堆法（不是逐个 push 的 O(n log n)）。
• 排序循环：Swap(&a[0], &a[end])把当前堆顶（最大）换到end位置，end--缩小堆的范围，AdjustDown(a, end, 0)对剩下的堆顶做一次向下调整（注意传入end而非n，因为末尾已排好不再参与）。

关键点：升序用大根堆（最大值往末尾送），降序用小根堆。不稳定。原地排序，空间 O(1)。建堆 O(n)，排序 n 次 O(log n) 调整，总体 O(n log n)。

6. 快速排序 QuickSort（Hoare 版 + 三数取中）

三数取中 Getmidi（优化 pivot）

intGetmidi(int*a,intleft,intright){intmidi=(left+right)/2;if(a[left]<a[midi]){if(a[midi]<a[right])returnmidi;elseif(a[left]<a[right])returnright;elsereturnleft;}else{if(a[right]>a[left])returnleft;elseif(a[midi]>a[right])returnmidi;elsereturnright;}}

原理：快排最怕有序数据——如果每次选第一个做 pivot，有序数组会让每轮只分出一个元素，退化到 O(n²)。三数取中从left、mid、right三个位置选中间值做 pivot，避免极端。

逐行解释：通过嵌套比较三个位置的值，返回中间值的下标。逻辑绕，但本质就是「三个数里排中间那个」。不是为了找最大或最小，而是找中位，让划分更均衡。

Hoare 划分版 QuickSort

voidQuickSort(int*a,intleft,intright){if(left>=right)return;// 区间长度 <=1 终止intmidi=Getmidi(a,left,right);Swap(&a[midi],&a[left]);// pivot 换到 left 位置intkeyi=left;intbegin=left,end=right;while(begin<end){// end 先走，找比 pivot 小的while(begin<end&&a[end]>=a[keyi])end--;// begin 后走，找比 pivot 大的while(begin<end&&a[begin]<=a[keyi])begin++;Swap(&a[begin],&a[end]);// 交换这对逆序}Swap(&a[keyi],&a[end]);// pivot 归位到相遇点keyi=begin;QuickSort(a,left,keyi-1);// 递归左半QuickSort(a,keyi+1,right);// 递归右半}

原理：选一个 pivot，把数组分成「小于 pivot / pivot / 大于 pivot」三段，pivot 到位，再递归排左右两段。分治思想。

逐行解释 & 关键点：

1. Getmidi选 pivot 并换到left，避免有序退化。
2. 为什么end先走：pivot 在left，end从右找小的，begin从左找大的。当begin和end相遇时，相遇点的值应该比 pivot 小（因为是end最后停在那），这样Swap(&a[keyi], &a[end])才能把 pivot 换到正确的「左小右大」分界。如果begin先走，相遇点可能是比 pivot 大的值，pivot 换过去就错了。这是 Hoare 划分最核心的细节。
3. a[end] >= a[keyi]用>=而非>：遇到相等的也跳过，避免相等元素卡住循环。
4. 递归终止left >= right：区间空或单元素已有序。

关键点：

• 平均 O(n log n)，最坏 O(n²)（三数取中极大缓解）。
• 递归深度 O(log n)，栈空间。
• 不稳定。
• 工程优化（未实现）：小区间（如 <16）切换插入排序，减少递归开销；尾递归优化减少栈深度。

7. 三路快速排序 QuickSort3Way（解决大量重复元素）

voidQuickSort3Way(int*a,intleft,intright){if(left>=right)return;intmidi=Getmidi(a,left,right);Swap(&a[midi],&a[left]);intkey=a[left];// 三段循环不变量：// a[left..lt-1] < key// a[lt..i-1] = key// a[i..gt] 未处理// a[gt+1..right] > keyintlt=left;intgt=right;inti=left;while(i<=gt){if(a[i]<key)// 小于：换到 < 区{Swap(&a[i],&a[lt]);lt++;i++;// i 前进，换来的已检查过}elseif(a[i]>key)// 大于：换到 > 区{Swap(&a[i],&a[gt]);// ⚠️ i 不前进！换来的 a[gt] 没检查过gt--;}else// 等于：留在 = 区{i++;}}// 只递归 < 区和 > 区，= 区已就位不再处理QuickSort3Way(a,left,lt-1);QuickSort3Way(a,gt+1,right);}

原理：荷兰国旗问题（Dutch National Flag）。传统快排两路划分在大量重复元素时会退化（很多元素等于 pivot，反复无效交换）。三路把数组分成< key、= key、> key三段，= key段直接跳过不再递归，重复元素越多越快。

逐行解释 & 关键点：

• 三个游标维护循环不变量：lt是<区右端，gt是>区左端，i是当前考察位置。
• a[i] < key：换到<区末尾，lt++、i++。换来的元素来自lt位置（属于=区，已检查过），所以i前进。
• a[i] > key：换到>区开头，gt--。i不前进——因为从gt换过来的元素还没检查过，下轮要再看它。
• a[i] == key：留在=区，i++。
• 递归只处理<区[left, lt-1]和>区[gt+1, right]，= key段跳过。

i是否前进是最关键的细节：<和==时i++，>时i不动。搞反了会漏判或多判。

关键点：解决大量重复元素的退化问题，重复越多越接近 O(n)。仍然 O(n log n) 平均、不稳定。

复杂度与特性总表

常见陷阱清单

1. 插入排序不先存tmp→ 待插元素被覆盖丢失。
2. 希尔排序gap不加 1→gap卡在 2 跳出，漏最后一次完整排序。
3. 选择排序maxi == begin不修正→maxi指向被mini交换走的值，结果错误。
4. 堆排序升序建小根堆→ 应建大根堆（最大值往末尾送）。
5. Hoare 快排begin先走→ 相遇点可能是大值，pivot 归位错误。
6. 三路快排a[i] > key时i++→ 漏判换来的元素。
7. quicksort_残缺函数→ 代码里有个未完成的quicksort_，含未定义的swap、逻辑残缺，会导致编译失败（建议删除）。
8. 快排不处理有序退化→ 应加三数取中或随机化 pivot（本项目已加三数取中 ✅）。

我的实现 vs 教科书实现

• 亮点：快排加了三数取中（防有序退化）+ 三路划分（防重复退化），这是工业级优化意识。选择排序双向选 max/min 减半轮次。
• 残缺代码：quicksort_函数未完成，会编译失败，应删除。
• 注释笔误：希尔排序注释旧版本a[end+1] = tmp应为a[end+gap]（实际代码已对）。
• 缺归并排序：稳定 O(n log n)，外部排序、链表排序必备。
• 缺非比较排序：计数排序、基数排序、桶排序（线性时间，适合整数范围有限）。
• 缺快排优化：小区间切换插入排序、非递归（用栈模拟）。
• 测试覆盖：三路快排测了全相等/大量重复/已排序/逆序四种 case，测试意识好。

拓展知识点

变体与进阶

• 归并排序：分治 + 合并，稳定 O(n log n)，适合链表排序和外部排序（数据放不下内存时）。手写重点在merge的双指针合并和临时数组。
• 计数排序：统计每个值出现次数，适合值域小的整数，O(n+k)。非比较排序，能突破 O(n log n) 下界。
• 基数排序：按位（个十百…）用计数排序，适合定长整数或字符串。
• 桶排序：分桶后桶内排序，适合均匀分布数据。
• 双轴快排（Dual-Pivot）：JDKArrays.sort对基本类型的实现，两个 pivot 分三段，实测比单轴快。

常见考点（必刷）

• 快排的 pivot 优化：三数取中、随机化，防有序退化。
• 三路划分：大量重复元素的优化，荷兰国旗问题。
• 堆排序建堆 O(n) 证明：调整距离求和。
• 排序稳定性：哪些稳定（插入/冒泡/归并），哪些不稳定（希尔/选择/堆/快），及稳定性的应用场景（多关键字排序）。
• 快排非递归：用栈模拟递归，避免栈溢出。
• 各排序手写：面试常要求手写快排、归并、堆排。

与其他结构的关系

堆排序依赖堆结构（见 Binary_Tree 模块的AdjustDown/AdjustUp）；归并排序体现分治，和快排同源；快排的划分思想与 BST 的构建同构（一次快排划分 ≈ 把 pivot 插入 BST）。排序是二分查找、贪心、双指针等算法的前置条件——很多算法要求输入有序。

一句话记忆法

插入像理牌先存 tmp，希尔按 gap 缩，冒泡相邻换，选择两头挑且防 maxi 被换走，堆排建大根堆取顶，快排 end 先走 + 三数取中，三路分 < = > 且遇大于 i 不动。