一、起源:有序与可定位带来的收益

1.1 有序是一种可反复使用的预处理

无序数据只能逐项检查。把数据整理成有序序列之后,一批原本需要线性甚至平方级代价的操作获得结构性收益:

  • 二分定位。有序序列支持每次排除一半,查找代价从 O(n) 降为 O(log n)。10⁶ 个元素上,顺序查找平均需要约 5×10⁵ 次比较,二分查找最多 20 次。
  • 去重。有序之后只需比较相邻元素,线性一遍即可完成;无序时用嵌套比较是 O(n²),用散列表是期望 O(n) 但需要额外空间。
  • 区间查询。有序序列中同一区间内的元素在位置上连续,用两次二分即可圈出上下界;配合前缀和或前缀最值,区间统计可以从 O(n) 降为 O(1)。任意区间的动态查询属于另一类结构,见 线段树与并查集。
  • 归并。两个有序序列合并只需一次线性扫描,代价 O(m + n);这一操作既是归并排序的基础,也是多路归并、联结与流式合并的通用原语。
  • 其他派生收益。最值、第 k 小、中位数、最大差值、交集与并集、找重复元素,都在有序前提下获得更简单或更快的解法。

这些收益的共同来源是:有序性把"元素之间的全部两两关系"压缩为"位置关系"。一旦任意两个元素的大小可以由下标推出,逐个比较就被算术定位取代。

1.2 排序在工程中的位置

排序在系统中很少作为最终目的出现,它多数时候是其他操作的预处理阶段:

  • 聚合。分组统计前先按分组键排序,同一组的记录在位置上连续,一次扫描即可完成统计,无需为每组维护独立的容器。数据库的排序聚合、MapReduce 的 shuffle 与 sort 阶段都属此类。
  • 联结。两张表按同一键做等值联结时,若两侧都已按该键有序,可以双指针线性推进完成匹配,代价与输出规模同阶;这就是排序合并联结(sort-merge join)与分布式联结的依据。
  • 索引与唯一性。数据库的 B+ 树索引、唯一约束的判定,都以键的有序组织为前提,见 B+ 树与索引。索引把"排序一次"的成本摊到多次查询上。
  • 输出与展示。榜单、分页列表、日志按时间倒序,都是对外的可读性要求。
  • 取部分结果。只需要前 K 个时不必全排序,堆或快速选择能以更低代价给出结果(3.4 节)。

因此排序的代价需要放在整条链路中衡量:一次 O(n log n) 的预处理若能被后续 m 次查询复用,单次查询就摊到了 O((n log n)/m);若每次查询都重新排序,则属于 3.5 节所列的常见误用。

1.3 查找的前提与结构选择

查找要解决的是"定位某个键",可选手段的前提与代价差异很大:

手段 代价 前提 不支持的能力
顺序查找 O(n) 无 大规模数据下的效率
二分查找 O(log n) 有序 + 随机访问 频繁插入删除(维护有序的代价)
平衡搜索树 / 跳表 O(log n) 键可比较 常数因子较大、节点开销
散列表 期望 O(1) 键可实现散列,分布良好 范围查询、有序遍历、最接近的键
B+ 树 O(log n)(含磁盘访问) 数据在外部存储 内存内的常数优势

同一份"按键查找"的规范可以对应多种实现,选择取决于附加需求:需要范围或邻近查询时有序结构无法被散列表替代,只判断存在性时散列表的常数优势更明显。这层区分见 二叉树与二叉搜索树、散列表 与 抽象数据类型(ADT)。二分查找是其中最便宜的一种(不需要额外结构),代价是要求数据已经有序且可按下标随机访问。

1.4 数据特征决定算法选择

不存在"最快的排序"。算法的实际表现依赖输入的数据特征:

  • 近乎有序。插入排序、冒泡排序与归并类实现在这类输入上接近线性。
  • 大量重复键。二路分区会把相等的元素反复交换,三路分区可以跳过等于枢轴的整段。
  • 键值域小而密集。计数排序可以不比较键,达到线性代价。
  • 数据规模与内存的关系。数据超过内存容量时必须借助外部排序,可用的算法集合随之改变。
  • 稳定性要求。多关键字排序要求保持相等键的原始相对顺序,可选项因此收窄。
  • 只需前 K 个。全排序做了大量无用工作,堆或划分选择更省。

由此确定本文的组织方式:先建立描述算法性质的维度与理论下界,再逐个说明十类算法的原理与适用边界,最后落到实现要点、实测方法与选型。


二、原理

2.1 排序算法的性质维度

比较两个排序实现时,只看时间复杂度的量级不足以决策。需要同时确认以下几组性质。

2.1.1 稳定性

定义:若序列中存在两个键相等的元素,排序前 a 在 b 之前,排序后 a 仍在 b 之前,则该排序算法稳定;否则不稳定。

稳定的价值体现在多关键字排序:要按次要键、主要键两级排序时,可以先按次要键排一遍,再用稳定排序按主要键排一遍,最终结果中主要键相同的元素保持次要键的顺序。不稳定的算法无法这样组合——相等的主要键会让次要键的顺序丢失。这一操作也可以改为在比较器中串联两个键,代价是每次比较都要访问两个字段,且需要保证比较器本身的一致性。

几个与稳定性有关的事实:

  • 稳定性只在存在相等键时才可观察。键互不相同的输入上,稳定与不稳定实现的输出完全一致,因此缺陷容易被测试用例漏掉。
  • 稳定不等于更好。稳定的代价通常是额外空间(归并类)或额外的比较与搬移;基本类型数组的排序通常不关心稳定性,因为相等的数值彼此不可区分。
  • 链表上的插入排序与归并排序可以做到稳定且近乎原地,而数组上的原地快速排序与堆排序都不稳定。稳定性的可达性与存储结构相关。
  • 需要稳定而算法不稳定的补救方式:在比较器中加入次序键(例如原始下标),把"相等"变为"可区分",代价是比较次数增加。

2.1.2 原地性

原地(in-place) 指额外空间为 O(1) 或 O(log n)(仅递归栈)。原地性影响三件事:

  1. 内存峰值。非原地算法需要与输入等长的辅助空间,数据量大时这一项可能成为约束。
  2. 分配与回收成本。辅助数组的申请与释放、以及随之而来的垃圾回收压力,在时间上表现为常数项的增加。
  3. 缓存局部性。辅助数组会与输入数组竞争缓存容量,双向读写使缓存行更频繁地被换出。

原地算法未必总是更省:快速排序的递归栈在最坏情况下为 O(n),堆排序虽然是严格的 O(1) 额外空间,但其访问模式对缓存不友好,实测常数因子通常反而更大。

2.1.3 比较与非比较

  • 比较排序:只通过元素之间的比较获取顺序信息,适用面最广,只要键可比较即可。其代价存在 Ω(n log n) 的下界(2.2 节)。
  • 非比较排序:直接利用键的取值结构(整数范围、进制位、分布的区间)确定位置,不需要比较,可以达到线性代价。代价是适用范围受限,对键的类型与分布有明确要求。

这一区分决定了优化方向:比较排序已达下界,进一步优化只能落在常数因子、缓存行为与稳定性上;非比较排序的收益与前提绑定,前提不成立时会退化甚至失效。

2.1.4 适应性与三类复杂度

适应性(adaptive) 指算法能利用输入中已有的有序性来减少工作量。带提前退出标志的冒泡排序、插入排序、希尔排序、Timsort 都是适应性的;选择排序、堆排序与经典快速排序不是。判断依据是最好情况复杂度是否优于平均情况。

复杂度需要按三个口径分别给出,并注明空间:

口径 含义 用途
最好情况 最有利输入下的代价 说明是否存在廉价路径与适应性
平均情况 在输入分布假设下的期望 反映典型表现,结论依赖分布假设
最坏情况 最不利输入下的代价 延迟上限与容量规划的依据

三个口径的关系、分布假设的必要性以及摊还分析的口径见 复杂度与算法分析。比较排序中,堆排序与归并排序的三类口径一致,快速排序与插入排序则存在明显落差。

2.2 比较排序的下界

任何仅通过比较元素来确定顺序的排序算法,都需要 Ω(n log n) 次比较。论证方式是决策树:

n 个元素共有 n! 种可能的初始排列,算法必须把每一种都引导到正确的输出排列上。
决策树的每个内部节点是一次比较(两种结果,即两个分支),每个叶节点对应一种输出排列。
要覆盖全部 n! 种情况,叶节点数不少于 n!。
高度为 h 的二叉树最多有 2^h 个叶节点,因此 2^h ≥ n!。
取对数:h ≥ log₂(n!) ≥ log₂((n/2)^(n/2)) = (n/2)·log₂(n/2)
即 h = Ω(n log n)

由这条论证可以确定三件事:

  1. 归并排序与堆排序已经达到该下界,在比较模型内不存在量级上的改进空间,差异只可能来自常数因子、缓存行为与辅助空间。
  2. 绕过下界必须改变前提。计数排序、基数排序、桶排序不依赖比较,利用的是键的取值结构,因此能达到 O(n + k) 或 O(d·n) 一类代价。它们并不违反前述结论,因为其正确性建立在"键的取值范围有限"或"分布已知"这些额外信息上。
  3. 下界不约束稳定性、空间与常数。达到 O(n log n) 的实现之间,辅助空间可以是 O(1)(堆排序)也可以是 O(n)(归并排序),稳定性可以是不稳定也可以是稳定。下界只说明"比较次数的量级无法再降"。

