提到“八大排序算法”新入门的朋友第一反应通常是到底是哪八个说实话这个“八”并没有一个完全统一的标准版本。常见的组合是冒泡、选择、插入、希尔、归并、快速、堆、计数这八个也有地方会把基数排序、桶排序拉进来把计数挤出去或者干脆列出十种。但不管名单怎么变核心思路永远是那些——搞清楚“比较排序”和“非比较排序”两大分支掌握每个算法的原理、复杂度、稳定性和适用场景比死记硬背是哪八个重要得多。这篇文章我会站在一个常年写排序、也经常帮人调试排序代码的工程师角度把这八个最常用的排序算法完整讲透。包括每一步是怎么执行的、为什么要这么设计、代码怎么写、有哪些坑、工程上到底该选谁以及那些“面试官爱问但书里不写”的细节。如果你是准备笔试面试的计算机专业学生或者正在做数据结构课程设计、需要手写排序的开发者这篇应该能帮你省下不少查资料的力气。1. 排序算法认知框架怎么分类为什么先看“稳不稳定”1.1 按比较方式分比较排序与非比较排序排序算法第一个维度的分类是看它是否依赖元素之间的两两比较。冒泡、选择、插入、希尔、归并、快速、堆这七个统统属于比较排序。它们的核心操作都是“比较两个元素的大小然后决定是否交换位置”。理论上任何能比较大小的数据都能用它们排序这是比较排序最大的通用性优势。计数排序则属于非比较排序。它不比较元素大小而是利用元素本身的整数值作为索引统计每个值出现的次数再按顺序输出。这要求数据必须是有限范围内的整数或者能映射成整数但换来的是惊人的 O(nk) 时间复杂度在很多场景里比比较排序快一个量级。理解这个分类有什么用它直接决定了你在实战中的选型。数据是 float 且范围巨大计数排序直接出局数据是 0 到 100 分的考试成绩计数排序就是降维打击。1.2 稳定性到底是什么为什么重要稳定性这个指标新手常常忽略但它恰恰是工程场景里最要命的一个属性。稳定排序的定义是如果两个元素的值相等排序后它们的相对顺序保持不变。也就是说在原始数组里位置在前的那个相等元素排序后仍然在前。为什么这很重要想象一个员工列表你先按部门排了一次序现在想按薪水再排一次。如果第二次排序是稳定的那么同薪水的员工之间依然保持着部门排序的顺序如果算法不稳定第二次排序会把第一次排序的结果完全打乱。很多真实业务系统都是这种多层排序需求。所以 Java 的Collections.sort、Python 的sorted底层才要费那么大劲去实现稳定排序。八大排序里冒泡、插入、归并是稳定的选择、希尔、快速、堆是不稳定的计数排序通过特定写法可以做到稳定。1.3 复杂度的三种视角最好、平均、最坏分析排序算法时不能只看平均复杂度最好和最坏同样关键。冒泡排序最好情况是 O(n)数组已经有序优化后一轮扫描发现没有交换就退出最坏是 O(n^2)。快速排序平均 O(n log n)但最坏会退化到 O(n^2)这就是为什么要做随机化选 pivot。堆排序最坏也是 O(n log n)这是它最大的卖点。归并排序稳定在 O(n log n)但需要额外 O(n) 空间。面试时被问到“这个算法在什么情况下会变慢”本质就是在考察你是否理解算法内部的循环结构和数据分布之间的关系。2. 三大基础排序冒泡、选择、插入——先掌握“人的直觉”2.1 冒泡排序让大值像气泡一样上浮冒泡排序的思路非常直观重复遍历数组每次比较相邻两个元素如果顺序不对就交换。一轮遍历下来最大的元素就像气泡一样“浮”到了数组末尾。下一轮遍历就可以忽略已经就位的末尾区间。用 [5, 3, 8, 1, 9, 2, 7, 4, 6] 演示第一轮比较 5 和 3交换 → [3, 5, 8, 1, 9, 2, 7, 4, 6]比较 5 和 8不交换 → [3, 5, 8, 1, 9, 2, 7, 4, 6]比较 8 和 1交换 → [3, 5, 1, 8, 9, 2, 7, 4, 6]继续下去9 会一路交换到数组末尾。第一次完整遍历后9 固定在最后一位。第二次遍历时8 会被顶到倒数第二位。以此类推。def bubble_sort(arr): n len(arr) for i in range(n - 1): swapped False for j in range(n - 1 - i): if arr[j] arr[j 1]: arr[j], arr[j 1] arr[j 1], arr[j] swapped True if not swapped: break return arr这里有一个很关键的优化每轮设置swapped标志位。如果某一轮遍历下来没有任何交换说明数组已经完全有序可以直接退出此时最好情况退化为 O(n)。还可以进一步优化——记录最后一轮最后发生交换的位置last_swap。在这个位置之后的元素都已经排好序了下一轮只需要遍历到last_swap即可。冒泡排序是稳定的因为只有arr[j] arr[j1]时才交换相等的值不会越过彼此。它的时间复杂度平均和最坏都是 O(n^2)空间复杂度 O(1)。实际工作中几乎不会用冒泡排序处理真正的大数据。但它教学价值极高它清晰展示了“比较-交换”这个排序算法的基本单元而且代码里最容易出现的越界错误、循环边界错误都能在写冒泡时暴露出来。2.2 选择排序每次挑出最小值放到前面选择排序的思路比冒泡更“直男”第 i 轮扫描未排序区间找最小值和未排序区间的第一个元素交换位置。这样每一轮确定一个元素的最终位置总共需要 n-1 轮。以 [5, 3, 8, 1, 9, 2, 7, 4, 6] 为例第一轮扫描全数组找到最小值 1与下标 0 的 5 交换 → [1, 3, 8, 5, 9, 2, 7, 4, 6]第二轮扫描从下标 1 开始找到最小值 2与下标 1 的 3 交换 → [1, 2, 8, 5, 9, 3, 7, 4, 6]依此类推每一轮都有序区间扩大一格。def selection_sort(arr): n len(arr) for i in range(n - 1): min_idx i for j in range(i 1, n): if arr[j] arr[min_idx]: min_idx j if min_idx ! i: arr[i], arr[min_idx] arr[min_idx], arr[i] return arr选择排序的交换次数是 O(n) 级别最多 n-1 次交换。这一点在“写操作代价远大于读操作”的场景里有意义——比如对一块 EEPROM 进行排序擦写次数有限选择排序能最大程度减少写入次数。但要特别注意选择排序是不稳定的。举个例子数组 [3, 3, 1]第一轮找到最小值 1与第一个 3 交换结果变成 [1, 3, 3]。看似两个 3 的相对顺序没变换个例子 [3a, 3b, 2, 1]第一轮找到最小值 1与 3a 交换数组变成 [1, 3b, 2, 3a]。此时 3a 和 3b 的相对顺序已经翻转了。这个细节很多面试者会答错。你以为“选择最小值和前面的元素交换”不会破坏相等元素顺序但实际上交换是跨区间跳变的完全可能把后面的相等元素换到前面来。2.3 插入排序像整理扑克牌一样自然插入排序的思路就是打扑克牌时理牌的动作从第二个元素开始把当前元素插入到左侧已经有序的序列中的合适位置。为了腾出位置比当前元素大的那些元素要依次向右移动一位。以 [5, 3, 8, 1] 为例处理 3左侧有序序列是 [5]3 比 5 小5 右移3 插入到开头 → [3, 5, 8, 1]处理 8左侧 [3, 5]8 比 5 大不需要移动 → [3, 5, 8, 1]处理 1左侧 [3, 5, 8]1 比它们都小逐个右移插入到开头 → [1, 3, 5, 8]def insertion_sort(arr): for i in range(1, len(arr)): cur arr[i] j i - 1 while j 0 and arr[j] cur: arr[j 1] arr[j] j - 1 arr[j 1] cur return arr这里关键的一步是先用cur arr[i]把当前值存起来然后让比它大的元素逐个向右移动最后把它放到腾出来的位置。注意循环条件是arr[j] cur不是这是保证插入排序稳定的关键相等的元素遇到 cur 时不会移动保持了相对顺序。插入排序的绝活在于处理“基本有序”的数组。如果数组已经接近有序内层 while 循环很快就能停下来时间复杂度接近 O(n)。这一点被工程级排序算法大量利用——比如 Python 的 Timsort 会在归并前用插入排序处理小片段很多快速排序实现里当子数组长度小于某个阈值通常是 16 或 32时会改用插入排序收尾。插入排序代码在八大里最简单没有交换、只有移动对内存友好是写背文档时最容易手撸出来的排序。三个基础排序对比下来算法平均/最坏时间额外空间稳定性冒泡排序O(n²)O(1)稳定选择排序O(n²)O(1)不稳定插入排序O(n²)O(1)稳定它们的最坏复杂度都是平方级但在特定场景下插入排序完全能打赢一部分 O(n log n) 算法。这个反直觉的事实正是理解后面希尔排序和工程优化的重要铺垫。3. 进阶三选手希尔、归并、快速排序的进化逻辑3.1 希尔排序跨越步长的插入排序希尔排序是插入排序的改良版核心思想是“先让数组局部有序再逐步全局有序”。它把数组按一定步长 gap 分成若干组每组内部做插入排序然后缩小 gap继续分组排序直到 gap 为 1做最后一次完整的插入排序。gap 的选择很关键。最常见的写法是 gap 从 n/2 开始每次折半gap 4 时下标 0、4、8 一组1、5 一组2、6 一组3、7 一组每组内部插入排序。gap 2 时重新分组做插入排序。gap 1 时就是普通插入排序。def shell_sort(arr): n len(arr) gap n // 2 while gap 0: for i in range(gap, n): cur arr[i] j i while j gap and arr[j - gap] cur: arr[j] arr[j - gap] j - gap arr[j] cur gap // 2 return arr为什么这样会更快因为插入排序的痛点在于元素一次只能移动一位数据离目标位置很远时效率极低。希尔排序通过大步长的分组插入让元素在早期就能快速跳跃到“大致正确”的位置最后一步普通插入排序时数组已经基本有序内层循环的移动次数大大降低。希尔排序的复杂度分析是八大里最复杂的。它的时间复杂度取决于 gap 序列的选择折半序列的最坏情况是 O(n^2)但某些精心设计的序列比如 Sedgewick 序列可以把最坏复杂度压到 O(n^(4/3)) 甚至更好。注意希尔排序是不稳定的。因为在不同 gap 下分组跨越很远相等的值可能在某个中间步长下被跨越交换破坏了先后顺序。我在实际项目中几乎不用希尔排序——因为大多数编程语言自带的sort()已经比手写希尔强太多。但理解希尔排序的价值在于它展示了“优化一个平方级算法”的思路——通过预处理减少最终阶段的移动量。这种思路在刷题和设计更高层算法时依然有参考意义。3.2 归并排序分而治之的标准模板归并排序是分治思想的教科书级应用。它的逻辑分三步把数组从中间拆成两半分别递归排序最后把两个有序数组合并成一个有序数组。递归的终止条件是子数组长度为 1一个元素天然有序。合并的过程需要额外的辅助数组。准备两个指针 i 和 j 分别指向左半数组和右半数组的开头比较两个指针指向的值把较小的放入结果数组。如果左半的值小于等于右半的值优先取左半的——这个的选择是归并排序稳定的关键。def merge_sort(arr): if len(arr) 1: return arr mid len(arr) // 2 left merge_sort(arr[:mid]) right merge_sort(arr[mid:]) return merge(left, right) def merge(left, right): res [] i j 0 while i len(left) and j len(right): if left[i] right[j]: res.append(left[i]) i 1 else: res.append(right[j]) j 1 res.extend(left[i:]) res.extend(right[j:]) return res这个写法最简单但有额外开销——每次递归都创建新列表。工程上更常见的是“原地合并”版本的归并预先申请一个和原数组等长的辅助数组在递归过程中通过下标交替归并避免频繁分配内存。归并排序的时间复杂度稳定在 O(n log n)无论数据是否有序这个复杂度都不变。空间复杂度是 O(n)因为合并时需要辅助数组。归并排序最大的优势是稳定并且性能可预期。它也是外部排序的基石当数据量大到内存放不下时可以把数据分块读入内存分别排序后写回磁盘再做多路归并。这就是数据库、大数据框架里做大规模排序的基本策略。但归并排序的代价是额外空间和缓存不友好。对于纯内存排序它通常快不过优化良好的快速排序。3.3 快速排序工程应用最广的“表演型选手”快速排序是我最常用的排序也是说“排序必谈快排”的那个算法。它的步骤也很简单从数组里选一个基准值 pivot。分区partition把小于 pivot 的放左边大于 pivot 的放右边pivot 落在中间。递归对左右两个子区间做同样的操作。def quick_sort(arr, low, high): if low high: return pivot_idx partition(arr, low, high) quick_sort(arr, low, pivot_idx - 1) quick_sort(arr, pivot_idx 1, high) def partition(arr, low, high): pivot arr[high] i low - 1 for j in range(low, high): if arr[j] pivot: i 1 arr[i], arr[j] arr[j], arr[i] arr[i 1], arr[high] arr[high], arr[i 1] return i 1上面的实现是 Lomuto 分区简单但效率略低。实际工程更常用的是 Hoare 分区左右两个指针向中间靠拢左指针找大于 pivot 的右指针找小于 pivot 的找到就交换。它的交换次数更少常数更小。为什么快速排序叫“快速”因为它内部循环的细节对 CPU 缓存极度友好。它操作的是连续的内存块分区之后递归处理子区间局部性远好于归并排序那种来回复制数组的行为。所以同样 O(n log n) 复杂度实际运行时长通常比归并短。快速排序有两个著名的痛点。第一个是退化到 O(n^2)。如果 pivot 选得不好——比如对已经有序的数组固定选最后一个元素每次分区都极度不平衡——复杂度会退化到平方级。解决办法有几种随机选 pivot、三数取中取首、中、尾三个元素的中位数、以及在子数组规模小于阈值时改用插入排序。STL 的std::sort结合了这几种方案称为内省排序先做快排万一递归深度超过 log n 的某个阈值自动切换成堆排序保证最坏 O(n log n)。第二个是它不稳定。分区操作本身就是跨距离交换相等元素的相对顺序无法保证。用快排实战时我记得第一次把 Lomuto 分区写错成导致死循环时的崩溃感。后来总结出经验partition 里判断条件不要用统一用递归之前先检查low high。这些细节看似不起眼写错一次排查半小时。4. 堆排序与计数排序以及硬件视角的排序实现4.1 堆排序基于二叉堆的原地排序堆排序利用的是一种特殊的数据结构——二叉堆。我用大顶堆来排序堆顶是最大值把堆顶和堆末交换最大值就放到数组末尾了然后缩小堆的范围调整堆结构再次取堆顶……重复 n-1 次数组就有序了。建堆是从最后一个非叶子节点开始的逐个向下调整。def heap_sort(arr): n len(arr) for i in range(n // 2 - 1, -1, -1): heapify(arr, n, i) for i in range(n - 1, 0, -1): arr[i], arr[0] arr[0], arr[i] heapify(arr, i, 0) return arr def heapify(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] heapify(arr, n, largest)建堆的复杂度是 O(n)不是很多人直觉以为的 O(n log n)。因为越靠近叶子的节点下沉操作的次数越少累计计算下来是线性复杂度。调整堆的复杂度是 O(n log n)因为每次取堆顶后要下沉 log n 层。堆排序是真正意义上的原地排序只用 O(1) 额外空间而且最坏情况稳定在 O(n log n)。这些特点让它很适合内存极度受限、又必须保证性能上限的场景——比如嵌入式系统里的一段关键代码。但堆排序的实际运行速度通常比快速排序慢。原因在于堆的访问模式是跳跃式的数组下标按二叉树关系跳转CPU 缓存命中率非常差。同时堆排序的交换次数也偏多。所以工程上很少直接拿堆排序做通用排序它的主要价值在于“优先队列”这类需要不断取最大/最小值的场景以及作为内省排序的兜底方案。4.2 计数排序不比较大小的“数数”排序计数排序的思路清奇我没必要比较元素大小我只要知道每个值出现了几次然后从头到尾把值重新填回去。它的前提是数据范围有限且为整数。比如给一个班的成绩排序分数范围是 0 到 100那么建一个长度为 101 的计数数组遍历原始数据每个分数出现一次对应位置加 1最后按顺序输出。初学者最容易忽略的是“稳定”版本的计数排序写法。如果只是简单地从前往后填回数据排序结果虽然是升序的但不稳定。要让计数排序稳定需要做一步“前缀和”转换计数数组从第二个位置开始累加前一个位置的值这样每个元素位置值表示“该值以及小于它的值一共有多少个”。然后从原始数组的最后一个元素开始根据计数数组找到它的最终位置放入结果数组同时把计数数组对应位置减 1。def counting_sort(arr): if not arr: return arr k max(arr) 1 count [0] * k for num in arr: count[num] 1 # 前缀和count[i] 表示 i 的元素个数 for i in range(1, k): count[i] count[i - 1] output [0] * len(arr) for num in reversed(arr): output[count[num] - 1] num count[num] - 1 return output为什么从后往前遍历目的就是为了稳定。后出现的相同值先出队放进靠后的位置这样相同元素的相对顺序和原始数组保持一致。计数排序的时间复杂度是 O(n k)其中 k 是数据范围。当 k 远小于 n 时比如 100 万条分数在 0-100 之间的记录计数排序能秒杀所有比较排序。但 k 非常大时比如数据范围是 0 到 10^9计数数组根本开不出来只能考虑别的方案。4.3 当排序进入硬件9 个值排序的 RTL 实现思路热搜词里有“9个值排序算法RTL实现”这个方向很有意思值得单独展开聊。RTL 是寄存器传输级的缩写通常指用 Verilog 或 VHDL 这类硬件描述语言来设计数字电路。为什么软件里排得好好的序要拿到硬件里做因为有些场景对实时性和延迟的要求软件排序根本顶不住。比如网络报文调度、数据处理流水线里的帧重排、雷达信号处理数据一帧一到要求几个时钟周期内必须输出排序结果。软件跑排序可能有几十微秒甚至几毫秒的延迟硬件流水只需要几十个时钟周期。9 个值排序属于典型的“小规模排序”在 RTL 里实现时和软件完全不同软件追求通用和复杂度硬件追求并行度和流水线吞吐。最直接的思路是排序网络。所谓排序网络就是一组固定接线的比较器阵列每个比较器同时比较两个输入如果顺序不对就交换。比较器之间完全并行延迟只取决于比较器的级数。对于 9 个输入比较器网络的具体接法有多种常见的选择是 Batcher 奇偶归并网络或双调排序网络。理论上 9 个值用排序网络可以做到大约 7-9 级比较器延迟每一级内部的比较器都可以并行执行。另一种更适合硬件流式处理的方案是插入排序阵列设计一个由 9 个寄存器单元组成的链式结构每个时钟周期进入一个新值从链头开始依次与链上已有元素比较找到插入位置后面的元素逐个后移。这个结构像流水线数据吞吐量高但每个新值插入时最长需要 9 次比较时延会比较长。为降低关键路径延迟比较逻辑可以通过树形结构并行化。我见过不少工程师在 RTL 里做排序时踩过这些坑比较器的交换逻辑没有严格“同时取样”导致组合逻辑产生毛刺。解决办法是寄存器打拍先比较下一拍再交换。同步复位和异步复位的选择在排序链路里直接影响恢复时间建议用统一的同步复位。数据位宽不同会明显影响资源。9 个 8 位数值排序和 9 个 32 位数值排序面积差距很大设计前要确认位宽需求。真正做流式处理时必须给排序网络加握手信号和 valid 信号否则数据边界容易错乱。从软件排序到硬件排序最大的认知转变是软件排序优化的是比较次数和移动次数硬件排序优化的是级数和吞吐率。9 个值的场景软件怎么写循环都麻烦硬件反而可以用纯并行逻辑一两个周期出结果这就是“规模小反而适合硬件”的反直觉点。5. 八种排序横向对比与工程选型实战5.1 核心速查表复杂度、稳定性、场景一目了然把八种排序集中放在一起对比是面试前最值得背的一页排序算法平均时间复杂度最坏时间复杂度额外空间稳定性适用场景冒泡排序O(n²)O(n²)O(1)稳定教学示例数据量极小选择排序O(n²)O(n²)O(1)不稳定写代价高、交换次数要少插入排序O(n²)O(n²)O(1)稳定基本有序小规模排序希尔排序O(n log n)~O(n^(4/3))O(n²)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)不稳定内存受限最坏有上限计数排序O(n k)O(n k)O(k)稳定值域有限的整数排序这张表里最容易混淆的是快排和堆排的空间复杂度。快排的 O(log n) 额外空间其实是递归调用栈的开销不是真的额外数组。如果完全用非递归的迭代版快排这个空间可以压到 O(log n) 甚至更小。5.2 工程上到底怎么选不同数据特征下的决策路径实际开发里99% 的场景不需要你手写排序直接调库就行了。Python 的sorted()底层是 TimsortC 的std::sort底层是内省排序加插入排序Java 的Arrays.sort对对象用稳定归并、对基础类型用双轴快排。它们都经过极其充分的调优手写排序很难超越。但一旦你确实需要自己实现排序或者需要为某个系统挑选合适的排序策略决策路径可以参考这样几条数据量很小几百个以内直接选插入排序。它代码简单常数极小实测中在 n 小于 50 的时候插入排序经常快过快速排序因为它没有递归开销和分区开销。数据基本有序插入排序依然是王者。比如某个日志系统里新数据大概率比旧数据大偶尔有几条乱序插入排序一轮扫描就能完成大部分工作。数据量巨大但内存充足并且业务上要求稳定排序选归并排序。它不受初始数据分布影响最坏情况下也是 O(n log n)行为可预期。数据量巨大且内存很紧张选堆排序。它的原地性保证了 O(1) 额外空间同时最坏复杂度不退化。虽然实际速度可能不如快排但在内存受限的设备上少占几 MB 内存往往比快那么几毫秒更重要。数据是值域有限的整数比如 0-100 的成绩、IPv4 端口号、年龄等直接上计数排序。不要去写什么快排归并计数排序常数极小代码也简单。数据量巨大到内存放不下只能走外部排序。标准做法是把大文件拆成多块每块在内存里排序后写回磁盘然后多路归并。归并排序在这里是不可替代的。5.3 面试高频追问与避坑心得排序算法是面试重灾区面试官特别喜欢在基础题后面追几个“如果不做优化会怎样”的问题。结合我自己面试和被面试的经验以下问题出现频率最高为什么要区分稳定和不稳定不要只说“相等元素保持相对顺序”。要补充实际场景比如先按时间排序后按优先级排序稳定排序才能保留两层顺序关系。快速排序最坏什么时候发生数组完全有序且每次选到的 pivot 都是当前区间最大或最小值时递归树退化成链复杂度 O(n^2)。解决方案是随机选 pivot 或三数取中。很多面试者知道“最坏是 O(n^2)”却说不清怎么避免这就是经验差异。堆排序为什么不是稳定排序因为堆在调整下沉时父节点会和子节点交换这些交换是跨距离的完全可能让相等的两个元素相对位置翻转。这个解释最好结合一个具体例子。为什么工程库普遍用快排而不是归并快排缓存局部性好、原地交换避免大量内存拷贝常数更小。归并被用作 Timsort 的基础主要因为其稳定性和对“基本有序”数据的友好性。O(n log n) 是所有比较排序的理论下限吗是的。可以用决策树证明n 个元素的排列有 n! 种可能决策树至少 n! 个叶子节点树高至少 log(n!)约等于 n log n。只有绕开比较模型比如计数排序、桶排序、基数排序才有可能突破这个下限。我自己踩过的一个印象最深的坑是写快排时脑子里想着“稳定”结果给 partition 加了一个辅助数组去模拟归并的稳定行为代码跑起来比归并还慢。后来才醒悟当稳定性是硬需求时应该直接选择稳定的算法归并、插入等而不是去改造一个天生不稳定的算法。改造不仅增加复杂度还会引入各种隐蔽 bug。最后说点个人体会排序算法写多了我有一个很深的体会每一个看似“平平无奇”的排序算法背后都对应着一种解决问题的思维范式。冒泡是暴力枚举选择是贪心视野插入是动态维护希尔是分阶段逼近归并是分治合并快排是选定基准拆分堆排序是数据结构驱动计数排序是用空间换时间。这些范式会潜移默化地影响你解决其他问题的能力。比如处理一个流式数据求中位数的问题我会立刻想到用两个堆来维护处理一个订单列表需要多条件排序时我会立刻想到稳定排序要不要保底。这种“排序思维”一旦建立很多问题的解法都是顺手拈来。另外给刚接触排序的朋友一个建议不要只看代码和复杂度表一定要动手在草稿纸上把每一轮排序的过程画出来至少画一遍插入排序、快排、归并排序的完整执行过程。画完你会发现自己对“元素怎么移动”这个问题的理解上了不止一个台阶。我当时自学的时候把每个排序都画过至少三轮后来面试被问任何细节都能脱口而出。排序是一个看起来简单、其实很深的话题。八大排序只是起点后面还有基数排序、桶排序、双调排序、外排序这些延伸内容。先把这八个吃透数据结构的地基就算打牢了。 
长河君 · 2026/9/15 17:11:27 · 阅读 1.2k 八大排序算法全解析：原理、复杂度、稳定性与工程选型
提到“八大排序算法”新入门的朋友第一反应通常是到底是哪八个说实话这个“八”并没有一个完全统一的标准版本。常见的组合是冒泡、选择、插入、希尔、归并、快速、堆、计数这八个也有地方会把基数排序、桶排序拉进来把计数挤出去或者干脆列出十种。但不管名单怎么变核心思路永远是那些——搞清楚“比较排序”和“非比较排序”两大分支掌握每个算法的原理、复杂度、稳定性和适用场景比死记硬背是哪八个重要得多。这篇文章我会站在一个常年写排序、也经常帮人调试排序代码的工程师角度把这八个最常用的排序算法完整讲透。包括每一步是怎么执行的、为什么要这么设计、代码怎么写、有哪些坑、工程上到底该选谁以及那些“面试官爱问但书里不写”的细节。如果你是准备笔试面试的计算机专业学生或者正在做数据结构课程设计、需要手写排序的开发者这篇应该能帮你省下不少查资料的力气。1. 排序算法认知框架怎么分类为什么先看“稳不稳定”1.1 按比较方式分比较排序与非比较排序排序算法第一个维度的分类是看它是否依赖元素之间的两两比较。冒泡、选择、插入、希尔、归并、快速、堆这七个统统属于比较排序。它们的核心操作都是“比较两个元素的大小然后决定是否交换位置”。理论上任何能比较大小的数据都能用它们排序这是比较排序最大的通用性优势。计数排序则属于非比较排序。它不比较元素大小而是利用元素本身的整数值作为索引统计每个值出现的次数再按顺序输出。这要求数据必须是有限范围内的整数或者能映射成整数但换来的是惊人的 O(nk) 时间复杂度在很多场景里比比较排序快一个量级。理解这个分类有什么用它直接决定了你在实战中的选型。数据是 float 且范围巨大计数排序直接出局数据是 0 到 100 分的考试成绩计数排序就是降维打击。1.2 稳定性到底是什么为什么重要稳定性这个指标新手常常忽略但它恰恰是工程场景里最要命的一个属性。稳定排序的定义是如果两个元素的值相等排序后它们的相对顺序保持不变。也就是说在原始数组里位置在前的那个相等元素排序后仍然在前。为什么这很重要想象一个员工列表你先按部门排了一次序现在想按薪水再排一次。如果第二次排序是稳定的那么同薪水的员工之间依然保持着部门排序的顺序如果算法不稳定第二次排序会把第一次排序的结果完全打乱。很多真实业务系统都是这种多层排序需求。所以 Java 的Collections.sort、Python 的sorted底层才要费那么大劲去实现稳定排序。八大排序里冒泡、插入、归并是稳定的选择、希尔、快速、堆是不稳定的计数排序通过特定写法可以做到稳定。1.3 复杂度的三种视角最好、平均、最坏分析排序算法时不能只看平均复杂度最好和最坏同样关键。冒泡排序最好情况是 O(n)数组已经有序优化后一轮扫描发现没有交换就退出最坏是 O(n^2)。快速排序平均 O(n log n)但最坏会退化到 O(n^2)这就是为什么要做随机化选 pivot。堆排序最坏也是 O(n log n)这是它最大的卖点。归并排序稳定在 O(n log n)但需要额外 O(n) 空间。面试时被问到“这个算法在什么情况下会变慢”本质就是在考察你是否理解算法内部的循环结构和数据分布之间的关系。2. 三大基础排序冒泡、选择、插入——先掌握“人的直觉”2.1 冒泡排序让大值像气泡一样上浮冒泡排序的思路非常直观重复遍历数组每次比较相邻两个元素如果顺序不对就交换。一轮遍历下来最大的元素就像气泡一样“浮”到了数组末尾。下一轮遍历就可以忽略已经就位的末尾区间。用 [5, 3, 8, 1, 9, 2, 7, 4, 6] 演示第一轮比较 5 和 3交换 → [3, 5, 8, 1, 9, 2, 7, 4, 6]比较 5 和 8不交换 → [3, 5, 8, 1, 9, 2, 7, 4, 6]比较 8 和 1交换 → [3, 5, 1, 8, 9, 2, 7, 4, 6]继续下去9 会一路交换到数组末尾。第一次完整遍历后9 固定在最后一位。第二次遍历时8 会被顶到倒数第二位。以此类推。def bubble_sort(arr): n len(arr) for i in range(n - 1): swapped False for j in range(n - 1 - i): if arr[j] arr[j 1]: arr[j], arr[j 1] arr[j 1], arr[j] swapped True if not swapped: break return arr这里有一个很关键的优化每轮设置swapped标志位。如果某一轮遍历下来没有任何交换说明数组已经完全有序可以直接退出此时最好情况退化为 O(n)。还可以进一步优化——记录最后一轮最后发生交换的位置last_swap。在这个位置之后的元素都已经排好序了下一轮只需要遍历到last_swap即可。冒泡排序是稳定的因为只有arr[j] arr[j1]时才交换相等的值不会越过彼此。它的时间复杂度平均和最坏都是 O(n^2)空间复杂度 O(1)。实际工作中几乎不会用冒泡排序处理真正的大数据。但它教学价值极高它清晰展示了“比较-交换”这个排序算法的基本单元而且代码里最容易出现的越界错误、循环边界错误都能在写冒泡时暴露出来。2.2 选择排序每次挑出最小值放到前面选择排序的思路比冒泡更“直男”第 i 轮扫描未排序区间找最小值和未排序区间的第一个元素交换位置。这样每一轮确定一个元素的最终位置总共需要 n-1 轮。以 [5, 3, 8, 1, 9, 2, 7, 4, 6] 为例第一轮扫描全数组找到最小值 1与下标 0 的 5 交换 → [1, 3, 8, 5, 9, 2, 7, 4, 6]第二轮扫描从下标 1 开始找到最小值 2与下标 1 的 3 交换 → [1, 2, 8, 5, 9, 3, 7, 4, 6]依此类推每一轮都有序区间扩大一格。def selection_sort(arr): n len(arr) for i in range(n - 1): min_idx i for j in range(i 1, n): if arr[j] arr[min_idx]: min_idx j if min_idx ! i: arr[i], arr[min_idx] arr[min_idx], arr[i] return arr选择排序的交换次数是 O(n) 级别最多 n-1 次交换。这一点在“写操作代价远大于读操作”的场景里有意义——比如对一块 EEPROM 进行排序擦写次数有限选择排序能最大程度减少写入次数。但要特别注意选择排序是不稳定的。举个例子数组 [3, 3, 1]第一轮找到最小值 1与第一个 3 交换结果变成 [1, 3, 3]。看似两个 3 的相对顺序没变换个例子 [3a, 3b, 2, 1]第一轮找到最小值 1与 3a 交换数组变成 [1, 3b, 2, 3a]。此时 3a 和 3b 的相对顺序已经翻转了。这个细节很多面试者会答错。你以为“选择最小值和前面的元素交换”不会破坏相等元素顺序但实际上交换是跨区间跳变的完全可能把后面的相等元素换到前面来。2.3 插入排序像整理扑克牌一样自然插入排序的思路就是打扑克牌时理牌的动作从第二个元素开始把当前元素插入到左侧已经有序的序列中的合适位置。为了腾出位置比当前元素大的那些元素要依次向右移动一位。以 [5, 3, 8, 1] 为例处理 3左侧有序序列是 [5]3 比 5 小5 右移3 插入到开头 → [3, 5, 8, 1]处理 8左侧 [3, 5]8 比 5 大不需要移动 → [3, 5, 8, 1]处理 1左侧 [3, 5, 8]1 比它们都小逐个右移插入到开头 → [1, 3, 5, 8]def insertion_sort(arr): for i in range(1, len(arr)): cur arr[i] j i - 1 while j 0 and arr[j] cur: arr[j 1] arr[j] j - 1 arr[j 1] cur return arr这里关键的一步是先用cur arr[i]把当前值存起来然后让比它大的元素逐个向右移动最后把它放到腾出来的位置。注意循环条件是arr[j] cur不是这是保证插入排序稳定的关键相等的元素遇到 cur 时不会移动保持了相对顺序。插入排序的绝活在于处理“基本有序”的数组。如果数组已经接近有序内层 while 循环很快就能停下来时间复杂度接近 O(n)。这一点被工程级排序算法大量利用——比如 Python 的 Timsort 会在归并前用插入排序处理小片段很多快速排序实现里当子数组长度小于某个阈值通常是 16 或 32时会改用插入排序收尾。插入排序代码在八大里最简单没有交换、只有移动对内存友好是写背文档时最容易手撸出来的排序。三个基础排序对比下来算法平均/最坏时间额外空间稳定性冒泡排序O(n²)O(1)稳定选择排序O(n²)O(1)不稳定插入排序O(n²)O(1)稳定它们的最坏复杂度都是平方级但在特定场景下插入排序完全能打赢一部分 O(n log n) 算法。这个反直觉的事实正是理解后面希尔排序和工程优化的重要铺垫。3. 进阶三选手希尔、归并、快速排序的进化逻辑3.1 希尔排序跨越步长的插入排序希尔排序是插入排序的改良版核心思想是“先让数组局部有序再逐步全局有序”。它把数组按一定步长 gap 分成若干组每组内部做插入排序然后缩小 gap继续分组排序直到 gap 为 1做最后一次完整的插入排序。gap 的选择很关键。最常见的写法是 gap 从 n/2 开始每次折半gap 4 时下标 0、4、8 一组1、5 一组2、6 一组3、7 一组每组内部插入排序。gap 2 时重新分组做插入排序。gap 1 时就是普通插入排序。def shell_sort(arr): n len(arr) gap n // 2 while gap 0: for i in range(gap, n): cur arr[i] j i while j gap and arr[j - gap] cur: arr[j] arr[j - gap] j - gap arr[j] cur gap // 2 return arr为什么这样会更快因为插入排序的痛点在于元素一次只能移动一位数据离目标位置很远时效率极低。希尔排序通过大步长的分组插入让元素在早期就能快速跳跃到“大致正确”的位置最后一步普通插入排序时数组已经基本有序内层循环的移动次数大大降低。希尔排序的复杂度分析是八大里最复杂的。它的时间复杂度取决于 gap 序列的选择折半序列的最坏情况是 O(n^2)但某些精心设计的序列比如 Sedgewick 序列可以把最坏复杂度压到 O(n^(4/3)) 甚至更好。注意希尔排序是不稳定的。因为在不同 gap 下分组跨越很远相等的值可能在某个中间步长下被跨越交换破坏了先后顺序。我在实际项目中几乎不用希尔排序——因为大多数编程语言自带的sort()已经比手写希尔强太多。但理解希尔排序的价值在于它展示了“优化一个平方级算法”的思路——通过预处理减少最终阶段的移动量。这种思路在刷题和设计更高层算法时依然有参考意义。3.2 归并排序分而治之的标准模板归并排序是分治思想的教科书级应用。它的逻辑分三步把数组从中间拆成两半分别递归排序最后把两个有序数组合并成一个有序数组。递归的终止条件是子数组长度为 1一个元素天然有序。合并的过程需要额外的辅助数组。准备两个指针 i 和 j 分别指向左半数组和右半数组的开头比较两个指针指向的值把较小的放入结果数组。如果左半的值小于等于右半的值优先取左半的——这个的选择是归并排序稳定的关键。def merge_sort(arr): if len(arr) 1: return arr mid len(arr) // 2 left merge_sort(arr[:mid]) right merge_sort(arr[mid:]) return merge(left, right) def merge(left, right): res [] i j 0 while i len(left) and j len(right): if left[i] right[j]: res.append(left[i]) i 1 else: res.append(right[j]) j 1 res.extend(left[i:]) res.extend(right[j:]) return res这个写法最简单但有额外开销——每次递归都创建新列表。工程上更常见的是“原地合并”版本的归并预先申请一个和原数组等长的辅助数组在递归过程中通过下标交替归并避免频繁分配内存。归并排序的时间复杂度稳定在 O(n log n)无论数据是否有序这个复杂度都不变。空间复杂度是 O(n)因为合并时需要辅助数组。归并排序最大的优势是稳定并且性能可预期。它也是外部排序的基石当数据量大到内存放不下时可以把数据分块读入内存分别排序后写回磁盘再做多路归并。这就是数据库、大数据框架里做大规模排序的基本策略。但归并排序的代价是额外空间和缓存不友好。对于纯内存排序它通常快不过优化良好的快速排序。3.3 快速排序工程应用最广的“表演型选手”快速排序是我最常用的排序也是说“排序必谈快排”的那个算法。它的步骤也很简单从数组里选一个基准值 pivot。分区partition把小于 pivot 的放左边大于 pivot 的放右边pivot 落在中间。递归对左右两个子区间做同样的操作。def quick_sort(arr, low, high): if low high: return pivot_idx partition(arr, low, high) quick_sort(arr, low, pivot_idx - 1) quick_sort(arr, pivot_idx 1, high) def partition(arr, low, high): pivot arr[high] i low - 1 for j in range(low, high): if arr[j] pivot: i 1 arr[i], arr[j] arr[j], arr[i] arr[i 1], arr[high] arr[high], arr[i 1] return i 1上面的实现是 Lomuto 分区简单但效率略低。实际工程更常用的是 Hoare 分区左右两个指针向中间靠拢左指针找大于 pivot 的右指针找小于 pivot 的找到就交换。它的交换次数更少常数更小。为什么快速排序叫“快速”因为它内部循环的细节对 CPU 缓存极度友好。它操作的是连续的内存块分区之后递归处理子区间局部性远好于归并排序那种来回复制数组的行为。所以同样 O(n log n) 复杂度实际运行时长通常比归并短。快速排序有两个著名的痛点。第一个是退化到 O(n^2)。如果 pivot 选得不好——比如对已经有序的数组固定选最后一个元素每次分区都极度不平衡——复杂度会退化到平方级。解决办法有几种随机选 pivot、三数取中取首、中、尾三个元素的中位数、以及在子数组规模小于阈值时改用插入排序。STL 的std::sort结合了这几种方案称为内省排序先做快排万一递归深度超过 log n 的某个阈值自动切换成堆排序保证最坏 O(n log n)。第二个是它不稳定。分区操作本身就是跨距离交换相等元素的相对顺序无法保证。用快排实战时我记得第一次把 Lomuto 分区写错成导致死循环时的崩溃感。后来总结出经验partition 里判断条件不要用统一用递归之前先检查low high。这些细节看似不起眼写错一次排查半小时。4. 堆排序与计数排序以及硬件视角的排序实现4.1 堆排序基于二叉堆的原地排序堆排序利用的是一种特殊的数据结构——二叉堆。我用大顶堆来排序堆顶是最大值把堆顶和堆末交换最大值就放到数组末尾了然后缩小堆的范围调整堆结构再次取堆顶……重复 n-1 次数组就有序了。建堆是从最后一个非叶子节点开始的逐个向下调整。def heap_sort(arr): n len(arr) for i in range(n // 2 - 1, -1, -1): heapify(arr, n, i) for i in range(n - 1, 0, -1): arr[i], arr[0] arr[0], arr[i] heapify(arr, i, 0) return arr def heapify(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] heapify(arr, n, largest)建堆的复杂度是 O(n)不是很多人直觉以为的 O(n log n)。因为越靠近叶子的节点下沉操作的次数越少累计计算下来是线性复杂度。调整堆的复杂度是 O(n log n)因为每次取堆顶后要下沉 log n 层。堆排序是真正意义上的原地排序只用 O(1) 额外空间而且最坏情况稳定在 O(n log n)。这些特点让它很适合内存极度受限、又必须保证性能上限的场景——比如嵌入式系统里的一段关键代码。但堆排序的实际运行速度通常比快速排序慢。原因在于堆的访问模式是跳跃式的数组下标按二叉树关系跳转CPU 缓存命中率非常差。同时堆排序的交换次数也偏多。所以工程上很少直接拿堆排序做通用排序它的主要价值在于“优先队列”这类需要不断取最大/最小值的场景以及作为内省排序的兜底方案。4.2 计数排序不比较大小的“数数”排序计数排序的思路清奇我没必要比较元素大小我只要知道每个值出现了几次然后从头到尾把值重新填回去。它的前提是数据范围有限且为整数。比如给一个班的成绩排序分数范围是 0 到 100那么建一个长度为 101 的计数数组遍历原始数据每个分数出现一次对应位置加 1最后按顺序输出。初学者最容易忽略的是“稳定”版本的计数排序写法。如果只是简单地从前往后填回数据排序结果虽然是升序的但不稳定。要让计数排序稳定需要做一步“前缀和”转换计数数组从第二个位置开始累加前一个位置的值这样每个元素位置值表示“该值以及小于它的值一共有多少个”。然后从原始数组的最后一个元素开始根据计数数组找到它的最终位置放入结果数组同时把计数数组对应位置减 1。def counting_sort(arr): if not arr: return arr k max(arr) 1 count [0] * k for num in arr: count[num] 1 # 前缀和count[i] 表示 i 的元素个数 for i in range(1, k): count[i] count[i - 1] output [0] * len(arr) for num in reversed(arr): output[count[num] - 1] num count[num] - 1 return output为什么从后往前遍历目的就是为了稳定。后出现的相同值先出队放进靠后的位置这样相同元素的相对顺序和原始数组保持一致。计数排序的时间复杂度是 O(n k)其中 k 是数据范围。当 k 远小于 n 时比如 100 万条分数在 0-100 之间的记录计数排序能秒杀所有比较排序。但 k 非常大时比如数据范围是 0 到 10^9计数数组根本开不出来只能考虑别的方案。4.3 当排序进入硬件9 个值排序的 RTL 实现思路热搜词里有“9个值排序算法RTL实现”这个方向很有意思值得单独展开聊。RTL 是寄存器传输级的缩写通常指用 Verilog 或 VHDL 这类硬件描述语言来设计数字电路。为什么软件里排得好好的序要拿到硬件里做因为有些场景对实时性和延迟的要求软件排序根本顶不住。比如网络报文调度、数据处理流水线里的帧重排、雷达信号处理数据一帧一到要求几个时钟周期内必须输出排序结果。软件跑排序可能有几十微秒甚至几毫秒的延迟硬件流水只需要几十个时钟周期。9 个值排序属于典型的“小规模排序”在 RTL 里实现时和软件完全不同软件追求通用和复杂度硬件追求并行度和流水线吞吐。最直接的思路是排序网络。所谓排序网络就是一组固定接线的比较器阵列每个比较器同时比较两个输入如果顺序不对就交换。比较器之间完全并行延迟只取决于比较器的级数。对于 9 个输入比较器网络的具体接法有多种常见的选择是 Batcher 奇偶归并网络或双调排序网络。理论上 9 个值用排序网络可以做到大约 7-9 级比较器延迟每一级内部的比较器都可以并行执行。另一种更适合硬件流式处理的方案是插入排序阵列设计一个由 9 个寄存器单元组成的链式结构每个时钟周期进入一个新值从链头开始依次与链上已有元素比较找到插入位置后面的元素逐个后移。这个结构像流水线数据吞吐量高但每个新值插入时最长需要 9 次比较时延会比较长。为降低关键路径延迟比较逻辑可以通过树形结构并行化。我见过不少工程师在 RTL 里做排序时踩过这些坑比较器的交换逻辑没有严格“同时取样”导致组合逻辑产生毛刺。解决办法是寄存器打拍先比较下一拍再交换。同步复位和异步复位的选择在排序链路里直接影响恢复时间建议用统一的同步复位。数据位宽不同会明显影响资源。9 个 8 位数值排序和 9 个 32 位数值排序面积差距很大设计前要确认位宽需求。真正做流式处理时必须给排序网络加握手信号和 valid 信号否则数据边界容易错乱。从软件排序到硬件排序最大的认知转变是软件排序优化的是比较次数和移动次数硬件排序优化的是级数和吞吐率。9 个值的场景软件怎么写循环都麻烦硬件反而可以用纯并行逻辑一两个周期出结果这就是“规模小反而适合硬件”的反直觉点。5. 八种排序横向对比与工程选型实战5.1 核心速查表复杂度、稳定性、场景一目了然把八种排序集中放在一起对比是面试前最值得背的一页排序算法平均时间复杂度最坏时间复杂度额外空间稳定性适用场景冒泡排序O(n²)O(n²)O(1)稳定教学示例数据量极小选择排序O(n²)O(n²)O(1)不稳定写代价高、交换次数要少插入排序O(n²)O(n²)O(1)稳定基本有序小规模排序希尔排序O(n log n)~O(n^(4/3))O(n²)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)不稳定内存受限最坏有上限计数排序O(n k)O(n k)O(k)稳定值域有限的整数排序这张表里最容易混淆的是快排和堆排的空间复杂度。快排的 O(log n) 额外空间其实是递归调用栈的开销不是真的额外数组。如果完全用非递归的迭代版快排这个空间可以压到 O(log n) 甚至更小。5.2 工程上到底怎么选不同数据特征下的决策路径实际开发里99% 的场景不需要你手写排序直接调库就行了。Python 的sorted()底层是 TimsortC 的std::sort底层是内省排序加插入排序Java 的Arrays.sort对对象用稳定归并、对基础类型用双轴快排。它们都经过极其充分的调优手写排序很难超越。但一旦你确实需要自己实现排序或者需要为某个系统挑选合适的排序策略决策路径可以参考这样几条数据量很小几百个以内直接选插入排序。它代码简单常数极小实测中在 n 小于 50 的时候插入排序经常快过快速排序因为它没有递归开销和分区开销。数据基本有序插入排序依然是王者。比如某个日志系统里新数据大概率比旧数据大偶尔有几条乱序插入排序一轮扫描就能完成大部分工作。数据量巨大但内存充足并且业务上要求稳定排序选归并排序。它不受初始数据分布影响最坏情况下也是 O(n log n)行为可预期。数据量巨大且内存很紧张选堆排序。它的原地性保证了 O(1) 额外空间同时最坏复杂度不退化。虽然实际速度可能不如快排但在内存受限的设备上少占几 MB 内存往往比快那么几毫秒更重要。数据是值域有限的整数比如 0-100 的成绩、IPv4 端口号、年龄等直接上计数排序。不要去写什么快排归并计数排序常数极小代码也简单。数据量巨大到内存放不下只能走外部排序。标准做法是把大文件拆成多块每块在内存里排序后写回磁盘然后多路归并。归并排序在这里是不可替代的。5.3 面试高频追问与避坑心得排序算法是面试重灾区面试官特别喜欢在基础题后面追几个“如果不做优化会怎样”的问题。结合我自己面试和被面试的经验以下问题出现频率最高为什么要区分稳定和不稳定不要只说“相等元素保持相对顺序”。要补充实际场景比如先按时间排序后按优先级排序稳定排序才能保留两层顺序关系。快速排序最坏什么时候发生数组完全有序且每次选到的 pivot 都是当前区间最大或最小值时递归树退化成链复杂度 O(n^2)。解决方案是随机选 pivot 或三数取中。很多面试者知道“最坏是 O(n^2)”却说不清怎么避免这就是经验差异。堆排序为什么不是稳定排序因为堆在调整下沉时父节点会和子节点交换这些交换是跨距离的完全可能让相等的两个元素相对位置翻转。这个解释最好结合一个具体例子。为什么工程库普遍用快排而不是归并快排缓存局部性好、原地交换避免大量内存拷贝常数更小。归并被用作 Timsort 的基础主要因为其稳定性和对“基本有序”数据的友好性。O(n log n) 是所有比较排序的理论下限吗是的。可以用决策树证明n 个元素的排列有 n! 种可能决策树至少 n! 个叶子节点树高至少 log(n!)约等于 n log n。只有绕开比较模型比如计数排序、桶排序、基数排序才有可能突破这个下限。我自己踩过的一个印象最深的坑是写快排时脑子里想着“稳定”结果给 partition 加了一个辅助数组去模拟归并的稳定行为代码跑起来比归并还慢。后来才醒悟当稳定性是硬需求时应该直接选择稳定的算法归并、插入等而不是去改造一个天生不稳定的算法。改造不仅增加复杂度还会引入各种隐蔽 bug。最后说点个人体会排序算法写多了我有一个很深的体会每一个看似“平平无奇”的排序算法背后都对应着一种解决问题的思维范式。冒泡是暴力枚举选择是贪心视野插入是动态维护希尔是分阶段逼近归并是分治合并快排是选定基准拆分堆排序是数据结构驱动计数排序是用空间换时间。这些范式会潜移默化地影响你解决其他问题的能力。比如处理一个流式数据求中位数的问题我会立刻想到用两个堆来维护处理一个订单列表需要多条件排序时我会立刻想到稳定排序要不要保底。这种“排序思维”一旦建立很多问题的解法都是顺手拈来。另外给刚接触排序的朋友一个建议不要只看代码和复杂度表一定要动手在草稿纸上把每一轮排序的过程画出来至少画一遍插入排序、快排、归并排序的完整执行过程。画完你会发现自己对“元素怎么移动”这个问题的理解上了不止一个台阶。我当时自学的时候把每个排序都画过至少三轮后来面试被问任何细节都能脱口而出。排序是一个看起来简单、其实很深的话题。八大排序只是起点后面还有基数排序、桶排序、双调排序、外排序这些延伸内容。先把这八个吃透数据结构的地基就算打牢了。