简介面向算法初学者、编程备考者与软件开发人员的排序算法学习资料系统梳理了选择排序、插入排序、归并排序、快速排序、堆排序、冒泡排序和希尔排序七种基于比较的排序方法从基本思想到代码实现逐一展开。压缩包采用zip格式共18个文件主体为15个Java源文件可直接运行查看每种排序的完整实现另有1份Markdown说明文档用于介绍原理与使用说明并附带License、Gitignore等工程配置文件资源整体仅有18KB轻量便携。目前已有1816人学习该资料。通过拆分源码与文档读者可横向对比七种算法在稳定性、时间复杂度、空间复杂度及适用数据规模上的差异也能结合示例理解不同场景下的选型思路如小规模用插入排序、大规模优先考虑归并或快速排序。这些代码和说明既能辅助课堂学习也可作为算法面试前集中复习的参考资料。 排序算法这个东西大学数据结构课要学一整学期面试又能问一整轮但真到工程里大部分人要么调Arrays.sort()要么写个冒泡糊弄过去。我自己带过一段时间的算法小组发现大家最大的问题不是不理解某个算法而是七种常见比较排序摆在一起的时候脑子是乱的什么时候用哪个为什么快排叫快排却最怕有序数据归并稳定但为什么工程上反而少见这篇文章就把基于比较的七种经典排序——冒泡排序、选择排序、插入排序、希尔排序、归并排序、快速排序、堆排序——从头到尾拉通捋一遍重点放在思路演变和实际选型上。看完你能做到两件事第一手写任意一种不出错第二面试或项目里碰到排序需求能准确判断该用哪一款。适合正在学数据结构的学生也适合准备算法面试的开发者。1. 先捋清楚这七种算法到底在解决什么问题1.1 比较排序的共同起点所谓基于比较的排序指的是只通过元素间的两两比较来获得大小关系进而确定顺序的一类算法。上面那七种全部属于这个范畴。与之相对的是桶排序、基数排序、计数排序这类非比较排序它们利用数据本身的分布特征能做到 O(n) 的时间复杂度但对数据形态有严格要求。比较排序有一个非常重要的理论边界基于比较的排序算法时间复杂度下限是 O(n log n)。这个结论来自决策树模型——每次比较只产生两个结果n 个元素有 n! 种排列可能决策树的深度至少要能容纳 n! 个叶子节点所以最坏情况下的比较次数下界就是 log(n!)近似为 n log n。换句话说你不可能设计出基于比较的、最坏情况下突破 O(n log n) 的排序算法。这个结论看着抽象但它帮我们建立了一个标尺归并、快排、堆排序这些 O(n log n) 的算法已经站在理论最优的等级上了冒泡这种 O(n²) 的算法天花板就低了一大截。1.2 七种算法不是并列关系是演进关系很多人把七种排序当成七个孤立知识点去背这是最吃亏的学习方式。实际上它们之间存在清晰的演进脉络冒泡和选择是最朴素的暴力思路——每轮扫描找出一个最值放到最终位置插入排序则换了个更聪明的局部策略——维护前段有序区间新元素不断插入进来希尔排序是插入排序的改进版——通过大步长预处理让数据基本有序再回归插入归并和快排引入了分治思想——把大问题拆成小问题各自解决后再合并或再分区堆排序则借助了堆这种完全二叉树结构来完成选择过程是选择排序思想 高效数据结构的结合。我用这个演进顺序去教组里的新人效果比按教材顺序冒泡、选择、插入、希尔、归并、快排、堆讲好得多。原因很简单后者是并列关系学完七个知识点脑子里还是一盘散沙前者是递进关系每个新算法都能解释为对上一个算法某个痛点的针对性优化理解成本直线下降。1.3 一个被低估的选型标准稳定性在考虑选哪种排序之前先认识一个常被忽略但工程上极其重要的属性——稳定性。稳定排序的定义是如果两个元素大小相等排序后它们的相对位置保持不变。文字描述很绕举个例子你先按学号排好了学生名单再按成绩排一遍稳定排序会保证同分学生的内部顺序仍然按照学号有序不稳定排序则可能把之前的顺序打乱掉。这个需求在业务系统里太常见了——排行榜、分页列表的多字段排序、Excel 里的多重排序底层都是这个逻辑。七种算法中冒泡、插入、归并是稳定的选择、希尔、快排、堆排序是不稳定的注意这里说的是常规实现。这个属性不能靠死记得从算法的交换方式去理解我们下面每个算法都会点一下它稳或不稳的根本原因。2. 逐个拆解七种排序的核心思路与实现要点2.1 冒泡和选择入门级思路但工程价值有限冒泡排序的思路最简单从头到尾相邻两个元素比较顺序不对就交换一趟下来最大的元素就像气泡一样浮到最后面。重复 n-1 趟就排完了。稳定性取决于交换条件——只有严格a[j] a[j1]时才交换相等的元素不会相对移动所以它是稳定的。一个容易忽略的优化点是提前终止如果某一趟完整扫描下来一次交换都没发生说明序列已经有序可以提前跳出循环。这个优化能让冒泡在近乎有序的数据上跑出接近 O(n) 的复杂度。但就算加上这个优化冒泡的真实地位依然尴尬——它的交换次数在七种算法里最多因为每比较一次可能就要交换一次而交换的开销远比比较昂贵。选择排序的思路是每轮从未排序区间中找到最小元素放到已排序区间的末尾。它把比较和交换分离了每轮只做一次交换这点比冒泡好。但选择排序有一个致命短板不稳定。原因在于交换这个动作——把当前元素和最小值交换时如果中间隔着与当前元素相等的值它们的相对顺序就会被打乱。举个例子数组[5a, 3, 5b]第一轮找到最小值 3 与 5a 交换两个 5 的顺序就变了。注意冒泡虽然慢但它赢在稳定和实现简单少量数据的教学场景里仍然会用到。选择排序的不稳定性并不是说它不能用而是说在需要稳定性的场景里它直接出局。2.2 插入排序和希尔排序小数据量里的真香算法插入排序是大多数人打扑克时整理手牌的习惯动作把每张新牌插入到手里已有牌的合适位置。实现上维护一个有序前缀当前元素从后往前与有序区间比较找到位置后整体后移再插入。这个算法有两个关键特性第一完全有序的数据它只需要 O(n) 次比较效率极高第二它是稳定的因为插入位置是遇到第一个严格大于当前元素的位置等值元素不会越过彼此。希尔排序Shell Sort是插入排序的升级版它的出发点是插入排序在数据近乎有序时效率非常高那能不能先用某种方式把数据变成基本有序再插入希尔的做法是设置一系列递减的增量gap每一轮按 gap 分组组内做插入排序最后 gap1 时就是普通的插入排序。比如数组长度 8gap 序列取 4、2、1第一轮把下标 0 和 4、1 和 5 各自分成一组做插入排序第二轮 gap2 时数据已经比较有序了最后一轮 gap1 时插入排序几乎不需要移动元素。希尔排序的增量序列选择是个经典问题不同的 gap 序列会直接影响时间复杂度。比较经典的序列是n/2, n/4, ..., 1希尔原始版本平均复杂度约为 O(n^1.5)更优的 Sedgewick 序列能达到 O(n^(4/3)) 甚至更好。但希尔排序是不稳定的——因为间隔分组后等值元素可能落在不同组组间移动时会打乱顺序。它的另一个缺点是高度依赖 gap 选择工程上不好调所以实际场景使用率不算高。2.3 归并排序和快速排序分治思想的两条路线归并排序的核心操作是合并两个有序数组。它的分治过程如下把数组一分为二分别排序再归并。归并时用双指针从头比较两个子数组把较小的元素依次放入临时数组最后拷回原数组。时间复杂度恒为 O(n log n)无论数据好坏都一样而且稳定——归并时遇到相等的元素优先取左半边的就能保持稳定性。归并排序的核心代价是额外空间 O(n)这也是它在纯内存场景里不如快排常用的原因。但它有两个不可替代的价值第一是稳定这点让它成为 Java 对象排序、Python 内置排序等对稳定性有要求的场景里的核心部件第二是它对链表的排序天然友好因为链表的随机访问代价高归并恰恰只需要顺序访问。我实习时做过一个外部排序的模块数据量大到放不进内存用的就是归并的多路归并版本——磁盘顺序读、归并、顺序写完全是归并排序的思路这是快排做不到的。快速排序是实践中最常用的 O(n log n) 排序。它的核心是 partition 操作选一个基准值pivot把数组分成左边小于 pivot、右边大于等于 pivot 的两部分然后递归处理左右两个子区间。快排的平均时间复杂度是 O(n log n)常数因子很小而且不需要额外空间只消耗递归栈。它的不稳定来自 partition 中的交换——当 pivot 与某个元素交换时等值元素的相对顺序可能被打乱。快排最怕的是每次选到的 pivot 都恰好是极值比如对完全有序的数组用固定取第一个元素当 pivot退化程度会到 O(n²) 且递归深度到 n直接栈溢出。工程化的解决方法是三数取中median-of-three取首、中、尾三个元素的中位数作为 pivot能大幅降低退化概率还有一个常用策略是递归到小区间时切换成插入排序因为 n 很小的时候递归开销反而不如插入排序直接。这两招在标准库实现里几乎都能看到。2.4 堆排序用数据结构优化选择过程把选择排序的思路再往前推一步——选择排序每轮要找最小最大元素用的是线性扫描所以总复杂度是 O(n²)。如果用一个支持高效取最值的数据结构来替代扫描能不能加快这就是堆排序的出发点把数组原地建成一个大顶堆每轮把堆顶最大值和堆末尾元素交换然后将堆大小减一再对新的堆顶做下沉调整。建堆 O(n)每轮取最大值的调整 O(log n)总复杂度 O(n log n)。堆排序看起来和快排同级但实际表现通常逊于快排第一堆排序的内存访问模式是跳跃式的访问父节点与子节点之间跨度很大对 CPU 缓存不友好第二它每轮做完交换后都要重新调整堆比较和交换次数多于快排常数因子偏大。堆排序的另一个特点是“不稳定”——堆调整过程中父子节点交换很容易跨越等值元素没有任何机制能保证相对顺序。不过堆排序有一个快排没有的优势无论是最好情况还是最坏情况它都是严格的 O(n log n)而且只需要 O(1) 额外空间。在对最坏情况有强制要求的场景比如嵌入式环境、实时系统内核堆排序是比快排更安全的选择。2.5 排序算法实现速写核心框架下面给出七种算法的核心实现框架Python 风格伪代码重点关注主循环和边界条件# 冒泡排序 def bubble_sort(a): n len(a) for i in range(n - 1): swapped False for j in range(n - 1 - i): if a[j] a[j 1]: a[j], a[j 1] a[j 1], a[j] swapped True if not swapped: break # 选择排序 def selection_sort(a): n len(a) for i in range(n - 1): min_idx i for j in range(i 1, n): if a[j] a[min_idx]: min_idx j a[i], a[min_idx] a[min_idx], a[i] # 插入排序 def insertion_sort(a): for i in range(1, len(a)): key a[i] j i - 1 while j 0 and a[j] key: a[j 1] a[j] j - 1 a[j 1] key # 希尔排序 def shell_sort(a): n len(a) gap n // 2 while gap 0: for i in range(gap, n): key a[i] j i while j gap and a[j - gap] key: a[j] a[j - gap] j - gap a[j] key gap // 2 # 归并排序 def merge_sort(a, left, right): if right - left 1: return mid (left right) // 2 merge_sort(a, left, mid) merge_sort(a, mid, right) temp [] i, j left, mid while i mid and j right: if a[i] a[j]: temp.append(a[i]); i 1 else: temp.append(a[j]); j 1 temp.extend(a[i:mid]) temp.extend(a[j:right]) a[left:right] temp # 快速排序 def quick_sort(a, left, right): if right - left 1: return pivot a[right - 1] # 简单版直接取末尾 i left for j in range(left, right - 1): if a[j] pivot: a[i], a[j] a[j], a[i] i 1 a[i], a[right - 1] a[right - 1], a[i] quick_sort(a, left, i) quick_sort(a, i 1, right) # 堆排序 def heapify(a, n, root): largest root left 2 * root 1 right 2 * root 2 if left n and a[left] a[largest]: largest left if right n and a[right] a[largest]: largest right if largest ! root: a[root], a[largest] a[largest], a[root] heapify(a, n, largest) def heap_sort(a): n len(a) for i in range(n // 2 - 1, -1, -1): heapify(a, n, i) for i in range(n - 1, 0, -1): a[0], a[i] a[i], a[0] heapify(a, i, 0)这里快排只写了最简单的固定取尾版方便看逻辑实际工程会用三数取中或者随机 pivot否则有序数组直接退化。3. 横向对比复杂度、稳定性与适用场景速查冒泡最好 O(n)已优化平均 O(n²)最坏 O(n²)空间 O(1)稳定。适合教学演示、数据量极小且要求稳定的场景。选择无论数据好坏都是 O(n²)空间 O(1)不稳定。适合数据量小、不在乎稳定性且希望减少交换开销的场景。插入最好 O(n)有序平均 O(n²)最坏 O(n²)空间 O(1)稳定。适合小规模数据、或者一组已经“基本有序”的数据。希尔最好取决于 gap 序列平均约 O(n^1.3~1.5)最坏 O(n²)空间 O(1)不稳定。适合中等规模且不要求稳定的排序需求。归并最好/平均/最坏都是 O(n log n)空间 O(n)稳定。适合对稳定性有硬性要求、或链表排序、或外部排序。快排最好/平均 O(n log n)最坏 O(n²)可借随机化降低概率空间 O(log n)递归栈不稳定。适合通用大规模排序工程中应用最广。堆排序最好/平均/最坏都是 O(n log n)空间 O(1)不稳定。适合最坏情况复杂度要求严格的嵌入式场景。注意七种算法里只有冒泡、插入、归并是稳定的。如果你正在做一个“先按 A 字段排好再按 B 字段排回来”的多关键字业务需求稳定或不稳定会直接决定结果对不对。4. 工程实践中的排序避坑指南4.1 快排退化与递归深度问题我见过不少同学手写快排代码逻辑没问题一测试就栈溢出。原因几乎都是固定取第一个元素当 pivot然后传入一个已经有序的数组——此时每次 partition 只排好一个元素递归深度变成 n直接爆栈。解决思路有三层先用三数取中降低出现最坏情况的概率如果 still 担心深度可以在递归前先判断right - left是否小于某个阈值小于阈值就用插入排序收尾再激进一点直接使用非递归版本用显式栈模拟递归。工程上大多数标准库采用“快速排序为主 插入排序兜底 递归深度检测”的混合策略C STL 的std::sort就是这种思路。4.2 归并排序的空间优化归并排序标准实现里的临时数组是每层递归都新建的大量碎片化的内存分配会显著拖慢性能。两个可行的优化一是全局只开一个临时数组递归过程中复用它二是在归并前加一个判断——如果a[mid - 1] a[mid]说明两个子数组已经整体有序直接跳过归并步骤。这个优化对接近有序的数据非常有效。即使不做任何优化归并排序在数组排序中的主要缺陷也是空间而不是时间所以当你看到“O(n) 空间”评估时要算清 n 即输入规模这里不是小开销。4.3 语言内置排序到底用的什么很多开发者不知道主流语言的内置排序早就不是单一算法了。Python 的sorted和list.sort()用的是 Timsort——本质是归并排序的改进版充分利用数据中已经存在的“自然有序”片段稳定且自适应所以 Python 列表排序不仅稳遇到近似有序的数据还非常快。Java 的Arrays.sort()对不同类型分了不同策略对基本类型用 Dual-Pivot 快排不稳定但高效对对象类型用 Timsort需要稳定。Go 在 1.19 之后把sort包换成了 pdqsort是“快排 堆排 插入排序”的混合算法。了解这些底层实现的价值在于业务代码里应该优先用语言内置排序因为它们在所有极端情况下都被大量测试过比自己手写体面得多。4.4 手写排序的边界条件自查清单如果面试或作业要求手写排序注意以下几个点空数组、单元素数组要能直接返回所有元素相等时算法不能死循环或越界快排 partition 后左右区间的边界别重合避免无限递归希尔排序的 gap 从n//2起步最后一轮 gap 必须是 1否则排序不完整堆排序建堆时从最后一个非叶子节点n//2 - 1开始且初始化堆后每轮交换完都要调整到“堆长度减一”的子堆。这些坑我都亲手踩过排查的时候最烦的就是排序结果错一个位置而问题通常出在边界条件不是主逻辑。我个人在实际操作中的体会是这七种算法里性价比最高的掌握组合是“插入排序 归并排序 快速排序”。插入排序负责理解“局部有序怎么利用”归并排序负责理解“分治和稳定性”快速排序负责理解“原地 partition 和工程化优化”。剩下四种作为延伸去理解——冒泡是思维的起点选择暴露了稳定性的坑希尔是优化思想的练习堆排序则串起了堆这个重要数据结构。把这七种放进一个演进坐标系里看比孤立背任何一张表格都管用。顺序不必拘谨但理解它们数据结构这座大山的核心就算拿下了。本文还有配套的精品资源点击获取 七种经典比较排序算法全解析：从原理到工程选型
简介面向算法初学者、编程备考者与软件开发人员的排序算法学习资料系统梳理了选择排序、插入排序、归并排序、快速排序、堆排序、冒泡排序和希尔排序七种基于比较的排序方法从基本思想到代码实现逐一展开。压缩包采用zip格式共18个文件主体为15个Java源文件可直接运行查看每种排序的完整实现另有1份Markdown说明文档用于介绍原理与使用说明并附带License、Gitignore等工程配置文件资源整体仅有18KB轻量便携。目前已有1816人学习该资料。通过拆分源码与文档读者可横向对比七种算法在稳定性、时间复杂度、空间复杂度及适用数据规模上的差异也能结合示例理解不同场景下的选型思路如小规模用插入排序、大规模优先考虑归并或快速排序。这些代码和说明既能辅助课堂学习也可作为算法面试前集中复习的参考资料。 排序算法这个东西大学数据结构课要学一整学期面试又能问一整轮但真到工程里大部分人要么调Arrays.sort()要么写个冒泡糊弄过去。我自己带过一段时间的算法小组发现大家最大的问题不是不理解某个算法而是七种常见比较排序摆在一起的时候脑子是乱的什么时候用哪个为什么快排叫快排却最怕有序数据归并稳定但为什么工程上反而少见这篇文章就把基于比较的七种经典排序——冒泡排序、选择排序、插入排序、希尔排序、归并排序、快速排序、堆排序——从头到尾拉通捋一遍重点放在思路演变和实际选型上。看完你能做到两件事第一手写任意一种不出错第二面试或项目里碰到排序需求能准确判断该用哪一款。适合正在学数据结构的学生也适合准备算法面试的开发者。1. 先捋清楚这七种算法到底在解决什么问题1.1 比较排序的共同起点所谓基于比较的排序指的是只通过元素间的两两比较来获得大小关系进而确定顺序的一类算法。上面那七种全部属于这个范畴。与之相对的是桶排序、基数排序、计数排序这类非比较排序它们利用数据本身的分布特征能做到 O(n) 的时间复杂度但对数据形态有严格要求。比较排序有一个非常重要的理论边界基于比较的排序算法时间复杂度下限是 O(n log n)。这个结论来自决策树模型——每次比较只产生两个结果n 个元素有 n! 种排列可能决策树的深度至少要能容纳 n! 个叶子节点所以最坏情况下的比较次数下界就是 log(n!)近似为 n log n。换句话说你不可能设计出基于比较的、最坏情况下突破 O(n log n) 的排序算法。这个结论看着抽象但它帮我们建立了一个标尺归并、快排、堆排序这些 O(n log n) 的算法已经站在理论最优的等级上了冒泡这种 O(n²) 的算法天花板就低了一大截。1.2 七种算法不是并列关系是演进关系很多人把七种排序当成七个孤立知识点去背这是最吃亏的学习方式。实际上它们之间存在清晰的演进脉络冒泡和选择是最朴素的暴力思路——每轮扫描找出一个最值放到最终位置插入排序则换了个更聪明的局部策略——维护前段有序区间新元素不断插入进来希尔排序是插入排序的改进版——通过大步长预处理让数据基本有序再回归插入归并和快排引入了分治思想——把大问题拆成小问题各自解决后再合并或再分区堆排序则借助了堆这种完全二叉树结构来完成选择过程是选择排序思想 高效数据结构的结合。我用这个演进顺序去教组里的新人效果比按教材顺序冒泡、选择、插入、希尔、归并、快排、堆讲好得多。原因很简单后者是并列关系学完七个知识点脑子里还是一盘散沙前者是递进关系每个新算法都能解释为对上一个算法某个痛点的针对性优化理解成本直线下降。1.3 一个被低估的选型标准稳定性在考虑选哪种排序之前先认识一个常被忽略但工程上极其重要的属性——稳定性。稳定排序的定义是如果两个元素大小相等排序后它们的相对位置保持不变。文字描述很绕举个例子你先按学号排好了学生名单再按成绩排一遍稳定排序会保证同分学生的内部顺序仍然按照学号有序不稳定排序则可能把之前的顺序打乱掉。这个需求在业务系统里太常见了——排行榜、分页列表的多字段排序、Excel 里的多重排序底层都是这个逻辑。七种算法中冒泡、插入、归并是稳定的选择、希尔、快排、堆排序是不稳定的注意这里说的是常规实现。这个属性不能靠死记得从算法的交换方式去理解我们下面每个算法都会点一下它稳或不稳的根本原因。2. 逐个拆解七种排序的核心思路与实现要点2.1 冒泡和选择入门级思路但工程价值有限冒泡排序的思路最简单从头到尾相邻两个元素比较顺序不对就交换一趟下来最大的元素就像气泡一样浮到最后面。重复 n-1 趟就排完了。稳定性取决于交换条件——只有严格a[j] a[j1]时才交换相等的元素不会相对移动所以它是稳定的。一个容易忽略的优化点是提前终止如果某一趟完整扫描下来一次交换都没发生说明序列已经有序可以提前跳出循环。这个优化能让冒泡在近乎有序的数据上跑出接近 O(n) 的复杂度。但就算加上这个优化冒泡的真实地位依然尴尬——它的交换次数在七种算法里最多因为每比较一次可能就要交换一次而交换的开销远比比较昂贵。选择排序的思路是每轮从未排序区间中找到最小元素放到已排序区间的末尾。它把比较和交换分离了每轮只做一次交换这点比冒泡好。但选择排序有一个致命短板不稳定。原因在于交换这个动作——把当前元素和最小值交换时如果中间隔着与当前元素相等的值它们的相对顺序就会被打乱。举个例子数组[5a, 3, 5b]第一轮找到最小值 3 与 5a 交换两个 5 的顺序就变了。注意冒泡虽然慢但它赢在稳定和实现简单少量数据的教学场景里仍然会用到。选择排序的不稳定性并不是说它不能用而是说在需要稳定性的场景里它直接出局。2.2 插入排序和希尔排序小数据量里的真香算法插入排序是大多数人打扑克时整理手牌的习惯动作把每张新牌插入到手里已有牌的合适位置。实现上维护一个有序前缀当前元素从后往前与有序区间比较找到位置后整体后移再插入。这个算法有两个关键特性第一完全有序的数据它只需要 O(n) 次比较效率极高第二它是稳定的因为插入位置是遇到第一个严格大于当前元素的位置等值元素不会越过彼此。希尔排序Shell Sort是插入排序的升级版它的出发点是插入排序在数据近乎有序时效率非常高那能不能先用某种方式把数据变成基本有序再插入希尔的做法是设置一系列递减的增量gap每一轮按 gap 分组组内做插入排序最后 gap1 时就是普通的插入排序。比如数组长度 8gap 序列取 4、2、1第一轮把下标 0 和 4、1 和 5 各自分成一组做插入排序第二轮 gap2 时数据已经比较有序了最后一轮 gap1 时插入排序几乎不需要移动元素。希尔排序的增量序列选择是个经典问题不同的 gap 序列会直接影响时间复杂度。比较经典的序列是n/2, n/4, ..., 1希尔原始版本平均复杂度约为 O(n^1.5)更优的 Sedgewick 序列能达到 O(n^(4/3)) 甚至更好。但希尔排序是不稳定的——因为间隔分组后等值元素可能落在不同组组间移动时会打乱顺序。它的另一个缺点是高度依赖 gap 选择工程上不好调所以实际场景使用率不算高。2.3 归并排序和快速排序分治思想的两条路线归并排序的核心操作是合并两个有序数组。它的分治过程如下把数组一分为二分别排序再归并。归并时用双指针从头比较两个子数组把较小的元素依次放入临时数组最后拷回原数组。时间复杂度恒为 O(n log n)无论数据好坏都一样而且稳定——归并时遇到相等的元素优先取左半边的就能保持稳定性。归并排序的核心代价是额外空间 O(n)这也是它在纯内存场景里不如快排常用的原因。但它有两个不可替代的价值第一是稳定这点让它成为 Java 对象排序、Python 内置排序等对稳定性有要求的场景里的核心部件第二是它对链表的排序天然友好因为链表的随机访问代价高归并恰恰只需要顺序访问。我实习时做过一个外部排序的模块数据量大到放不进内存用的就是归并的多路归并版本——磁盘顺序读、归并、顺序写完全是归并排序的思路这是快排做不到的。快速排序是实践中最常用的 O(n log n) 排序。它的核心是 partition 操作选一个基准值pivot把数组分成左边小于 pivot、右边大于等于 pivot 的两部分然后递归处理左右两个子区间。快排的平均时间复杂度是 O(n log n)常数因子很小而且不需要额外空间只消耗递归栈。它的不稳定来自 partition 中的交换——当 pivot 与某个元素交换时等值元素的相对顺序可能被打乱。快排最怕的是每次选到的 pivot 都恰好是极值比如对完全有序的数组用固定取第一个元素当 pivot退化程度会到 O(n²) 且递归深度到 n直接栈溢出。工程化的解决方法是三数取中median-of-three取首、中、尾三个元素的中位数作为 pivot能大幅降低退化概率还有一个常用策略是递归到小区间时切换成插入排序因为 n 很小的时候递归开销反而不如插入排序直接。这两招在标准库实现里几乎都能看到。2.4 堆排序用数据结构优化选择过程把选择排序的思路再往前推一步——选择排序每轮要找最小最大元素用的是线性扫描所以总复杂度是 O(n²)。如果用一个支持高效取最值的数据结构来替代扫描能不能加快这就是堆排序的出发点把数组原地建成一个大顶堆每轮把堆顶最大值和堆末尾元素交换然后将堆大小减一再对新的堆顶做下沉调整。建堆 O(n)每轮取最大值的调整 O(log n)总复杂度 O(n log n)。堆排序看起来和快排同级但实际表现通常逊于快排第一堆排序的内存访问模式是跳跃式的访问父节点与子节点之间跨度很大对 CPU 缓存不友好第二它每轮做完交换后都要重新调整堆比较和交换次数多于快排常数因子偏大。堆排序的另一个特点是“不稳定”——堆调整过程中父子节点交换很容易跨越等值元素没有任何机制能保证相对顺序。不过堆排序有一个快排没有的优势无论是最好情况还是最坏情况它都是严格的 O(n log n)而且只需要 O(1) 额外空间。在对最坏情况有强制要求的场景比如嵌入式环境、实时系统内核堆排序是比快排更安全的选择。2.5 排序算法实现速写核心框架下面给出七种算法的核心实现框架Python 风格伪代码重点关注主循环和边界条件# 冒泡排序 def bubble_sort(a): n len(a) for i in range(n - 1): swapped False for j in range(n - 1 - i): if a[j] a[j 1]: a[j], a[j 1] a[j 1], a[j] swapped True if not swapped: break # 选择排序 def selection_sort(a): n len(a) for i in range(n - 1): min_idx i for j in range(i 1, n): if a[j] a[min_idx]: min_idx j a[i], a[min_idx] a[min_idx], a[i] # 插入排序 def insertion_sort(a): for i in range(1, len(a)): key a[i] j i - 1 while j 0 and a[j] key: a[j 1] a[j] j - 1 a[j 1] key # 希尔排序 def shell_sort(a): n len(a) gap n // 2 while gap 0: for i in range(gap, n): key a[i] j i while j gap and a[j - gap] key: a[j] a[j - gap] j - gap a[j] key gap // 2 # 归并排序 def merge_sort(a, left, right): if right - left 1: return mid (left right) // 2 merge_sort(a, left, mid) merge_sort(a, mid, right) temp [] i, j left, mid while i mid and j right: if a[i] a[j]: temp.append(a[i]); i 1 else: temp.append(a[j]); j 1 temp.extend(a[i:mid]) temp.extend(a[j:right]) a[left:right] temp # 快速排序 def quick_sort(a, left, right): if right - left 1: return pivot a[right - 1] # 简单版直接取末尾 i left for j in range(left, right - 1): if a[j] pivot: a[i], a[j] a[j], a[i] i 1 a[i], a[right - 1] a[right - 1], a[i] quick_sort(a, left, i) quick_sort(a, i 1, right) # 堆排序 def heapify(a, n, root): largest root left 2 * root 1 right 2 * root 2 if left n and a[left] a[largest]: largest left if right n and a[right] a[largest]: largest right if largest ! root: a[root], a[largest] a[largest], a[root] heapify(a, n, largest) def heap_sort(a): n len(a) for i in range(n // 2 - 1, -1, -1): heapify(a, n, i) for i in range(n - 1, 0, -1): a[0], a[i] a[i], a[0] heapify(a, i, 0)这里快排只写了最简单的固定取尾版方便看逻辑实际工程会用三数取中或者随机 pivot否则有序数组直接退化。3. 横向对比复杂度、稳定性与适用场景速查冒泡最好 O(n)已优化平均 O(n²)最坏 O(n²)空间 O(1)稳定。适合教学演示、数据量极小且要求稳定的场景。选择无论数据好坏都是 O(n²)空间 O(1)不稳定。适合数据量小、不在乎稳定性且希望减少交换开销的场景。插入最好 O(n)有序平均 O(n²)最坏 O(n²)空间 O(1)稳定。适合小规模数据、或者一组已经“基本有序”的数据。希尔最好取决于 gap 序列平均约 O(n^1.3~1.5)最坏 O(n²)空间 O(1)不稳定。适合中等规模且不要求稳定的排序需求。归并最好/平均/最坏都是 O(n log n)空间 O(n)稳定。适合对稳定性有硬性要求、或链表排序、或外部排序。快排最好/平均 O(n log n)最坏 O(n²)可借随机化降低概率空间 O(log n)递归栈不稳定。适合通用大规模排序工程中应用最广。堆排序最好/平均/最坏都是 O(n log n)空间 O(1)不稳定。适合最坏情况复杂度要求严格的嵌入式场景。注意七种算法里只有冒泡、插入、归并是稳定的。如果你正在做一个“先按 A 字段排好再按 B 字段排回来”的多关键字业务需求稳定或不稳定会直接决定结果对不对。4. 工程实践中的排序避坑指南4.1 快排退化与递归深度问题我见过不少同学手写快排代码逻辑没问题一测试就栈溢出。原因几乎都是固定取第一个元素当 pivot然后传入一个已经有序的数组——此时每次 partition 只排好一个元素递归深度变成 n直接爆栈。解决思路有三层先用三数取中降低出现最坏情况的概率如果 still 担心深度可以在递归前先判断right - left是否小于某个阈值小于阈值就用插入排序收尾再激进一点直接使用非递归版本用显式栈模拟递归。工程上大多数标准库采用“快速排序为主 插入排序兜底 递归深度检测”的混合策略C STL 的std::sort就是这种思路。4.2 归并排序的空间优化归并排序标准实现里的临时数组是每层递归都新建的大量碎片化的内存分配会显著拖慢性能。两个可行的优化一是全局只开一个临时数组递归过程中复用它二是在归并前加一个判断——如果a[mid - 1] a[mid]说明两个子数组已经整体有序直接跳过归并步骤。这个优化对接近有序的数据非常有效。即使不做任何优化归并排序在数组排序中的主要缺陷也是空间而不是时间所以当你看到“O(n) 空间”评估时要算清 n 即输入规模这里不是小开销。4.3 语言内置排序到底用的什么很多开发者不知道主流语言的内置排序早就不是单一算法了。Python 的sorted和list.sort()用的是 Timsort——本质是归并排序的改进版充分利用数据中已经存在的“自然有序”片段稳定且自适应所以 Python 列表排序不仅稳遇到近似有序的数据还非常快。Java 的Arrays.sort()对不同类型分了不同策略对基本类型用 Dual-Pivot 快排不稳定但高效对对象类型用 Timsort需要稳定。Go 在 1.19 之后把sort包换成了 pdqsort是“快排 堆排 插入排序”的混合算法。了解这些底层实现的价值在于业务代码里应该优先用语言内置排序因为它们在所有极端情况下都被大量测试过比自己手写体面得多。4.4 手写排序的边界条件自查清单如果面试或作业要求手写排序注意以下几个点空数组、单元素数组要能直接返回所有元素相等时算法不能死循环或越界快排 partition 后左右区间的边界别重合避免无限递归希尔排序的 gap 从n//2起步最后一轮 gap 必须是 1否则排序不完整堆排序建堆时从最后一个非叶子节点n//2 - 1开始且初始化堆后每轮交换完都要调整到“堆长度减一”的子堆。这些坑我都亲手踩过排查的时候最烦的就是排序结果错一个位置而问题通常出在边界条件不是主逻辑。我个人在实际操作中的体会是这七种算法里性价比最高的掌握组合是“插入排序 归并排序 快速排序”。插入排序负责理解“局部有序怎么利用”归并排序负责理解“分治和稳定性”快速排序负责理解“原地 partition 和工程化优化”。剩下四种作为延伸去理解——冒泡是思维的起点选择暴露了稳定性的坑希尔是优化思想的练习堆排序则串起了堆这个重要数据结构。把这七种放进一个演进坐标系里看比孤立背任何一张表格都管用。顺序不必拘谨但理解它们数据结构这座大山的核心就算拿下了。本文还有配套的精品资源点击获取