决策树模型与下界论证的完整口径、以及它与复杂度分析其他结论的关系见 复杂度与算法分析 中理论的边界一节。

2.3 基础排序:冒泡、选择、插入、希尔

四者都是 O(n²) 量级的简单算法。它们在现代工程中不直接用于大规模数据,但作为混合排序的收尾阶段、近乎有序数据的专用解法与小规模输入的选择仍然常见。

2.3.1 冒泡排序

逐对比较相邻元素,逆序则交换。每完成一轮,当前未排序部分的最大元素被"冒"到末尾,因此 n−1 轮之后整体有序。

  • 交换次数等于逆序对数。逆序对是满足 i < j 且 a[i] > a[j] 的下标对。每交换一次相邻的逆序对,逆序对数恰好减少 1,因此冒泡排序的工作量与输入的无序程度直接相关。
  • 适应性:若某一轮没有发生任何交换,说明序列已有序,可以提前结束。带这一标志的最好情况代价为 O(n)(已有序输入只需一轮扫描)。
  • 稳定性:只在严格逆序时交换,相等元素不会被交换,因此稳定。
  • 代价:比较次数约 n(n−1)/2,交换次数等于逆序对数,平均约 n²/4。
  • 缺点:即使只差一个元素也需要 n 轮,且每轮都要扫描;插入排序可以用同样的交换次数把元素一步"长距离"移动到位,因此实践中冒泡排序被插入排序取代。

2.3.2 选择排序

每轮线性扫描未排序部分找最小值,与未排序部分的首位交换。

  • 交换次数为 n−1,是所有交换类排序中最少的。这一性质在元素移动代价极高时才有意义(例如元素是大对象且无法改为排序引用)。
  • 比较次数恒为 n(n−1)/2,与输入无关,因此没有适应性;有序输入与逆序输入的耗时相同。
  • 不稳定。交换发生在未排序部分的首位与被选中的最小值之间,这是一次跨越大量元素的长距离交换,可能把相等元素的相对顺序颠倒。例如 [2a, 2b, 1] 第一轮把 1 与 2a 交换,得到 [1, 2b, 2a],两个 2 的顺序被改变。
  • 适用面:只用于交换代价远大于比较代价、且不要求稳定性的场合;教学上用于说明"找最值"与"就位"分离的思路。

2.3.3 插入排序

把序列看作"已排序前缀 + 未排序后缀",每次取后缀首个元素,在前缀中从后向前找到插入位置,同时把大于它的元素整体后移一位。

  • 近乎有序数据上的优势是插入排序最重要的性质。已有序输入下,每个元素只需与前一个元素比较一次即可判定无需移动,总代价为 O(n);一般情形下,移动与比较的次数都与逆序对数成正比,因此代价约为 O(n + I),I 为逆序对数。数据"几乎排好、只有少量元素错位"时 I 远小于 n²,插入排序的实际耗时可以低于任何 O(n log n) 的复杂实现。
  • 稳定性:只有严格大于待插入元素时才后移,相等元素保持原有相对顺序。
  • 原地:除一个暂存变量外不需要额外空间;链表实现下可以把节点直接摘链插入,代价同样是 O(I) 且不需要搬移。
  • 代价:最坏与平均 O(n²)(逆序输入下每个元素移动到最前端),最好 O(n)。
  • 工程地位:所有主流标准库的排序实现都在小区间(常见阈值 7 至 16 个元素,部分实现更大)切换到插入排序。原因是小规模下 O(n²) 与 O(n log n) 的差距被循环开销与递归调用开销覆盖,插入排序的常数因子最小(复杂度与算法分析 中理论与实测的差异一节)。此外,插入排序是稳定的,可以作为稳定排序的收尾阶段而不破坏整体稳定性。

2.3.4 希尔排序

插入排序每次只能把元素向前移动一位,逆序元素距离很远时移动次数等于距离。希尔排序的思路是先用较大的步长做插入排序,使元素可以跳跃式地接近目标位置,再逐步缩小步长,最终步长为 1 时序列已接近有序,此时插入排序代价接近 O(n)。

  • 增量序列决定复杂度。步长从 h 开始、每轮按规则缩小,各轮分别对"间隔为 h 的子序列"做插入排序。
  • Shell 原始序列 h = n/2、n/4、…、1:最坏 O(n²),最坏输入可构造。
  • Knuth 序列 h = 3h + 1(1、4、13、40、…):最坏 O(n^1.5)。
  • Hibbard 序列 h = 2^k − 1:最坏 O(n^1.5)。
  • Sedgewick 序列:最坏约 O(n^(4/3))。
  • 代价:最好情况 O(n log n)(有序输入下每轮都是线性扫描),最坏情况取决于序列,介于 O(n^1.3) 与 O(n²) 之间。精确的最坏界与增量序列的关系至今没有完全确定的结论,因此希尔排序的复杂度结论必须与所用序列一起给出。
  • 稳定性:不稳定。跨步长的交换会把相等元素推过彼此。
  • 原地:额外空间 O(1)。
  • 适用面:实现简单、原地、对中等规模(数千至数万)数据表现良好,且不需要额外的辅助空间;在嵌入式或对内存敏感的场景常作为快速排序的替代。自适应性的强弱取决于序列,Knuth 序列在近乎有序输入上接近线性。

2.4 分治排序:归并排序与快速排序

两者都采用分治框架:把序列分成两部分,分别排序,再合并结果。差别在于"分解"与"合并"哪一步承担主要工作。

2.4.1 归并排序

过程:把序列从中点分成两半,递归排序两半,再把两个有序段合并为一个有序段。

  • 分解几乎不花费代价(取中点),代价集中在合并:一次线性扫描,逐次取两段头部中较小的元素写入辅助数组。
  • 递归式 T(n) = 2T(n/2) + O(n),由递归树或主定理得 O(n log n);每层合并的总代价为 O(n),层数为 log n。推导见 复杂度与算法分析 中递归式一节。分治框架的三个步骤、划分平衡与合并代价的权衡、归并排序与快速排序在分治中的位置见 递归与分治。
  • 稳定性:合并时若两段头部键相等,先取左段的元素,则相等元素的相对顺序不变,因此稳定。判断条件必须写成"右段元素严格小于左段元素时才先取右段",写成小于等于会破坏稳定性。
  • 空间代价:数组实现需要与输入等长的辅助数组,额外空间 O(n),是典型的非原地排序。若递归中每次都分配新数组,分配与回收的次数会随层数增长,实现上应在递归外分配一次并复用。链表实现只需 O(log n) 的递归栈,因为合并可以直接改指针。
  • 最好与最坏情况一致:都是 O(n log n),代价与输入分布无关,因此没有适应性(可以加入"若两段已整体有序则跳过合并"的判定来获得部分适应性)。
  • 缓存友好:合并是顺序扫描与顺序写入,硬件预取有效;这也是归并排序在实测常数上通常优于堆排序的原因。
  • 外部排序的基础:归并是唯一可以自然地"跨内存批次"进行的排序方式——把内存中排好的多个有序段合并为更大的段,无需随机访问整个数据集(2.9 节)。
  • 额外优点:天然的并行结构(两半可以并行排序,各层合并也可并行);对链表排序无需随机访问。

2.4.2 快速排序

过程:选取一个枢轴(pivot),把序列划分为"小于枢轴"与"大于枢轴"两部分,枢轴就位后再对两侧递归。

  • 分区是核心。常见两种写法:
  • Lomuto 分区:以末元素为枢轴,用单个指针 i 维护"小于枢轴区"的右边界,从左向右扫描,遇到小于枢轴的元素就与 i 处交换。写法简单、易验证,但对已有序输入退化的风险高,且在键大量重复时交换次数多。
  • Hoare 分区:左右双指针向中间推进,各自找到违反条件(左侧不小于枢轴、右侧不大于枢轴)的元素后交换。比较次数更少(平均约 3n/2 外还有约 n/6 的交换),两侧枢轴位置是"分割点"而非枢轴最终位置,边界处理稍复杂。
  • 枢轴选择决定最坏情况。
  • 固定取首元素或末元素:输入已有序或逆序时每次划分极不平衡(每次只减少一个元素),递归式退化为 T(n) = T(n−1) + O(n),总代价 O(n²),同时递归深度达到 n。这正是最坏输入被构造的方式。
  • 随机化:随机选取枢轴或先整体打乱,使最坏输入不再固定存在,期望代价 O(n log n)。随机化的价值在于把"存在确定的坏输入"变为"坏输入的概率极低",并不能消除 O(n²) 的最坏界。
  • 三数取中:取首、中、末三个元素的中位数作为枢轴,对近乎有序输入有明显改善,且常数开销小于随机化。
  • 三路分区处理大量重复键。把序列分为"小于枢轴""等于枢轴""大于枢轴"三段(荷兰国旗问题),等于枢轴的元素一次到位,后续递归只处理严格小于与严格大于的部分。当输入中重复键比例很高时,二路分区会把相等的元素反复搬移并产生大量不平衡划分,三路分区可以直接跳过等于段,使代价与"不同键的个数"相关。极端情形(所有键相等)下三路快排一次分区即结束,代价 O(n)。
  • 缓存友好。划分是顺序扫描加原地交换,工作集集中在当前区段内,与数组的内存布局一致;加上原地、无辅助分配、常数因子小,它是实测中平均最快的比较排序。代价是访问模式比归并更分散(交换是跳跃的),但整体仍优于堆排序。
  • 最坏情况的工程缓解:随机化或三数取中处理不平衡划分;小区间切换插入排序减少递归层数;三路分区处理重复键;递归时只对较短的一侧递归、较长的一侧用循环继续(尾递归消除),把递归深度控制在 O(log n) 以内。标准库另外使用"递归深度超过阈值则切换堆排序"的兜底策略,保证最坏 O(n log n)(2.7 节)。
  • 不稳定:划分过程中的长距离交换会跨越大量元素,相等键的相对顺序无法保持。

