简介面向算法学习者与编程初学者的排序算法专题资源汇总选择排序、插入排序、归并排序、快速排序、堆排序、冒泡排序、希尔排序七种基于比较的经典排序方法。资源包共18个文件其中15个Java源码文件完整实现各算法另有README说明文档、开源许可与版本控制配置文件整体仅18KB轻量易用。每种算法均按核心思想、实现逻辑、复杂度特征与适用场景组织代码可帮助读者对照描述快速理解从简单到复杂的排序策略并在实际项目中根据数据规模、稳定性需求和内存限制做出合理选型。目前已有1816人学习下载适合备考笔试、准备面试或夯实数据结构的读者边读代码边验证算法过程是一份便于随时查阅和二次修改的实用示例集。1. 同样是“比大小”为什么会出现七种排序算法我经常在面试里问候选人一个问题你会哪几种排序算法大多数人都能报出冒泡、快排、归并这些名字能背出复杂度表。但下一个问题是“你觉得哪种排序最好用”很多人就答不上来了。排序算法这门课如果只停留在背代码的层面那就浪费掉了它最重要的价值——它是理解算法设计思维的最佳训练场。先明确一下标题里的“基于比较的排序算法”是什么意思。这类算法的共同特征是通过元素之间两两比较大小来决定它们的先后顺序。冒泡、选择、插入、归并、快排、堆排、希尔全部属于这一类。与之相对的是计数排序、基数排序、桶排序这类非比较排序它们利用数据本身的分布特征可以突破比较排序的复杂度下限但适用场景很有限。比较排序有一个重要的理论结论任意基于比较的排序算法平均时间复杂度都不可能低于 O(n log n)。这个结论背后的直觉是n 个元素的全排列有 n! 种可能而一次两两比较最多只能把可能性缩小一半所以要区分出正确答案至少需要 log₂(n!) 次比较约等于 n log₂ n。也就是说归并排序、快速排序的 O(n log n) 已经是比较排序的天花板了不可能再被突破。但这里有个很有意思的点既然 O(n log n) 已经是极限了那为什么还有这么多算法答案很简单——现实世界里的“好坏”远不是一个平均复杂度就能定义的。稳定性、空间开销、缓存友好度、对数据初始状态的敏感度、实现复杂度这些维度在工程里往往比复杂度数字更重要。理解排序算法本质上就是理解这一组维度之间的取舍关系。这篇文章会把这七种算法拆开来讲但不会按“算法步骤 复杂度表”的教科书模式走。我会把重点放在“它们各自在解决什么问题”“为什么这么设计”“实际工程里谁更靠谱”这几个层面。无论你是刚开始学数据结构的新手还是在准备面试或者工作中需要评估排序方案的选型这篇都值得看完。2. O(n²)三兄弟选择排序、冒泡排序、插入排序的真实定位2.1 选择排序最符合人的直觉但也是最不实用的一个选择排序的思路非常朴素每一轮从未排序区间里挑出最小的元素放到已排序区间的末尾。你可以把它理解成“矮个子先出列”的排队逻辑操作起来不需要额外的内存交换次数是 O(n)最多 n-1 次交换。但它的主要问题是比较次数永远是固定的 n(n-1)/2无论数据是不是基本有序。这意味着一个本来就排好序的数组选择排序依然要老老实实比较完所有元素完全没法利用数据的初始状态。这个缺陷是致命级的。我在实际工作中几乎没见过哪个场景适合用选择排序它更多是教学意义上的“开胃菜”帮你理解“原地排序”和“比较排序”的基本框架。如果你实在想用它唯一合适的场景是数组很小比如几十个元素而且你希望尽量减少交换操作的次数——因为选择排序的交换次数确实比冒泡要少。但这个优势在插入排序面前也不值一提。2.2 冒泡排序教学价值大于工程价值冒泡排序的核心是让较大的元素一次次“冒泡”移动到数组末尾每一轮至少让一个元素到达最终位置。它的优化点在于如果在某一轮扫描中完全没有发生交换说明数组已经有序可以提前结束。对于近乎有序的数据优化后的冒泡排序效率会好一些。但说实话冒泡排序在工程上的存在感也非常低。原因有几个首先它和选择排序一样平均比较次数是 O(n²)而且交换次数更多其次它的数据移动频繁对缓存并不友好。它的唯一优势是实现极其简单是很多教材拿来引出“交换排序”思想的首选。不过教学价值方面冒泡是无可替代的。因为它把“交换”“有序区”“无序区”这些概念展示得很直观初学者最容易理解。如果你是在复习或者带新人入门把它当作思维脚手架没问题但别真的拿它去应对排序任务。2.3 插入排序才是那个“小而美”的实用派插入排序的思想是打扑克牌时的整理手法每拿到一张新牌就把它插入到已经排好序的牌堆里保持手牌有序。时间复杂度同样是 O(n²)但它有两个很关键的特性让它成为 O(n²) 家族里的“实战担当”。第一它对“近似有序”的数据非常快。如果数据已经是基本排好序的插入排序的比较和移动次数接近 O(n)这一点在工程中经常被利用。第二它的常数因子极小当 n 很小时插入排序的实际运行速度甚至能超过快速排序。你可能觉得不可思议O(n²) 怎么可能跑赢 O(n log n)但复杂度管的是趋势不是绝对速度。当 n 只有几十甚至几百时快速排序的递归调用、分区操作这些额外开销反而比插入排序的简单循环要昂贵得多。所以主流语言的标准库排序实现里几乎都会有一段“小数组走插入排序”的兜底逻辑。比如 Java 的Arrays.sort、Python 的 TimSort在数组规模较小时都会切换到插入排序。插入排序的实现也很干净不需要额外空间稳定交换次数能控制在 O(n²) 但实际数据移动量往往远低于选择排序。如果你要手写排序并且数据规模不超过几千直接写插入排序通常是个不错的选择。2.4 三兄弟的横向对比算法平均时间复杂度空间复杂度稳定性特点选择排序O(n²)O(1)不稳定交换次数少但比较次数固定冒泡排序O(n²)O(1)稳定有提前终止优化教学价值高插入排序O(n²)O(1)稳定近有序数据接近 O(n)小数据量实测最快提示如果你还在复习排序至少要把插入排序写得非常熟练。它是后面理解希尔排序的基础也是工程里兜底方案的首选面试手写概率极高。3. 希尔排序被严重低估的“插入排序优化版”3.1 希尔排序在解决什么问题希尔排序的出现直接冲着插入排序的一个痛点去的插入排序虽然在小规模和近有序数据上表现好但面对大规模乱序数据时一次只能把数据移动一个位置效率就崩了。希尔排序的思路是先让数据通过较大步长“宏观有序”再逐步缩小步长最后步长为 1 时本质上就是一次插入排序但此时数据已经接近有序插入排序的效率会非常高。这个思想后来被总结为“分阶段粗调整再精调整”和图像处理里的多尺度策略有点像。希尔排序的实现复杂度比插入排序高不了多少但时间复杂度的常数因子能大幅下降。在工程里它并没有那么常见但在某些特殊场景——比如数据基本有序、或者你不想引入额外空间、又不想承受快排最坏情况风险时它是个不错的中间选项。3.2 增量序列的选择直接影响性能希尔排序最核心的部分不是循环本身而是 gap增量序列怎么选。直接用 n/2、n/4、n/8... 直到 1 的“希尔德增量”实现简单但最坏时间复杂度仍是 O(n²)。如果使用一些经过验证的增量序列比如 Hibbard 序列1, 3, 7, 15, 31...最坏情况能降到 O(n^(3/2))。还有更优的 Sedgewick 序列在工程实测中表现很好平均复杂度可以接近 O(n^(7/6))。我的建议是如果不是做学术研究普通场景里用“除以 2 取整”的增量就够用因为实现简单、不易出错。如果对性能有要求可以直接预计算一个 Hibbard 序列表。但要注意希尔排序是不稳定排序这个性质在某些业务场景下会变成硬伤。3.3 希尔排序的现代应用场景看到这里你也许会问现在 O(n log n) 的排序算法已经这么成熟希尔排序还有必要掌握吗答案是有但定位变了。在嵌入式环境或某些极端内存受限的场景中希尔排序 O(1) 的额外空间和相对简单的实现让它比归并排序更容易落地在数据规模不大但又不是极小的场景它比插入排序快又不像快排那样有递归栈溢出的隐患。另一个价值在教学层面希尔排序是理解“如何通过改进已有算法来解决新问题”的极佳案例。它不是凭空发明新算法而是对插入排序做了一次非常聪明的结构改进。这种思路比算法本身更值得学习。def shell_sort(arr): n len(arr) gap n // 2 while gap 0: for i in range(gap, n): tmp arr[i] j i while j gap and arr[j - gap] tmp: arr[j] arr[j - gap] j - gap arr[j] tmp gap // 2 return arr4. 分治双雄归并排序与快速排序的工程战场4.1 归并排序稳定为王外部排序的基石归并排序是第一个真正意义上把 O(n log n) 做到“保证稳定”的算法。它的思路是分治把数组从中间切成两半递归排好左边和右边再合并两个有序子数组。合并过程需要额外的 O(n) 空间这是它的主要开销。那为什么还要用它因为它有两个不可替代的优点第一它是稳定的。在数据库、金融交易记录这类场景中稳定性不是可有可无的锦上添花而是硬性要求。比如你先按时间排序再按用户 ID 排序如果排序算法不稳定第二次排序会破坏掉第一次的结果业务逻辑就错了。第二它天然适合外部排序。当数据量大到内存装不下必须放在磁盘上时归并排序的合并过程可以分段读取、分段合并不需要一次性把所有数据加载到内存。分布式计算框架里的 Shuffle 排序、数据库的归并连接底层都是归并思想的变种。如果你以后做大数据方向归并排序一定会反复出现。4.2 快速排序partition 设计与 pivot 选择的门道快速排序是实践中最常用的 O(n log n) 排序算法。它的核心是 partition 操作选定一个 pivot基准值把数组重新排列成“小于等于 pivot 的部分 大于 pivot 的部分”然后递归处理两个子区间。听起来简单但细节决定成败。最经典的问题是 pivot 怎么选。如果直接取最后一个元素或第一个元素在数组已经有序的极端情况下快排会退化成 O(n²) 递归深度达到 n直接导致栈溢出。业界常见的解法是“三数取中”取左端、中间、右端三个元素的中位数作为 pivot可以大幅降低最坏情况出现的概率。更激进的做法是随机选 pivot从概率上保证不会稳定退化到 O(n²)。另一个细节是 partition 的方式。Lomuto 分区实现简单适合教学但在有大量重复元素时表现一般。Hoare 分区从两端向中间扫描交换次数更少实际性能更好。我在工程里通常建议用 Hoare 分区加三数取中这是实践检验过的稳健组合。def partition(arr, lo, hi): mid (lo hi) // 2 pivot sorted([arr[lo], arr[mid], arr[hi]])[1] i, j lo, hi while True: while arr[i] pivot: i 1 while arr[j] pivot: j - 1 if i j: return j arr[i], arr[j] arr[j], arr[i] i 1 j - 1快速排序实际最快的原因还有一个常被忽略它的内层循环操作十分简单只是比较和交换数组元素而且访问模式是顺序的缓存命中率远高于堆排序的跳跃式访问。现代 CPU 的缓存行为对性能的影响往往比理论时间复杂度更大这也是快排在绝大多数通用场景里都是默认选择的原因。4.3 双雄对比缓存友好性、稳定性与空间开销维度归并排序快速排序平均时间复杂度O(n log n)O(n log n)最坏时间复杂度O(n log n)O(n²)可用三数取中/随机化缓解空间复杂度O(n) 辅助数组O(log n) 递归栈稳定性稳定不稳定缓存友好性合并时顺序访问较好但需额外数组顺序访问极高效率最优典型场景外部排序、稳定排序需求通用排序、语言标准库默认注意很多人以为归并排序比快速排序“慢”其实在数据量极大、内存充足的场景下归并排序的稳定性优势会让它成为更安全的选择。快排只有在 cache 友好的常规场景里才显著占便宜。5. 堆排序理念满分实战吃亏在哪里5.1 建堆与下滤堆排序的核心操作堆排序的底层是二叉堆一个满足“父节点不小于子节点”的完全二叉树。排序过程分两步先建堆再逐个把堆顶元素放到数组末尾缩小堆范围后重新调整堆结构。核心操作是 sift_down下滤它的作用是当某个节点不满足堆性质时让它在子树里逐层下沉到正确位置。建堆有一个很精妙的性质如果从最后一个非叶子节点开始逐个做 sift_down建堆的时间复杂度是 O(n)而不是大多数初学者以为的 O(n log n)。原因是最底层的节点数量多但下沉距离短高层的节点下沉距离长但数量少加起来是个常数倍的关系。面试里问到建堆复杂度时最好能答出这一层。def sift_down(arr, n, i): largest i left 2 * i 1 right 2 * i 2 if left n and arr[left] arr[largest]: largest left if right n and arr[right] arr[largest]: largest right if largest ! i: arr[i], arr[largest] arr[largest], arr[i] sift_down(arr, n, largest)5.2 堆排序为什么竞争不过快速排序堆排序的理论复杂度是稳定的 O(n log n)最坏情况下也不会退化这是它最大的卖点。但在实际工程里它几乎被快速排序全面压制。原因主要来自缓存局部性堆排序在 sift_down 过程中访问的下标常常从父节点跳到子节点跨度是 2 倍甚至 4 倍关系。数据量一大缓存命中率就很低内存访问的开销超过了比较和交换本身的开销。我做过一个简单的基准测试对 1000 万个随机整数排序快速排序比堆排序快大约 2 到 3 倍而这个差距主要就是缓存行为造成的。所以堆排序在通用排序领域非常吃亏。它的价值不在“排序”而在“维护一个动态的 Top K 集合”和“优先队列”。5.3 堆结构的“复活”优先队列与 Top K虽然堆排序在排序场景失宠但堆这种数据结构本身是绝对核心的。优先队列就是堆的直接实现任务调度、Dijkstra 最短路、哈夫曼编码、事件驱动的定时器全都依赖它。你不需要把整个数组排好序只需要高效地拿到最大或最小的若干元素——这就是堆的主场。比如海量日志里取最新的 100 条错误记录或者排行榜里取 Top 10你完全没必要对全量数据排序。维护一个大小为 K 的最小堆每来一个新元素就堆顶比较比堆顶大的淘汰堆顶并插入新元素最终堆里就是前 K 大。这个操作的时间复杂度是 O(n log K)内存开销 O(K)在数据流场景里几乎是最优解。6. 最终选型面试怎么答生产环境怎么挑6.1 一张表搞定七种算法对比算法平均情况最坏情况空间复杂度稳定性适用场景选择排序O(n²)O(n²)O(1)不稳定教学入门冒泡排序O(n²)O(n²)O(1)稳定教学、近有序小批量数据插入排序O(n²)O(n²)O(1)稳定小规模数据、近有序数据希尔排序O(n^(3/2)) 左右视增量序列而定O(1)不稳定内存受限、中等规模数据归并排序O(n log n)O(n log n)O(n)稳定外部排序、需要稳定性的场景快速排序O(n log n)O(n²)O(log n)不稳定通用排序首选堆排序O(n log n)O(n log n)O(1)不稳定Top K、优先队列场景6.2 主流语言标准库都选了什么很多人不知道语言标准库的排序实现其实极其精妙读懂它们就是在读一份“最优选型”的实战答案。C 的std::sort一般用快速排序加上三数取中和插入排序兜底GCC 的实现还会在递归深度过深时切换成堆排序防止最坏情况。Java 的Arrays.sort对基本类型用双轴快速排序对对象类型用 TimSort归并排序的优化版因为对象排序要求稳定。Python 的内置sorted就是 TimSort它充分利用了数据中天然存在的有序片段对近似有序的数据表现极好。这说明什么没有一种算法能通吃所有场景。标准库的决策逻辑就是根据数据规模、数据类型、稳定性要求来决定走哪条路。我们在工程里也应该养成同样的习惯先弄清需求约束再选算法。6.3 我给初学者的三个实操建议第一个建议是不要急着一口气背七种排序。先把插入排序、快速排序、归并排序练熟这三者覆盖了从 O(n²) 到 O(n log n)、从稳定到不稳定、从原地到非原地的典型组合。剩下的算法理解了思想就能随时写出来。第二个建议是做一次基准测试用自己机器上的真实数据跑一遍看看插入排序在什么规模下会输给快排、堆排序到底比快排慢多少。这些亲测数据会比任何博客里的复杂度表都更让你印象深刻。第三个建议是务必理解清楚稳定性是什么、什么时候必须用。面试答到“这个场景不能破坏上一次排序结果所以要选稳定排序”比机械背诵复杂度表要加分得多。我在实际项目里就遇到过因为用了不稳定排序导致数据错乱的线上事故那种教训不想再经历第二次。最后分享一个我自己的习惯除非有特别明确的理由否则永远优先用语言标准库的排序函数。C 用sortJava 视类型选Arrays.sort或Collections.sortPython 直接用sorted。标准库是无数工程师多年打磨的结果绝大多数情况下比你自己手写的排序更稳、更快。手写排序的价值在于学习和特殊场景兜底而不在于替代标准库。把这些算法吃透之后你会发现不仅排序不再是问题很多数据结构和算法题的思路也一下子通透了。本文还有配套的精品资源点击获取