2.5 堆排序

堆排序利用堆的"堆顶即最值"这一性质完成排序,流程是"建堆 + 反复取堆顶":

  1. 对原数组执行自底向下沉(heapify)建成大顶堆,代价 O(n);
  2. 重复 n−1 次:把堆顶(当前最大值)与堆的末尾元素交换,堆的逻辑大小减一,再对新堆顶执行下沉。每次取顶的代价为 O(log n)。

总代价 O(n log n),且最坏情况同样如此。三项性质:

  • 原地:全程在原数组上交换,额外空间 O(1)(下沉写成循环而非递归时无栈开销)。
  • 不稳定:堆顶与末尾的交换跨越大量元素,下沉过程中相等键的左右子树位置也不受约束。
  • 缓存不友好:下沉时每层访问的下标跨度与前一层不同,父子节点常落在不同的缓存行,无法被顺序预取覆盖。三者的时间量级相同,但实测排序常数通常为快速排序 < 归并排序 < 堆排序。

堆的构建过程、下沉与上浮的下标关系、O(n) 建堆的级数推导以及堆排序与其他排序的对比见 堆与优先队列。堆排序的典型用途集中在两类场景:内存受限且要求最坏时间有保证;或者只需要部分有序的结果(例如取前 K 个,此时不需要全排序,见 3.4 节)。

2.6 非比较排序:计数、基数、桶

三类非比较排序都通过"直接按键确定位置"绕过比较模型的下界,因此可以达到线性代价。前提各不相同,前提不成立时会退化。

2.6.1 计数排序

适用前提:键是整数(或可映射为整数),且取值范围 [0, k) 中的 k 与元素个数 n 同阶或更小。

过程:

  1. 统计每个键出现的次数,放入长度为 k 的计数数组;
  2. 对计数数组求前缀和,使 count[v] 表示"键不大于 v 的元素个数";
  3. 从后向前遍历原序列,把元素按 count 定位写入输出数组,并把对应计数减一。

关键点:

  • 步骤 3 必须从后向前,这样相等键中后面出现的元素先被放置到更靠后的位置,相对顺序得以保持,排序才是稳定的。基数排序依赖这一稳定性。
  • 代价:时间 O(n + k),空间 O(k)(不要求稳定时可以省去输出数组,但仍需计数数组)。
  • 边界:k 与 n 无关且很大时(例如键是 32 位整数),O(k) 的空间与时间都不可接受,此时计数排序不适用;键为负数时需要先做偏移映射。
  • 与下界的关系:它不使用比较,而是利用"键的取值范围有限"这一额外信息,因此可以突破 Ω(n log n)。

2.6.2 基数排序

适用前提:键可以按位(十进制位、字节或二进制位)拆分,且位数 d 有限。

LSD(最低位优先)过程:从最低有效位开始,逐位对全部元素做一次稳定的计数排序(基数为 b 时计数数组长度为 b),直到最高位处理完毕。

  • 稳定性是正确性的前提。低位已排好的相对顺序必须被高位排序保留;一旦某一轮使用的子过程不稳定,低位的结果立刻失效。因此基数排序的实现必须使用稳定计数排序,或改为把元素按桶顺序依次串联(桶内保持入桶顺序)。
  • 代价:O(d·(n + b))。取 b = 10 时,d 为最大十进制位数(约 log₁₀ max);取 b = 256 时按字节处理,d 为字节数(如 32 位整数为 4 轮),此时每轮常数更小。b 的选择是"轮数"与"单轮计数数组大小"的折中。
  • 不要求数字比较,因此适合定长整数、定长编码、固定宽度字符串(如身份证号、时间戳、IP 地址)。变长字符串的定长补齐会带来额外开销,此时可用 MSD 基数排序(按最高位先分桶,再对每个桶递归),它与字典树、三路字符串快排属于同一类思路。
  • 空间:需要计数数组(O(b))与输出数组(O(n))。
  • 稳定性:LSD 实现是稳定的,这也是它的正确性要求。负数需要按符号位特殊处理(例如先按符号分两组再分别处理)。

2.6.3 桶排序

适用前提:键可以映射到一个区间,且在该区间上分布近似均匀。

过程:把区间划分为若干等宽子区间(桶),按键把元素分配到对应桶内,对每个桶内部排序,再按桶的顺序依次串联。

  • 代价:元素分配与串联是 O(n);若 n 个元素均匀分布在 n 个桶中,每个桶平均一个元素,桶内排序总代价 O(n),因此期望 O(n)。最坏情况是分布严重不均:全部元素落入同一个桶,退化为单次桶内排序,代价取决于所用算法(若桶内用插入排序则可能达到 O(n²))。
  • 稳定性:取决于桶内排序是否稳定,以及串联时是否保持桶内顺序。
  • 空间:O(n + k),k 为桶数;需要额外的桶容器,通常按链表或动态数组实现。
  • 与基数排序的关系:基数排序可以看作"按位分桶"的多轮桶排序,桶的划分依据是某一位的值而不是区间;桶排序可以看作一次性的、按区间划分的分配式排序。
  • 工程用途:数据分布已知且均匀时的线性排序(如按成绩分段、按哈希值分片);也是分布式排序中"按范围分片、各分片独立排序"的思路来源。

2.6.4 线性时间的前提与边界

三类算法的对照:

算法 前提 时间 空间 稳定 失效条件
计数排序 键为小范围整数 O(n + k) O(k) 稳定 k 远大于 n(键范围过大)
基数排序 键可按位拆分,位数有限 O(d·(n + b)) O(n + b) 稳定 键为变长或需要浮点比较
桶排序 键可映射到区间且分布均匀 期望 O(n),最坏 O(n·桶内算法) O(n + k) 取决于桶内排序 分布集中,全部落入少量桶

共同的结论:线性时间是"利用键的结构"换来的,而不是普遍比比较排序更快。前提不成立时,计数排序会因 k 过大而耗尽内存,基数排序的轮数会随位数增长,桶排序会退化为桶内排序。选型前必须先确认键的类型、范围与分布,三项中有一项不确定时,比较排序是更稳妥的选择。

2.7 工程中的排序实现

2.7.1 混合策略

标准库不直接使用教科书中的单一算法,而是把多种算法按规模与递归深度组合,原因是不同算法在不同规模与不同数据特征下各有优势。以 Java 的 Arrays.sort 为例:

目标 使用的算法 组成
基本类型数组 两轴快速排序(DualPivotQuicksort) 双枢轴分区 + 小区间插入排序 + 针对结构化数组的归并回退
对象数组 Timsort(归并排序的变体) 识别自然有序段(run)+ 归并 + 小区间二分插入排序

为什么基本类型与对象使用不同算法:基本类型的相等实例彼此不可区分,稳定性没有意义,可以选择更快但不稳定的快速排序;对象数组的相等元素是不同的对象,排序结果中的相对顺序可能被使用者观察(例如界面按分数排序后,同分记录的顺序变化会被察觉),因此使用稳定的 Timsort。这一差别是"稳定性是否有意义"决定算法选择的直接例子。

Timsort 的要点:

  • 从左向右识别已是升序或严格降序的连续段(run),降序段就地反转;
  • 段长小于 MIN_MERGE(JDK 中为 32)时用二分插入排序扩展到该长度;
  • 把各 run 按栈上的长度关系合并(保证合并代价接近平衡归并);
  • 已排序与近乎有序的输入下,识别出的 run 极少,代价接近 O(n),因此 Timsort 有很强的适应性;最坏仍为 O(n log n),代价是最坏需要 O(n/2) 的辅助空间。

其他语言的一致性做法:C++ 的 std::sort 使用内省排序(introsort:快速排序为主,递归深度超过 2·log₂n 时切换堆排序,小区间用插入排序收尾),std::stable_sort 使用归并排序;Python 的 list.sort 与 sorted 使用 Timsort;Go 的 sort.Slice 使用混合的 pdqsort(模式判定 + 插入排序 + 堆排序兜底 + 分治分区)。

混合策略的三条通用手段:

  1. 小区间切换插入排序:减少递归层数与函数调用开销,且插入排序稳定,不破坏整体稳定性。
  2. 递归深度兜底:快速排序的递归深度超过阈值时切换为堆排序,把最坏情况的时间复杂度从 O(n²) 控制在 O(n log n)。这是"平均快 + 最坏有保证"的组合方式。
  3. 枢轴与分区的加固:三数取中、随机化、三路分区或双枢轴,用来抑制已有序输入与大量重复键这两类常见退化。

2.7.2 稳定排序的保证方式

需要稳定时,可按代价从低到高依次考虑:

  1. 使用语言中承诺稳定的接口:Java 的对象数组排序(Arrays.sort(Object[])、Collections.sort、List.sort)与 Python 的 sorted 都是稳定的;C++ 需要显式使用 std::stable_sort;Java 的基本类型数组排序明确不保证稳定。
  2. 在比较器中加入次序键:把原始下标作为次要比较字段,使任意两个元素的比较结果为非零,稳定与不稳定实现的输出都会与稳定排序一致。这一步在 Java 中同时能规避 Timsort 的比较器一致性检查(3.5 节)。
  3. 改写为两轮稳定排序:先按次要键排,再按主要键稳定排。

需要注意 TreeMap、TreeSet 一类有序容器的相等性判定只用比较结果(compare 返回 0 即视为同一个键),不使用 equals;比较器与 equals 语义不一致时会出现键被覆盖或 contains 行为异常。相关契约与配套陷阱见 Java 集合框架实现原理。

2.7.3 基本类型数组与对象数组的排序差异

同一语言中,基本类型数组与对象数组排序的实际耗时往往相差数倍甚至一个数量级,来源有四项:

  • 比较方式:基本类型直接比较机器数(可被编译为单条指令,部分实现还可用向量化指令批量处理);对象比较需要调用 compareTo / 比较器,涉及虚方法分派甚至字段解引用链。
  • 元素访存方式:基本类型数组的元素连续存放;对象数组存放的是引用,排序过程中每次比较都要跟随引用访问对象字段,缓存未命中的概率显著上升。相关机制见 数组与链表 中缓存局部性一节。
  • 移动代价:基本类型数组的交换只移动机器字;对象数组的交换移动的是引用(本身也不便宜,但比移动整个对象小得多)。若排序的是"对象本身的数组",而对象体积很大,则应改为排序"引用数组"或"下标数组",用一次间接访问换取移动量的下降。
  • 算法与稳定性要求不同(2.7.1 节),量级相同但常数与辅助空间不同。

结论:比较大对象集合的排序性能时,首先要区分被排序的是对象引用还是对象数据;把排序键提取为独立的键数组或下标数组,往往比更换排序算法更有效。

2.7.4 并行排序

并行排序把分治的两半或合并的多个分支分配给不同线程,理论加速比受限于可并行比例与数据规模。

  • 适用条件:数据规模大(并行排序的实现通常设有最小分片阈值,Java 的 Arrays.parallelSort 在片段长度小于约 8192 时退化为串行排序)、内存带宽与缓存尚未饱和、可用核数大于 1、数据本身可随机访问。
  • 主要限制:
  1. 排序是访存密集型。多线程同时读写内存,内存带宽很快成为瓶颈,加速比通常明显低于核数;实测中常见 4 至 8 倍是较好的情况。
  2. 并行归并需要额外的缓冲区,内存占用上升;对内存受限的场景不利。
  3. 小规模下反而更慢。线程创建与任务调度(ForkJoin 的任务拆分)的开销超过收益,交叉点通常在数万至数十万元素量级,需按目标规模实测确定。
  4. 共享状态。使用比较器时,比较器必须无副作用且线程安全(禁止在比较器内修改共享缓存)。
  • 典型收益场景:单次对 10⁶ 以上元素的批量排序(离线计算、批量导入前的整理);不适用于每次只排几十个元素的请求链路。

2.8 查找:顺序查找与二分查找

2.8.1 顺序查找

顺序查找逐个比较,代价 O(n),平均比较次数约 (n+1)/2。它的价值在于前提最少:不要求有序、不要求随机访问、不要求键可散列。

两个容易被忽略的结论:

  • 链表上只能顺序查找。二分的每一步都需要随机访问中点,链表定位中点本身是 O(n),因此链表上的二分查找总代价为 O(n)(若在单链表上先跳过前半段再比较,每轮都要重新走链)。
  • 小数组(约 10 个元素以内)上,顺序查找可能比二分更快。二分的分支结果不可预测,分支预测失败的流水线冲刷成本高于几次顺序比较;这是"量级更优不等于实际更快"的又一例(复杂度与算法分析)。

2.8.2 二分查找的前提与直觉

二分查找每轮把搜索区间缩小一半,代价 O(log n)。成立需要两个前提:

  1. 单调性(或等价的判别性质)。存在一个判定条件,使得条件在区间上"先假后真"(或先真后假),才能根据中点的结果决定舍弃哪一半。"有序"是单调性最常见的形式,但不是唯一形式:旋转有序数组、先增后减的序列、函数边界问题都满足某种单调性。
  2. 随机访问。每轮都需要访问区间中点,数组下标寻址是 O(1),链表则不成立。

常见误解:认为"数组是排序的"就能二分。排序只是提供了单调性;若数组在查找过程中被修改(插入、删除、局部更新)而有序性不再成立,二分的结果不可预期。二分查找适用于静态或低频变更的有序数据;频繁插入删除的场景应使用平衡树、跳表或 B+ 树。

2.8.3 区间开闭与边界

二分查找的绝大多数缺陷来自区间定义不统一。两种主流约定:

约定 初始区间 循环条件 收缩方式 循环退出时
闭区间 [lo, hi] lo = 0, hi = n−1 lo <= hi lo = mid + 1 或 hi = mid − 1 区间为空(lo > hi),未找到
左闭右开 [lo, hi) lo = 0, hi = n lo < hi lo = mid + 1 或 hi = mid lo == hi,即答案位置

两类错误由此产生:

  • 区间与收缩方式不匹配造成死循环。在 [lo, hi] 约定里若写 hi = mid(而不是 mid − 1),当 mid == lo 且区间只剩两个元素时区间不再缩小,循环永不结束。反之,在 [lo, hi) 约定里写 hi = mid − 1 会漏掉 mid − 1 这个候选位置,可能返回错误的边界。
  • 取中方式造成越界或死循环。mid = (lo + hi) / 2 在 lo 与 hi 都接近 int 上限时溢出为负数,访问 a[负值] 抛越界异常;应写成 mid = lo + (hi - lo) / 2。在 [lo, hi) 约定里还可以用 mid = lo + ((hi - lo) >> 1)(无符号思想下等价于向下取整)。若采用"上取整"的 mid(lo + (hi - lo + 1) / 2),收缩方式必须相应改变,否则低端不前进。

统一原则:一份代码内只使用一种区间约定,并在注释中写明;变体实现只在"判定条件"与"收缩方向"上做修改,不动区间约定。

2.8.4 二分查找的变体

有序数据上的定位需求很少只问"存不存在",更多是问"边界在哪里"。以下变体都由同一模板通过替换判定条件得到:

需求 判定条件(区间 [lo, hi)) 返回值含义
首个等于 target 的下标 a[mid] < target 则 lo = mid+1,否则 hi = mid lower_bound,再校验 a[lo] == target
末个等于 target 的下标 a[mid] <= target 则 lo = mid+1,否则 hi = mid upper_bound − 1,再校验
首个不小于 target(插入位置) a[mid] < target lower_bound
首个大于 target a[mid] <= target upper_bound
旋转有序数组中的最小值 a[mid] > a[hi] 最小值的下标
峰值元素(先增后减) a[mid] < a[mid+1] 峰值下标
二分答案 feasible(mid) 为假则 lo = mid+1 最小的可行解

旋转数组(原本有序的数组在某个位置被旋转,例如 [4,5,6,7,0,1,2])的关键是判断哪一半有序,进而判断目标是否落在该半段内。查找最小值时改用与右端点的比较可以避免"中点落在哪一段"的分支判断:

/** 旋转有序数组(元素互不相同)中的最小值:把 a[mid] 与右端点比较。 */
public static int findMin(int[] a) {
    int lo = 0;
    int hi = a.length - 1;
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (a[mid] > a[hi]) {
            lo = mid + 1;          // 中点大于右端点,最小值在右半段
        } else {
            hi = mid;              // 否则最小值在左半段(可能正是 mid)
        }
    }
    return a[lo];
}

峰值元素的判定利用的是"局部上升则右侧必有峰值"这一性质(数组两端视为 −∞):若 a[mid] < a[mid+1],则峰值在右半段,否则在左半段(含 mid)。这类"非全局有序但满足单调判别性质"的问题都可以套用同一模板。

二分答案把二分从"在数组中查找"推广到"在解空间中查找":只要判定函数 feasible(x) 关于 x 单调(例如"容量为 x 时能否完成"),即可对解空间二分,把最优化问题转化为判定问题,代价为 O(log(值域) × 判定代价)。

浮点数二分不能用"区间为空"作为终止条件(浮点数可以无限细分),应固定迭代次数(例如 100 次,每次区间减半,100 次后精度已远超双精度有效位)或使用绝对/相对误差阈值。

2.8.5 插值查找与斐波那契查找

两者都是二分查找的变形,改的是"取哪个位置作为切分点"。

插值查找按值的比例估计位置,取

mid = lo + (target - a[lo]) / (a[hi] - a[lo]) × (hi - lo)

在键近似均匀分布时(例如按时间顺序排列且访问均匀的日志),每轮可以把区间缩小到接近 O(√n) 的比例,期望代价 O(log log n)。局限:分布不均匀时定位偏差大,最坏退化为 O(n)(每次只排除一个元素);计算涉及浮点除法,单次开销高于二分;数组必须支持随机访问。适用面窄,只在键分布已知且均匀、查找次数极多时才值得采用。

斐波那契查找用斐波那契数列确定切分点(F(k−1) 与 F(k−2)),使每次切分只用到加减法,不涉及除法。历史背景是早期硬件除法昂贵;现代处理器上整数除法与乘法的代价差异很小,且斐波那契查找需要把数组补齐到斐波那契长度,实际收益有限(平均查找长度略优于二分,但在实测中通常被额外的索引计算与边界判断抵消)。作为一种"避免除法"的技巧,它在嵌入式或除法代价高的环境下仍有价值。

2.8.6 有序结构与散列结构的查找选择

二分查找要求数据有序且可随机访问,把"维护有序"的责任留给调用方。若数据会频繁变更或需要更丰富的查询能力,应改用以下结构:

需求 适用结构 依据
静态有序数组上的等值与边界查找 二分查找(Arrays.binarySearch、Python bisect) O(log n),无额外结构
按 key 查找,且需要范围与邻近查询 平衡二叉搜索树、跳表、B+ 树 提供 first/ceiling/floor/subMap 一类操作,见 二叉树与二叉搜索树、跳表
只判断存在性或做等值查找,无顺序需求 散列表、散列集合 期望 O(1);不支持范围与有序遍历,见 散列表
数据在磁盘上,需要按键定位且减少 IO 次数 B+ 树 节点大小对齐页,树高小,见 B+ 树与索引
只需判断"可能存在"且接受误判 位图、布隆过滤器 空间远小于散列结构,见 位图与布隆过滤器

选择依据是查询形态而不是单次查找的复杂度排名:散列表的期望 O(1) 优于平衡树的 O(log n),但范围查询、有序遍历与"最接近的键"在散列表上需要全量扫描。这一取舍与容器选型中的其他判断一致,各容器的复杂度总表见 Java 集合框架实现原理。

2.9 外排序与海量数据

数据量超过可用内存时,排序必须分批进行并借助磁盘。这类排序称为外部排序,它在算法层面仍是归并排序,难点在于 IO 次数与缓冲区的分配。

阶段一:生成初始归并段。

  • 常规做法:把输入分成大小为 M(内存容量)的块,逐块读入内存,用内存排序算法排好,写回磁盘形成一个有序段(run)。N 个元素产生约 N/M 个段。
  • 置换选择(replacement selection):用一个大小为 M 的堆在内存中维护候选集合。每次输出堆顶(当前最小元素)后,读入下一条记录:若它不小于刚输出的记录,则放入堆中继续参与当前段;否则它属于下一个段,暂存在缓冲区。当堆被耗尽(或缓冲区满)时结束当前段。这样生成的段平均长度约为 2M,段数减半,从而减少后续归并的趟数。段的长度取决于输入的初始有序程度:输入已近似有序时段长可以达到 M 的数倍,完全逆序时接近 M。

阶段二:多路归并。把 k 个有序段合并为一个。用大小为 k 的小顶堆(或败者树)保存每段当前的游标元素,每次取最小值输出,并用该段的下一条记录替换堆顶。代价为 O(N log k),其中 N 为总记录数。与线性扫描 k 个游标的 O(N·k) 相比,堆把"选择最值"的代价压到对数级。堆的多路归并实现与复杂度见 堆与优先队列 中多路归并一节。

路数 k 的取舍:段数为 r 时,归并趟数为 log_k r。k 越大趟数越少、IO 次数越少;但每趟需要同时打开 k 个输入缓冲(内存被分割为 k+1 份,缓冲变小会降低单次 IO 的连续性),同时比较成本随 log k 增长,且受文件句柄数量限制。因此 k 由"可用内存能分出多少块缓冲"与"进程可打开的文件数"共同决定,常见取值在几十到数百之间。

败者树:k 较大时可以用败者树替代堆。它记录每一层比较的败者,胜者继续上升,因此每次选择新最小值只需沿树向上比较 log k 次,且不需要堆中的交换动作(堆在替换堆顶后需要下沉,涉及多次赋值)。败者树与堆的思想一致,都是把选择最值的代价保持在 O(log k),是外部排序中的常见优化。

磁盘 IO 与顺序访问的影响(这是外排序区别于内存排序的核心):

  • 顺序访问远快于随机访问。机械盘上一次寻道是毫秒级,顺序读一条记录的时间可以忽略;即使固态盘,随机 4KB 读的吞吐也远低于顺序读。因此外排序必须用大缓冲、顺序读写,避免"读一条记录、跳一次文件"的模式。
  • 页缓存与预读。操作系统会把文件数据缓存在页缓存中,并对顺序读做预读(提前把后续数据读入缓存)。归并过程中若各段的读取是顺序的,预读有效,后续块的读命中可以省去物理 IO;若访问模式变成随机跳读,预读失效,每次都要落到磁盘。页缓存的结构、预读机制与脏页回写对写性能的影响见 linux: 页缓存与 IO 性能。
  • 写侧的批量与刷盘。生成初始段时的写入应尽量批量,减少小随机写;在需要持久化保证时再调用 fsync,而不是每条记录同步一次(高频 fsync 会让排序用时被刷盘延迟主导)。
  • 两阶段的分界:阶段一的时间由内存排序算法与顺序写决定,阶段二的时间由 k 路归并的比较次数与顺序读写决定。数据量越大,IO 在总耗时中的占比越高,此时优化重点从"降低比较次数"转向"减少 IO 次数、提高每次 IO 的连续长度"。

外排序的思路也适用于内存内的分治与并行:把"内存放不下"换成"单机放不下"就得到按范围分片、分片内排序再归并的分布式排序;把"内存容量 M"换成"单次可处理批大小"就得到数据库与搜索引擎中的批量索引构建流程。


三、实现

3.1 排序实现要点

3.1.1 插入排序与希尔排序

/** 插入排序:对 [lo, hi] 区间排序。稳定、原地,近乎有序时接近 O(n)。 */
public static void insertionSort(int[] a, int lo, int hi) {
    for (int i = lo + 1; i <= hi; i++) {
        int key = a[i];
        int j = i - 1;
        while (j >= lo && a[j] > key) {   // 严格大于才后移,相等元素保持相对顺序
            a[j + 1] = a[j];
            j--;
        }
        a[j + 1] = key;
    }
}
/** 希尔排序:Knuth 增量序列 1, 4, 13, 40, ... 最坏 O(n^1.5)。不稳定、原地。 */
public static void shellSort(int[] a) {
    int h = 1;
    while (h < a.length / 3) {
        h = 3 * h + 1;                    // 生成不超过 n/3 的最大步长
    }
    for (; h >= 1; h /= 3) {
        for (int i = h; i < a.length; i++) {
            int key = a[i];
            int j = i - h;
            while (j >= 0 && a[j] > key) {
                a[j + h] = a[j];
                j -= h;
            }
            a[j + h] = key;
        }
    }
}

易错点:

  • 插入排序的内层条件必须同时判断下标下界与比较结果,且下界用 j >= lo(区间起点,不是 0),否则在子区间调用时会越界。
  • 比较符写成 >= 会破坏稳定性(相等元素被后移)。
  • 希尔排序最后一轮必须 h == 1,否则数组未必有序;步长序列必须严格递减到 1,整除式的递推(h /= 3)需要确认能取到 1(1/3 == 0 会提前结束循环,因此循环条件为 h >= 1)。

3.1.2 归并排序

/** 归并排序:稳定;额外空间 O(n)。临时数组在递归外分配一次并复用。 */
public static void mergeSort(int[] a) {
    int[] tmp = new int[a.length];
    sort(a, tmp, 0, a.length - 1);
}

private static void sort(int[] a, int[] tmp, int lo, int hi) {
    if (lo >= hi) {
        return;
    }
    int mid = lo + (hi - lo) / 2;
    sort(a, tmp, lo, mid);
    sort(a, tmp, mid + 1, hi);
    if (a[mid] <= a[mid + 1]) {
        return;                            // 两段已整体有序,跳过合并(获得部分适应性)
    }
    merge(a, tmp, lo, mid, hi);
}

private static void merge(int[] a, int[] tmp, int lo, int mid, int hi) {
    System.arraycopy(a, lo, tmp, lo, hi - lo + 1);
    int i = lo;
    int j = mid + 1;
    for (int k = lo; k <= hi; k++) {
        if (i > mid) {
            a[k] = tmp[j++];
        } else if (j > hi) {
            a[k] = tmp[i++];
        } else if (tmp[j] < tmp[i]) {
            a[k] = tmp[j++];               // 右段严格更小时才先取右段,相等取左段以维持稳定
        } else {
            a[k] = tmp[i++];
        }
    }
}

易错点:

  • 稳定性由判定条件与取值顺序共同决定:先比较的是 tmp[j] < tmp[i](左段优先),写成 <= 会先取右段,稳定性丢失。
  • 临时数组不要每层分配。每层都 new 会让分配次数达到 O(n) 次、总分配量 O(n log n),明显拖慢实测结果。
  • 合并前判断 a[mid] <= a[mid + 1] 可以跳过已整体有序的两段,对近乎有序输入接近 O(n)。
  • 递归深度为 O(log n),数组实现的栈开销可忽略;自底向上的迭代写法(步长从 1 开始倍增)可进一步消除递归。

3.1.3 快速排序:随机枢轴与三路分区

private static final int INSERTION_THRESHOLD = 12;

/** 快速排序:随机打乱 + 三路分区 + 小区间插入排序 + 尾递归消除。不稳定、近乎原地。 */
public static void quickSort(int[] a) {
    shuffle(a);                                // 随机化,规避确定性最坏输入
    sort3Way(a, 0, a.length - 1);
}

private static void sort3Way(int[] a, int lo, int hi) {
    while (lo < hi) {
        if (hi - lo + 1 <= INSERTION_THRESHOLD) {
            insertionSort(a, lo, hi);          // 小区间切换插入排序
            return;
        }
        int lt = lo;
        int i = lo + 1;
        int gt = hi;
        int pivot = a[lo];
        while (i <= gt) {                      // 三路分区:< pivot / == pivot / > pivot
            if (a[i] < pivot) {
                swap(a, lt++, i++);
            } else if (a[i] > pivot) {
                swap(a, i, gt--);              // 换来的元素未检查,i 不前进
            } else {
                i++;
            }
        }
        // 此时 [lo, lt) < pivot,[lt, gt] == pivot,已全部就位
        if (lt - lo < hi - gt) {
            sort3Way(a, lo, lt - 1);
            lo = gt + 1;                       // 较长的一侧用循环处理,递归深度保持 O(log n)
        } else {
            sort3Way(a, gt + 1, hi);
            hi = lt - 1;
        }
    }
}

易错点:

  • 三路分区中 a[i] > pivot 分支的 i 不前进。与 gt 交换后换来的元素尚未检查,若同时 i++ 会漏掉一个元素,导致分区错误(这一缺陷往往只在含重复键的用例上暴露)。
  • 循环条件为 i <= gt(闭区间),写成 i < gt 会漏掉最后一个被交换到 gt 位置的元素。
  • 小区间判定用 hi - lo + 1 <= 阈值(元素个数),不要混用下标差。
  • 随机化是必要的。若使用固定枢轴,已排序与逆序输入都会触发 O(n²) 与深度为 n 的递归(可能导致栈溢出),而这两种输入在实际系统中极为常见。
  • 递归深度。只对较短一侧递归是保证 O(log n) 栈深度的关键;若两侧都递归且枢轴固定取首元素,处理 10⁶ 规模的有序数组会直接触发栈溢出。
  • 相等键的批量聚拢是三路分区的主要收益:大量重复键场景下不再需要反复递归,代价与不同键的数量相关。

3.1.4 计数排序与基数排序

/** 计数排序:键为 [0, maxKey] 内的整数。稳定版本需要输出数组。 */
public static void countingSort(int[] a, int maxKey) {
    int[] count = new int[maxKey + 1];
    for (int x : a) {
        count[x]++;
    }
    for (int k = 1; k <= maxKey; k++) {
        count[k] += count[k - 1];              // 前缀和:count[k] 变为"不大于 k 的元素个数"
    }
    int[] out = new int[a.length];
    for (int i = a.length - 1; i >= 0; i--) {
        out[--count[a[i]]] = a[i];             // 从后向前填,保证相等元素的相对顺序不变
    }
    System.arraycopy(out, 0, a, 0, a.length);
}

/** LSD 基数排序:按十进制位从低位到高位,逐位调用稳定计数排序。 */
public static void radixSort(int[] a) {
    int max = 0;
    for (int x : a) {
        max = Math.max(max, x);
    }
    for (int exp = 1; max / exp > 0; exp *= 10) {
        countingSortByDigit(a, exp);
    }
}

private static void countingSortByDigit(int[] a, int exp) {
    int[] count = new int[10];
    int[] out = new int[a.length];
    for (int x : a) {
        count[x / exp % 10]++;
    }
    for (int d = 1; d < 10; d++) {
        count[d] += count[d - 1];
    }
    for (int i = a.length - 1; i >= 0; i--) {
        out[--count[a[i] / exp % 10]] = a[i];  // 子过程必须稳定
    }
    System.arraycopy(out, 0, a, 0, a.length);
}

易错点:

  • 计数排序的填充必须从后向前。改为从前向后会把相等元素的相对顺序颠倒,稳定性丢失;基数排序依赖这一稳定性,稳定性一旦破坏,排序结果直接错误(且错误只在含重复键时出现)。
  • 前缀和的语义。计算完前缀和后,count[v] 是"个数"而不是"下标",因此必须先自减再使用(out[--count[v]])。
  • 键的范围。maxKey 由数据决定,必须在入口校验上界,否则数组越界或内存耗尽;键含负数时需要先加上偏移量。
  • 基数排序的轮数与基数。按十进制位最直观,但取基数为 256(按字节)可把 32 位整数的轮数固定为 4 轮,同时计数数组只有 256 项,通常更快。
  • 比较排序与这两者的选择依据是键的类型与范围,不是数据规模。

3.1.5 堆排序

堆排序的实现(上浮、下沉、建堆、取堆顶)与索引关系见 堆与优先队列。实现上需要注意三点:

  • 建堆用自底向下沉(O(n))而不是逐个插入(O(n log n));
  • 下沉用循环而非递归,避免 O(log n) 的调用栈;
  • 下沉时必须与两个孩子中更优先者比较,只与左孩子比较会在右孩子更优时误判堆序成立,导致取出的不是最值。

3.2 二分查找实现要点

3.2.1 两种统一模板

模板一:闭区间 [lo, hi],适合"找到即返回"的查找。

/** 在升序数组中查找 target,返回任一匹配下标,未找到返回 -1。 */
public static int binarySearch(int[] a, int target) {
    int lo = 0;
    int hi = a.length - 1;
    while (lo <= hi) {                         // 闭区间:lo == hi 时区间内仍有一个待查元素
        int mid = lo + (hi - lo) / 2;          // 避免 lo + hi 上溢
        if (a[mid] < target) {
            lo = mid + 1;
        } else if (a[mid] > target) {
            hi = mid - 1;
        } else {
            return mid;
        }
    }
    return -1;
}

模板二:左闭右开 [lo, hi),适合求边界的变体(lower_bound / upper_bound)。这一模板的优势是循环退出时 lo == hi 就是答案位置,不需要额外的返回值约定。

/** lower_bound:首个不小于 target 的下标,也是 target 的插入位置;取值域为 [0, n]。 */
public static int lowerBound(int[] a, int target) {
    int lo = 0;
    int hi = a.length;                         // 答案取值域包含 n(target 大于所有元素时)
    while (lo < hi) {                          // 区间非空时继续
        int mid = lo + (hi - lo) / 2;          // mid 必落在 [lo, hi - 1],区间必然收缩
        if (a[mid] < target) {
            lo = mid + 1;                      // mid 及其左侧都不可能是答案
        } else {
            hi = mid;                          // mid 可能是答案,保留在区间内
        }
    }
    return lo;
}

/** upper_bound:首个大于 target 的下标。 */
public static int upperBound(int[] a, int target) {
    int lo = 0;
    int hi = a.length;
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (a[mid] <= target) {
            lo = mid + 1;
        } else {
            hi = mid;
        }
    }
    return lo;
}

由 lower_bound 与 upper_bound 直接得到的常见结论:

  • target 存在当且仅当 lb < n && a[lb] == target;
  • 等于 target 的元素个数为 ub - lb;
  • 最后一个等于 target 的下标为 ub - 1;
  • 若只需要"插入位置且不关心重复",用 lower_bound(或标准库的 Arrays.binarySearch 的负数返回值换算)。

Python 的 bisect 模块对应关系:bisect_left 即 lower_bound,bisect_right(等价于 bisect.bisect)即 upper_bound。

3.2.2 死循环与越界排查

二分查找的缺陷集中在四类,可按顺序检查:

症状 成因 检查点
死循环、CPU 占满 区间未收缩:写了 lo = mid 或 hi = mid 却使用 lo <= hi 的循环条件;mid 采用上取整而未调整收缩方向 每轮结束时 mid 是否必然被排除;区间长度是否严格减小
ArrayIndexOutOfBoundsException mid = (lo + hi) / 2 溢出为负数;或 hi = a.length 时把 a[mid] 写成 a[mid + 1] 一类越界访问 取中是否使用 lo + (hi - lo) / 2;所有下标访问是否在 [0, n−1] 内
返回的边界差 1 lower_bound 与 upper_bound 用错;hi = mid 与 hi = mid - 1 混淆 判定条件用的是 < 还是 <=;区间约定是否与收缩方式匹配
未找到时返回错误位置 用"找到即返回"的模板求边界,遇到重复键时返回任意一个匹配位置 求边界必须使用 lower_bound / upper_bound 模板
浮点数二分不终止 以"区间为空"为终止条件,浮点区间可以无限细分 固定迭代次数(如 100 次)或使用误差阈值

排查方法:用"区间不变式"的方式检查每一轮——写清楚当前区间的含义(例如"答案一定在 [lo, hi) 内"),确认三种情况下该不变式都保持:a[mid] < target 时答案在右半段、a[mid] > target 时答案在左半段、a[mid] == target 时按需求决定答案是否包含 mid。不变式与收缩方式一致时,循环一定终止且结果正确。

3.2.3 上溢安全的取中写法

三种写法及其适用条件:

int mid = lo + (hi - lo) / 2;                 // 推荐:任意非负 lo、hi 下都不溢出
int mid = (lo + hi) >>> 1;                    // 等价(无符号右移),要求 lo + hi 不以有符号方式溢出
int mid = lo + (hi - lo + 1) / 2;             // 向上取整;必须配合 lo = mid 一侧的收缩方式

(lo + hi) / 2 在 lo 与 hi 均接近 Integer.MAX_VALUE 时溢出为负数,随后作为下标使用会抛越界异常。这一缺陷在正常规模的数组上不会触发(需要数组长度超过 10⁹),但在以数值为搜索空间的"二分答案"场景中极为常见——此时 lo 与 hi 是解空间的边界,可以任意大。

3.3 复杂度与实测

3.3.1 十类排序的复杂度对照

算法 最好 平均 最坏 额外空间 稳定 原地 适应性
冒泡排序 O(n)(带标志) O(n²) O(n²) O(1) 稳定 是 是
选择排序 O(n²) O(n²) O(n²) O(1) 不稳定 是 否
插入排序 O(n) O(n²) O(n²) O(1) 稳定 是 是
希尔排序 O(n log n) 依增量序列 依增量序列(Knuth 为 O(n^1.5)) O(1) 不稳定 是 部分
归并排序 O(n log n) O(n log n) O(n log n) O(n)(数组) 稳定 否 部分(可加判定)
快速排序 O(n log n) O(n log n) O(n²) O(log n) 至 O(n)(递归栈) 不稳定 是 否
堆排序 O(n log n) O(n log n) O(n log n) O(1) 不稳定 是 否
计数排序 O(n + k) O(n + k) O(n + k) O(k) 稳定 否 否
基数排序 O(d·(n + b)) 同左 同左 O(n + b) 稳定 否 否
桶排序 O(n) O(n + k) O(n²)(桶内用插入排序时) O(n + k) 取决于桶内排序 否 否

表中 k 为键的取值范围(计数排序)或桶数(桶排序),d 为按基数 b 拆分后的位数。需要强调的是:量级相同的算法之间差异由常数因子、缓存行为与辅助空间决定,实测量级往往比表格更接近决策依据;量级不同时以分析结论为准。这一分工见 复杂度与算法分析。

3.3.2 不同规模与数据分布下的实测

排序的实测必须同时控制规模与数据分布两个变量,只测随机数据会掩盖算法之间最重要的差异。

数据分布 构造方式 预期表现
随机 打乱取值范围较宽的数组 各算法的"平均情况";用于比较常数因子
近乎有序 有序数组上随机交换少量元素 插入排序、Timsort、带判定归并接近 O(n);快速排序在固定枢轴时最坏
完全有序 / 逆序 升序或降序数组 固定枢轴快排退化到 O(n²) 与深度 O(n);堆排序、归并排序不受影响
大量重复 键取自很小的集合(如 0 至 9) 二路快排明显变慢;三路快排一次分区即跳过相等段
少量不同键但规模大 例如全是 0 与 1 计数排序接近线性;比较排序浪费大量比较

规模至少取三档(例如 10³、10⁵、10⁷)以观察比值随规模的变化:只在单一规模上比较绝对值,无法区分"常数差异"与"量级差异"。

实测方法:

  • 必须使用基准框架。排序属于会被完全内联并可能被整体消除的代码(结果未被消费时尤其明显),手写 System.nanoTime 计时会因预热不足、死代码消除与 JIT 内联而得到不可用结论;JMH 通过框架管理预热与测量、黑洞消费结果、分叉隔离进程来规避这些问题,具体陷阱与判读方式见 JMH 微基准测试。
  • 每次测量必须重新生成或拷贝输入。原地排序会破坏输入,复用同一个已被排序的数组会让后续轮次测的是"有序输入的排序"。
  • 同时报告时间与空间。非原地算法(归并、计数、基数)的分配量与内存峰值应一起记录;只比时间会得出与实际资源约束不符的结论。
  • 与标准库对比的注意事项:标准库实现通常是混合策略(2.7.1 节),在小规模、近乎有序与大量重复这三类输入上有专门优化,手写的单一算法在这些输入上落后属于预期;对比时应说明输入规模、分布、JDK/库版本与比较键的类型(基本类型还是对象),并确认标准库在同规模下的算法分支(例如 Java 基本类型数组在长度小于阈值时使用插入排序)。结论必须带条件,不可外推为"该算法比标准库快"。

3.4 选型指南

3.4.1 按需求选择

需求 首选 说明
一般内存排序,无特殊约束 语言内置排序(Java Arrays.sort / Python sorted) 混合策略已在多种输入上做了权衡,自写实现很难全面超越
要求稳定 归并排序 / Timsort(对象数组排序) 或在比较器中加入次序键使不稳定算法表现为稳定
内存受限、要求最坏时间有保证 堆排序 原地 O(1)、最坏 O(n log n)、必然不稳定且缓存不友好
近乎有序 插入排序 / Timsort 代价与逆序对数成正比
大量重复键 三路快速排序 相等段一次跳过,代价与不同键数量相关
键为小范围整数 计数排序 O(n + k),k 必须与 n 同阶或更小
键为定长整数或定长编码 基数排序 O(d·(n + b)),按字节拆分通常优于按十进制位
键在区间上近似均匀分布 桶排序(配以稳定的桶内排序) 期望 O(n),分布集中时退化
只取前 K 个(K 远小于 n) 大小为 K 的堆 O(n log K)、空间 O(K);见下
只需要第 K 小(不需要前 K 有序) 快速选择(划分选择) 平均 O(n),最坏 O(n²),原地
数据超过内存 外部归并排序 分块内存排序 + 多路归并(2.9 节)

3.4.2 部分排序:只需前 K 个

完整排序做了大量与需求无关的工作——需求只要前 K 个,排序却确定了全部 n 个元素之间的顺序。三种替代方案:

  • 大小为 K 的堆:求最大 K 个用小顶堆(堆顶是候选中最差的一个,便于替换),求最小 K 个用大顶堆。时间 O(n log K),空间 O(K),支持流式输入。堆方向写反会得到相反的一半结果,是这一类问题的典型缺陷。实现与复杂度见 堆与优先队列。
  • 快速选择(quickselect):基于快速排序的划分,每次划分后只递归含有目标位置的一侧,平均代价 O(n)、最坏 O(n²),原地且不需要额外结构,但要求数据可随机访问且不能用于流式输入。
  • 仅需第 K 小、不需要前 K 有序时快速选择优于堆;需要结果有序或数据流式到达时堆更合适。已有部分有序数据(例如多个来源各自有序)时,多路归并的代价 O(n log k) 也低于全排序。

3.4.3 特殊数据的处理

  • 近乎有序:直接用内置排序(Timsort 一类的实现能识别有序段),或对局部使用插入排序,避免先整体打乱再排序。
  • 重复多:三路快排,或先按"不同键"做计数/直方图再展开;对只需去重与计数的场景,散列表或计数数组的代价低于排序。
  • 值域小:计数排序;若需要按顺序输出且值域为字符级,可用位图压缩计数数组,见 位图与布隆过滤器。
  • 键为字符串:定长字符串可用基数排序;变长字符串的比较成本高,应考虑三路字符串快排或前缀树(前缀树),并注意避免在比较器中重复构造子串。
  • 大对象:排序引用数组或下标数组,让移动的单位从"整个对象"降为"一个引用或一个整数",需要时再按结果顺序访问对象(2.7.3 节)。

3.5 常见误用与排查

现象 可能原因 验证与处置
多关键字排序结果错乱,次要键的顺序随机 使用了不稳定的排序做第二轮排序;或两轮排序顺序颠倒(应先次要键、后主要键) 确认接口是否承诺稳定(Java 基本类型数组排序不保证稳定);改用对象数组排序、归并排序,或在比较器中串联两个键
抛 IllegalArgumentException: Comparison method violates its general contract 比较器不满足传递性(如用两数相减实现整数比较,溢出导致符号错误),或比较器有副作用、结果依赖调用次数;TimSort 会检测并抛出该异常 用 Integer.compare / Double.compare / Comparator.comparingXxx 替代相减;保证比较器是纯函数且与 equals 语义一致(Java 集合框架实现原理)
排序结果与预期"看起来对但顺序不稳定",某次升级 JDK 或换实现后顺序变了 依赖了未承诺的稳定性(例如依赖 Arrays.sort(int[]) 后相等元素的顺序) 需要稳定时显式选择稳定接口或加入次序键;不要在测试中断言相等元素的顺序
排序大对象集合时耗时异常 移动的数据量大;对象数组的每次比较都要跟随引用访问字段,缓存未命中率高 改为排序引用数组或下标数组;把参与比较的字段提取为独立的键数组;确认比较器中没有重复计算(如每次比较都解析字符串)
排序耗时随数据量呈平方级增长 使用固定枢轴的快速排序遇到已有序或逆序输入;选择排序用于大规模数据;桶排序分布集中导致单桶过大 检查是否已随机化或三数取中;确认输入的初始有序程度;对分布不确定的数据放弃桶排序
二分查找结果不稳定:有时找得到、有时返回错误位置 数据在两次查询之间被修改,有序性不再成立;或对含重复键的数组使用"找到即返回"的模板求边界 确认二分的两个前提(单调性与随机访问);求边界统一改为 lower_bound / upper_bound;频繁变更的数据改用平衡树或跳表
二分查找死循环或抛越界异常 区间约定与收缩方式不匹配(hi = mid 配 lo <= hi);(lo + hi) / 2 溢出 按 3.2.2 的表格逐项检查;统一使用左闭右开模板与 lo + (hi - lo) / 2
对链表使用二分查找,耗时仍为线性 链表不支持随机访问,每次定位中点是 O(n) 链表只做顺序查找;若必须二分,先转为数组(一次性 O(n) 代价)或改用跳表 / 平衡树
排序递归实现抛 StackOverflowError 快速排序在最坏输入下递归深度为 O(n);归并排序的递归深度通常为 O(log n),但若把枢轴选择写成"每次只减少一个元素"则同样会深 随机化或三数取中;只对较短一侧递归,较长一侧用循环;或改用自底向上的迭代式归并;也可在深度超限时切换到堆排序
循环内排序或每次查询都重排,整体耗时异常 排序未提到循环外,或对未变化的数据重复排序 一次排序后复用结果,查询走二分或散列;对需要频繁插入删除的数据改用有序结构而非"每次重排"
计数排序占用内存过大或抛越界 键的取值范围 k 远大于元素个数 n;键含负数或超出预期上界 入口校验键的上界与符号;k 过大时改用比较排序或基数排序

排查顺序:

  1. 确认数据的初始特征(规模、有序程度、重复比例、键的类型与范围),与选型时的假设对照;
  2. 确认所用实现的稳定性、最坏情况与空间开销是否与需求匹配;
  3. 用包含重复键与近乎有序用例的测试集验证正确性——这两类输入最能暴露稳定性与边界缺陷;
  4. 若为性能问题,先用基准框架分别测量"输入生成"与"排序"两段的耗时,确认瓶颈是否真的在排序(2.9 节的外部存储、比较器成本、装箱与对象分配都可能是真正的来源);
  5. 二分查找的问题优先按"区间不变式"复查,而不是逐行猜测边界。

3.6 检查清单

正确性。

  • 排序实现是否在有重复键的输入上验证过?需要稳定时,是否用"相等键保留原相对顺序"的用例验证?
  • 排序实现是否在空数组、单元素、两元素、全相等这四类边界输入上验证过?
  • 插入排序、快速排序、归并排序的子区间调用是否使用正确的区间端点(而不是固定 0 与 n−1)?
  • 计数排序与基数排序的填充方向是否为从后向前(保证稳定)?前缀和的语义是否用于定位而不是计数?
  • 二分的区间约定是否统一?循环中的每一轮是否保持"答案在区间内"这一不变式?取中是否使用上溢安全的写法?
  • 求边界的场合是否使用了 lower_bound / upper_bound 模板,而不是"找到即返回"的模板?
  • 需要稳定的场合,选用的接口是否明确承诺稳定?
  • 比较器是否满足传递性、自反性、反对称性,是否为纯函数,是否与 equals 的语义一致?

性能。

  • 是否在混合排序已有优势的场合重复造轮子(小规模、近乎有序、大量重复、对象数组稳定排序)?
  • 是否把排序放在了循环内,或对未变化的数据重复排序?
  • 排序对象是大对象还是引用?是否可以把比较键或下标单独提取成数组?
  • 比较器内部是否做了可预先完成的工作(字符串解析、正则、字段拼接、子串构造)?
  • 归并排序的临时数组是否在递归外复用?快速排序是否做了随机化或三数取中与小区间切换?
  • 递归深度是否有上界(最坏输入下是否会达到 O(n))?
  • 非比较排序的前提(键类型、取值范围、分布)是否已在入口校验,而不是隐含假设?
  • 二分查找的数据是否被其他路径修改?维护有序的代价是否已计入整体方案(更合适时是否应改用平衡树、跳表或散列结构)?
  • 性能结论是否来自基准框架,并记录了规模、数据分布、版本与被排序元素的类型?

四、总结

排序与查找是同一件事的两面:排序把数据整理成可被算术定位的形式,查找则消费这一形式。二分查找的 O(log n)、去重的 O(n)、区间查询的常数级定位、归并的线性合并,都以有序性为前提;而有序性本身需要一次 O(n log n) 的预处理,或由有序结构(平衡树、跳表、B+ 树)在每次修改时以对数代价维护。

原理层面的主线。

  • 性质决定可用集合:稳定性、原地性、比较与非比较、适应性,四个维度与三类复杂度共同描述一个排序算法。多关键字排序要求稳定,内存受限要求原地,键类型与范围决定能否使用非比较排序,输入分布决定适应性是否起作用。忽略其中任何一项都可能选出不满足需求的算法。
  • 下界划定了优化空间:比较排序的 Ω(n log n) 是决策树模型下问题固有的下界,归并排序与堆排序已到达该下界,进一步的改进只能落在常数因子、缓存行为与辅助空间上。突破下界必须改变前提——计数、基数、桶排序通过利用键的取值结构达到线性代价,代价是与前提绑定。
  • 十类算法的分工清晰:插入排序负责近乎有序与小规模,希尔排序用增量换取原地且无 O(n) 辅助空间的中等规模性能,归并排序提供稳定性与外部排序的基础,快速排序提供平均最快的原地排序,堆排序提供最坏时间有保证的原地排序,三类非比较排序负责满足前提的特定键集合。快速排序的两个退化来源(已有序输入、大量重复键)分别由随机化/三数取中与三路分区处理。
  • 混合策略是工程答案:标准库不选单一算法,而是"快速排序为主 + 插入排序收尾 + 堆排序兜底 + 针对数据特征的加固"。基本类型与对象数组使用不同算法的原因正是稳定性对后者才有意义。
  • 查找的代价由前提决定:顺序查找前提最少、代价线性;二分查找要求单调性与随机访问,代价对数;平衡树与跳表在维护有序的同时支持范围与邻近查询;散列表把等值查找降到期望常数,代价是放弃顺序与范围能力。选择依据是查询形态与数据的变更频率,而不是单次查找的复杂度排名。
  • 外部排序把"内存容量"变成参数:分块内存排序成型 + 多路归并合并,置换选择把初始段平均长度提高到约 2M,败者树把 k 路选择最值的代价压到 O(log k)。数据量越大,IO 的占比越高,优化的重点从比较次数转向 IO 次数与访问的连续性。

实现与工程层面的落点。

  • 边界与相等元素是缺陷最集中的两处:插入排序的下标下界、归并合并的严格小于、三路分区的双指针移动、计数排序的填充方向、二分的区间收缩,都属于需要逐项核对的位置。含重复键与近乎有序的测试集是暴露这些缺陷的最有效手段。
  • 递归深度需要有上界。快速排序在退化输入下的深度为 O(n),会直接触发栈溢出;只对较短一侧递归、随机化枢轴、深度超限切换堆排序是三种可组合的处置。
  • 排序键与比较器是性能的常见瓶颈。比较器的成本、键的提取方式、被排序的是对象还是引用,往往比更换算法更能改变实测结果。
  • 选型按需求收敛:需要稳定则选归并或 Timsort,内存受限且要求最坏界则选堆排序,重复多则三路快排,键为小范围整数则计数排序,只需前 K 则堆或快速选择,数据超过内存则外部归并;没有特殊需求时,语言内置的混合排序是默认答案。
  • 性能结论必须带条件。规模、数据分布、元素类型、库版本都会改变算法之间的排序,量级相同或落在交叉点附近时必须实测,量级不同且规模足够大时可以直接依据分析决策。

排序与查找的取舍可以归纳为两个问题:数据具备哪些可利用的结构(有序程度、重复比例、键的取值范围与分布),以及需求真正需要哪些承诺(稳定性、最坏界、原地性、范围查询能力)。回答完这两个问题,算法与结构的选择基本已经确定。