手写排序算法全解析：从基础到工程实战的选型指南

1. 这年头为什么还要手写排序算法

先把话说在前头：日常开发里，我几乎不会自己写排序，直接用语言内置的sort()就完事了。但"不会写排序"和"不懂排序"是两码事，很多面试题、性能问题排查、甚至数据结构设计，最后都会绕回排序算法的基本原理上。

网上关于排序算法的资料多到看不过来，但大部分要么是纯理论推导，要么是动画演示，跟实际工程场景隔着一层。我打算换个角度，从"算法各自是什么脾气"出发，聊聊冒泡、选择、插入、快排、归并、堆排这几种最常见的排序，重点是它们分别适合什么场景、会踩什么坑、代码怎么写才不容易出错。

不管你是刚学编程的初学者，还是已经写了几年业务代码想补基础的老手，这篇文章都能给你一些参考。我会给出可运行的代码思路，也会解释为什么某种排序快、某种排序慢，以及工程上那些你没有留意过的取舍。

先说一个很多初学者没想通的问题：排序算法的好坏到底怎么衡量？写业务代码时，我们只管功能对，可一旦数据量大起来，不同算法之间的差距是天壤之别。衡量排序性能主要看三件事：时间复杂度、空间复杂度、稳定性。

• 时间复杂度：数据规模n变大时，算法耗时的增长趋势。O(n²)意味着数据翻一倍，耗时翻四倍；O(n log n)意味着数据翻一倍，耗时只多一点点。这两者在n到十万级别时，差距就已经是几十倍了。
• 空间复杂度：排序过程额外占用多少内存。有的算法在原地折腾数组（原地排序），有的算法需要额外拷贝一份数据（非原地排序）。内存紧张时这一点很致命。
• 稳定性：排序后，相同值的元素相对顺序是否保持不变。听起来很学术，但实际应用里重要得很，比如先按时间排序、再按地区排序，如果第二轮排序不稳定，第一轮的先后关系就全乱了。

这三个指标像三个互相拉扯的约束条件，没有十全十美的排序。快速排序快但不够稳定（指稳定性），归并排序稳定但吃内存，堆排序省内存但实际跑起来并不快。工程选择就是取舍。

2. 基础三兄弟：冒泡、选择、插入，到底谁最实用

很多教程把冒泡排序放在第一位，因为它好理解，代码也短。但说实话，开发五年我一次都没在正经项目里用过冒泡排序，它更适合当教学示例，不适合干活。这节我把三个"O(n²)级别的排序"放一起对比，重点想讲明白：它们思路上有什么区别、为什么插入排序是三者里唯一值得留意的。

2.1 冒泡排序：最直观，也最慢

冒泡的核心思路是"相邻比较，逐步把最大的数送到最后"。就像气泡从水里往上冒，每一轮都会有一个元素到达它最终的位置上。

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)。不加这个标记的教科书写法，不管数组有序没序都傻乎乎地跑完n²次比较，白白浪费很多时间。

冒泡为什么慢？因为它的"交换操作"太频繁了。每次发现逆序就必须交换，而交换本身是个开销比较大的操作（尤其在数组元素是复杂对象时）。每次比较都可能触发一次交换，所以最坏情况下比较n²/2次，交换也差不多n²/2次，双重暴击。

2.2 选择排序：交换次数最少，但"尝试最少"不等于快

选择排序的思路是：每一轮找出数组剩余部分的最小值，放到当前轮次的起始位置。它有个突出的优点：交换次数固定为n-1次，是所有排序里最少的。如果数组元素是体积很大的对象，交换一次的成本很高，选择排序在"交换成本"这个维度很有优势。

def selection_sort(arr): n = len(arr) for i in range(n): min_idx = i for j in range(i + 1, n): if arr[j] < arr[min_idx]: min_idx = j arr[i], arr[min_idx] = arr[min_idx], arr[i] return arr

但选择排序有一个非常容易被忽略的问题：它不稳定。看这个例子：数组[4, 2, 3, 4']（两个4，用4'区分），第一轮找到最小值2，交换到开头，这没什么问题；但后续遍历过程中，某个相等元素的相对位置可能会被跨过。我在实际应用里很少单独用选择排序，因为数组元素是简单数字时，交换成本不高，选择排序的优势体现不出来；数组元素是复杂对象时，稳定性又恰恰是更稀缺的特性。

不过有一点要说清楚：选择排序的比较次数仍然跟冒泡一样是O(n²)。交换少只意味着"写入操作"少，但"读取和比较"还得跑满，所以整体依然慢。少干活不意味着总工作量小，这个道理在排序领域反复出现。

2.3 插入排序：小而美的逆袭者

插入排序的思路比前两者更接近"人类整理扑克牌的手感"：每次把一个新元素插入到已经排好序的子数组的正确位置上，后面的元素统一往后挪。

def insertion_sort(arr): for i in range(1, len(arr)): key = arr[i] j = i - 1 while j >= 0 and arr[j] > key: arr[j + 1] = arr[j] j -= 1 arr[j + 1] = key return arr

插入排序是这三个基础算法里最有工程价值的一个，原因有三：

第一，最好情况是O(n)。如果输入数据本身基本有序，内层while循环基本不执行，排序几乎只在做线性扫描。这个特性被后面的归并排序和Timsort直接利用。

第二，它是稳定排序。当arr[j] > key时停止，等于说相同元素不会互换位置。在需要保持稳定性的场景里，插入排序是靠谱的兜底选择。

第三，对小数组非常友好。虽然O(n²)在大数组上很难看，但当n只有几十个时，O(n²)和O(n log n)的实际差距根本看不出来，反而插入排序的常数开销更小、代码更简单、缓存利用率也高。所以很多工业级排序算法里都能看到它的身影——数据分到很小的块之后，直接用插入排序收尾。

提示：如果你做完一次快排后发现数据量已经小于某个阈值（比如16），很多实现会索性切到插入排序，这个"混合策略"是排序算法在工程落地的常态。

3. 进阶主力：快排、归并、堆排的正确打开方式

基础排序讲完，来看真正具备工程价值的三个O(n log n)排序。它们都是"分而治之"或"树结构"思路在排序上的应用，但细节差别很大，用不好会从O(n log n)退化到O(n²)，甚至跑得比插入排序还慢。

3.1 快速排序：最快，但也最容易写错

快速排序的思路是"选一个基准值（pivot），把比它小的放左边，比它大的放右边，然后左右递归"。之所以叫"快速"，是因为平均时间复杂度O(n log n)，常数开销还非常小——它排序过程中比较和交换都发生在数组内部，缓存命中率很高，这一点在真实硬件上优势极大。

快排的代码模板我非常推荐背下来，但更重要的是理解分区那一行：

def quick_sort(arr, low, high): if low >= high: return arr p = partition(arr, low, high) quick_sort(arr, low, p - 1) quick_sort(arr, p + 1, high) return arr 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

快排的"快"其实依赖于一个隐前提：每次分区尽量把数组对半劈开。如果每次选中的pivot都恰好是最大值或最小值，分区之后一侧永远是空的，递归深度退化成O(n)，时间复杂度也退化成O(n²)。这时快排反而成了一个效率极低的排序，连选择排序都不如。

怎么缓解？三个手段：

• 随机选pivot：避免"输入数据本身有序"导致每次选中最大/最小值的尴尬。这是最省事、也最常用的手段。
• 三数取中：取首、中、尾三个元素的中位数作为pivot。比纯随机更稳定，实现也不复杂。
• 递归深度过深时换算法：快到一定深度尚未结束就转而用堆排序兜底。C++的std::sort内部就是这么干的（IntroSort策略）。

另外记住：快排不稳定，而且不保证O(n log n)最坏情况。千万别在"稳定性必须保证"的场景硬用快排。

3.2 归并排序：稳定性和可预测性最优

归并排序的思路是"先拆到底，再两两合并"。把数组对半拆分到每个子数组只剩一个元素，然后反复把两个有序数组合并成一个有序数组。它的时间复杂度稳定在O(n log n)，不管数据乱到什么程度都不退化，这是它比快排稳的关键。

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): i = j = 0 result = [] while i < len(left) and j < len(right): if left[i] <= right[j]: result.append(left[i]) i += 1 else: result.append(right[j]) j += 1 result.extend(left[i:]) result.extend(right[j:]) return result

我上面这份代码是"简化教学版"，它有个很大的问题：每次递归都创建新的切片数组，额外空间开销极大。更工程的做法是预先分配一个辅助数组，通过索引在原数组和辅助数组之间来回倒腾。但核心思想是一样的：合并时只要保证相等元素取左边，就天然稳定。

归并排序的短板是空间复杂度O(n)。它需要额外的存储空间来装合并过程中的数据。内存紧张的大型数组场景，这个开销可能比时间开销更致命。

它在什么场景不可替代？外部排序。比如要对一个远超内存的大文件做排序，内存明显不够，这时只能用归并排序的思路：把文件切成能塞进内存在大小的块分别排序（也可以对块内部用快排），再对有序块做多路归并。在这种"数据放不下内存"的场景，归并排序几乎是唯一选择。

3.3 堆排序：极致的空间利用率

堆排序的思路是利用"最大堆"的性质：堆顶永远是最大值，把堆顶和最后一个元素交换，堆的大小减一，然后调整堆结构，循环往复，最终数组就是升序排列的。

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) 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

堆排序的独特优势是：原地排序，额外空间O(1)，最坏情况O(n log n)。这三个特点放在一起非常能打：它不会像快排那样退化到O(n²)，不会像归并那样额外占O(n)空间。听起来是完美的排序，为什么实际工程里还是很少用它？

因为它的常数开销太大了。堆排序的访问模式非常跳跃：数组下标不断在2*i+1和2*i+2之间跳，这导致缓存命中率很低。而快排是顺序扫描数组，归并虽然也跳跃但存在局部的顺序访问区段。现代计算机是缓存敏感的系统，快排的实际运行速度往往是堆排序的2到3倍，这就是为什么"算法复杂度相同"但实际体验差异巨大。

堆排序最适合的场景，反而是需要持续获取最大值/最小值的地方，也就是优先队列和TopK问题。比如"十万个数据里找前100个最大数"，用小顶堆非常方便：堆满100个后，新元素比堆顶大就替换堆顶并调整堆结构，遍历完一遍就是答案。这种场景堆排序的价值远超快排和归并。

3.4 三种进阶排序的表格式对比

这个表格我自己看过无数遍，但真正理解它需要一个场景之外的视角：没有哪个算法是绝对王者，关键看约束条件是时间、空间，还是稳定性。这也是排序题在面试里高频出现的原因——它是考察候选人对复杂度理解和工程权衡的绝佳题目。

4. 工程实践中的排序：标准库实现的混搭策略

前面讲的都是"某种单独算法"，但工业级排序库里，几乎不会只依赖一种算法。这节我们来聊聊真实代码库里的排序长什么样，以及你自己写排序时应该怎么借鉴这些经验。

4.1 Python排序：Timsort的"识别有序片段"策略

Python的排序算法叫Timsort，它的核心思路是识别数组中已经有序片段（run），然后把这些片段用归并的方式串起来。如果数组本身接近有序，Timsort能在接近O(n)的时间内完成排序。这一点对于真实世界的数据意义巨大——很多业务数据天然带有某种顺序性，比如时间戳排序、日志数据、部分已排序的列表。

Timsort还有一层实用策略：当一个run的长度小于阈值（在CPython参考实现里是32或64），就使用插入排序把这个run扩展到阈值长度。这就是前面说"插入排序的逆袭"在工程里的真实落脚点。Python中list.sort()和sorted()都以Timsort实现，并且都保证稳定排序，所以你可以放心地用Python默认排序处理复杂对象。

4.2 C++标准库排序：IntroSort的"三保险"策略

C++ 的std::sort常用的实现方式是IntroSort。它是一个混搭策略：

1. 一开始用快排的递归框架。
2. 当递归深度超过某个阈值（通常是2 * log(n)），说明快排选择的pivot质量很差，数据分布很不均匀，就切换到堆排序。
3. 当待排序区间长度小于某个阈值（通常是16左右），直接用插入排序收尾。

这样做的好处是：先享受快排的常数小、缓存友好的优势；在快排遇到"有序数组+糟糕pivot"这种退化场景时，通过堆排序兜底，保证最坏情况O(n log n)；小数组用插入排序，避免快排递归的函数调用开销。

这个"混搭"思路我特别想强调一下，因为很多人只记单个算法，从没想过它们可以组合。工程排序的本质不是选一个最好的算法，而是组合多个算法，让每个算法在最擅长的数据规模/区间上发挥作用。

4.3 自适配（Adaptive）排序：观察数据特征再决定策略

现代排序库还有一个共性：排序算法会先"观察"数据的特征，再决定使用什么策略。比如：

• 如果数组很短（比如len小于某个阈值），直接插入排序。
• 如果数组已经基本有序，Timsort会检测到很多可利用的有序run，走接近线性的路径。
• 如果数组元素是数值类型，可能用基数排序（Radix Sort）的思路加速，因为数字有确定的位级特征。

设计你自己的排序函数时，值得把这层"观察"加进去。与其纠结"用快排还是归并"，不如先看一眼数据特征：规模多大、是否接近有序、是否允许额外空间、元素是简单数字还是复杂对象。回答完这几个问题，排序策略基本就清晰了。

5. 排序算法选型清单：遇到实际需求怎么决策

理论讲了一大堆，最终还是要解决实际问题。我把这些年做项目时总结的一套排序算法决策思路整理一下，当你面对真实场景时可以直接按顺序问自己几个问题。

5.1 决策清单：从数据规模到稳定性要求

第一问：数据规模有多大？

• n小于50左右：直接插入排序即可。不用纠结，代码简单，常数小，跟什么高级排序比差距都在微秒级别，没必要折腾。
• n在几千到几十万：快排或归并，两者都行。不想处理pivot退化问题就归并，内存吃紧就快排加随机pivot。
• n达到几千万、上亿：单机内存已经撑不住，考虑外部归并排序；或者用堆做分布式归并的底层组件。
• 数据量远超内存：外部排序、多路归并，几乎不考虑别的。

第二问：内存允许额外占用吗？

• 严格限内存（比如嵌入式、游戏引擎）：堆排序或原地快排。
• 可以接受O(n)的额外空间：归并排序，稳且快。

第三问：稳定性有要求吗？

• 有（比如按多个字段依次排序）：归并排序，或者直接调用语言内置的稳定排序。
• 没有：快排优先，实测更快。

第四问：数据有什么特殊特征吗？

• 数据已经有部分有序：Timsort或者插入排序。
• 数据是有限范围整数（比如0到10000）：桶排序或计数排序可以达到O(n)，比任何比较排序都快得多。这个很多人不知道，但我实际用过一次，效果惊掉下巴。
• 数据是分布式的大文件：不用说了，归并排序体系。

5.2 用对排序的常见误区

误区一：排序算法越快越好？

不一定。如果数据量就几十个元素，O(n²)排序和O(n log n)排序实测没差别，反而O(n²)排序代码更少、可读性更好，出bug概率也低。很多同学一上来就堆快排代码，最后调试半天没搞定pivot逻辑，属实没必要。

误区二：语言内置排序够用了，不用学别的？

大部分情况确实够用。但当你需要"部分排序"（找TopK）、"按多个键排序但要保持顺序"、"在内存受限环境排序大数组"时，内置接口给不了你最优解。理解底层算法意味着你能判断出什么时候不该用内置排序，改用堆、归并或者桶排序。

误区三：原地排序一定比非原地排序好？

缓存、内存访问模式、数据拷贝开销，都是影响排序实测速度的因素。归并排序虽然占用额外空间，但在很多实现里它跑得比堆排序快得多，因为顺序写入的开销远小于跳跃访问。

5.3 TopK问题的实操案例

光说不练不行，我分享一个上个月实际碰到的问题。场景：一个用户行为分析模块，每天有约200万条用户访问记录，需要找出访问次数最多的前500个用户。数据量不大不小，恰恰是"一内存装得下，但直接全排序有点浪费"的典型场景。

最直观的做法是全量排序再取前500个，时间复杂度O(n log n)。数据200万条，全量排序大概耗时几秒。但我用一个小顶堆，堆大小固定为500，遍历一遍数据，只要新元素比堆顶（当前第500小的元素）大，就替换堆顶并调整堆结构，时间复杂度只有O(n log 500)，实测从几秒降到一两百毫秒，性能提升了十几倍。这个思路几乎没多写代码，但对高耗时的排序场景来说收益是巨大的。

当时的核心代码长这样：

import heapq def top_k_frequent(freq_map, k): heap = [] for user, count in freq_map.items(): if len(heap) < k: heapq.heappush(heap, (count, user)) elif count > heap[0][0]: heapq.heapreplace(heap, (count, user)) return [item[1] for item in heap]

注意这里堆存的是"最小的k个"，取出来时要手动反转。写这个逻辑时想清楚一点：堆顶是当前候选者里最小的那个，新数据要来比的是堆顶，而不是堆里任意一个元素。这是我见过初学者最容易写错的地方。

6. 排错实录：排序代码常见的翻车点和自查方法

很多排序代码逻辑没错，但一跑就结果不对，或者性能差得离谱。下面整理几个我踩过的坑和帮别人排查时高频出现的问题，按频率从高到低排列。

6.1 边界条件翻车：off-by-one错误

最常见的翻车点是索引边界。不管是快排的partition返回下标时到底要不要包含pivot，还是归并的mid = len // 2之后左右区间的划分，只要差一个位置，排序结果就会出现神秘的错位。

我的自查方法很简单：写完排序后，用边界数组测一下——空数组、单个元素、两个元素、所有元素相等、完全逆序、完全有序。这些小case能快速暴露绝大多数off-by-one错误。不要上来就跑随机大数组，那是浪费时间的排查路径。

6.2 递归深度爆炸：Python递归排序的隐患

快排和归并在Python里都用递归实现，Python默认递归深度限制是1000。如果排序的数据量超过几百上千，递归深度可能超过这个限制，直接抛RecursionError。这个问题我在用Python实现归并排序时就遇到过：对大数组跑分治排序，连续深入递归，栈帧越来越多。

两个解决办法：

• 调用sys.setrecursionlimit()提高递归上限，但这是治标不治本，递归过深依然可能爆栈。
• 把递归改为显式栈迭代。工程上我更推荐这个做法，虽然代码长一点，但彻底规避了递归深度问题。

顺带提醒：快排在"数据有序+pivot选得差"时递归深度退化成O(n)，即使数据量不大也可能把栈打穿。

6.3 稳定性"隐形丢失"：比较大小用>还是>=的区别

在归并合并的时候，如果写成if left[i] < right[j]而不是if left[i] <= right[j]，那么遇到相等元素时会优先取右侧的元素，导致稳定性丢失。这类bug非常隐蔽，表面看排序结果完全正确，但如果你依赖稳定性再按第二个字段排序，顺序就乱了。

排查思路：要对稳定性做断言式验证，构造一个由(字段1, 字段2)组成的数组，先按字段2排序，再按字段1排序，最后检查字段1相等元素间字段2是否保持升序。这一步能快速暴露问题。

6.4 性能远低于预期时的排查路径

排序算法跑得比理论预期慢得多，通常不是算法本身复杂度错了，而是以下三件事之一：数据访问模式不好（堆排序式的跳跃访问）、比较操作成本过高（每次比较都触发复杂的对象方法而非简单的数字大小比较）、以及不必要的元素拷贝（每次交换都在复制大对象）。

排查步骤：先跑一个"纯数字数组"的基准，再看"真实对象数组"的基准，两者差距过大说明问题在比较/拷贝成本，不在算法本身。此时你要做的不是换排序算法，而是优化比较器的开销——这是很多性能工程师忽视的一点。

7. 提效经验：我常用的排序调试和验证技巧

最后分享几个这几年沉淀下来的排序调试手段，它们不常出现在教科书里，但实际排查问题时就靠它们保命。

技巧一：写一个"排序是否正确"的通用验证函数。我并不建议每次写完排序都在print(arr)里肉眼观察结果。更可靠的方式是拿arr == sorted(arr)做断言。因为内置排序写了很多年，经受了无数边界case的检验，把它当正确答案非常可靠。每次写完新排序都用随机数据、边界数据、重复值数据分别跑一遍断言，能在一分钟内覆盖掉99%的基础错误。

技巧二：用"对比计数法"定位性能瓶颈。在排序代码里注入比较次数和交换次数的计数器，跟理论值对比。比如快排平均比较次数大约在n log n附近，如果计数比这个值高出好几倍，基本能断定pivot选得不好导致分区失衡。一眼定位问题方向，再针对调整。

技巧三：画"运行轨迹图"代替脑补。对算法初学阶段，我强烈建议把每次排序完的数组合并打印出来，或者用缩进表现出递归的层级。这种可视化的方式让你一眼看到快排的分区是否均衡、归并的合并顺序是否合理。调试完成了再删掉这些打印，代码量不多也占不了几行，但对排错帮助极大。

技巧四：善用"几乎有序"和"彻底逆序"两组特殊数据。排序算法在不同分布的数据上表现差异很大，只测随机数据会掩盖很多问题。比如插入排序在"几乎有序"数据上表现极好，但同样是这组数据，快排如果不做随机pivot可能直接跑出O(n²)。这两组数据是排序算法"照妖镜"，测试时一定不要漏掉。

技巧五：比较器要显式定义，别依赖默认行为。Python里sorted(arr, key=lambda x: x.field)能按字段排，但如果你写的是arr.sort()，它按什么规则排取决于元素类型。对象没有定义比较逻辑时，字典序和对象地址序可能完全不是你想要的结果。排序前先想清楚你需要的排序键，对工程排序而言，这个思考比选哪个算法更重要。

8. 代码模板速查：五种排序的干净写法

为了让你直接上手，我把用了很多次的"测试过、边界考虑过"的排序模板再完整贴一遍。建议不要死记硬背，而是理解每一行的作用。实际写代码时，如果能用内置排序就用内置排序，手写排序主要在面试/教学/特殊场景才需要。

快排（随机pivot版本，抗有序退化）：

import random def quick_sort(arr, low, high): if low >= high: return pivot_idx = random.randint(low, high) arr[pivot_idx], arr[high] = arr[high], arr[pivot_idx] 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] p = i + 1 quick_sort(arr, low, p - 1) quick_sort(arr, p + 1, high)

注意随机选pivot后要先把pivot交换到末尾，这样分区逻辑可以统一用最后一个元素作为pivot，代码更好读。这里可以加一个递归深度过大时转堆排序的兜底，篇幅有限不展开。

归并排序（迭代版，无递归爆栈风险）：

def merge_sort_iter(arr): n = len(arr) width = 1 aux = [0] * n while width < n: for left in range(0, n, 2 * width): mid = min(left + width, n) right = min(left + 2 * width, n) i, j, k = left, mid, left while i < mid and j < right: if arr[i] <= arr[j]: aux[k] = arr[i] i += 1 else: aux[k] = arr[j] j += 1 k += 1 while i < mid: aux[k] = arr[i] i += 1 k += 1 while j < right: aux[k] = arr[j] j += 1 k += 1 arr[:] = aux[:] width *= 2 return arr

这个版本的归并排序用"宽度翻倍"代替递归，从最小宽度1开始，每轮把相邻区间两两合并，直到整个数组有序。它不需要担心递归深度，也容易改成真正原地操作的版本（虽然原地归并的空间节省以复杂度和常数增加为代价）。

堆排序（非递归下沉版本）：

def heap_sort(arr): n = len(arr) for start in range(n // 2 - 1, -1, -1): sift_down(arr, start, n - 1) for end in range(n - 1, 0, -1): arr[end], arr[0] = arr[0], arr[end] sift_down(arr, 0, end - 1) return arr def sift_down(arr, start, end): root = start while 2 * root + 1 <= end: child = 2 * root + 1 if child + 1 <= end and arr[child] < arr[child + 1]: child += 1 if arr[root] < arr[child]: arr[root], arr[child] = arr[child], arr[root] root = child else: break

堆排序的sift_down里用的是while循环而不是递归，这是为了减少函数调用开销——堆排序本身常数已经不小了，没必要在一个下沉操作上再叠加递归成本。

提示：上面这些排序模板的测试优先级是：空数组 > 单元素 > 双元素 > 全部相等 > 逆序 > 大规模随机数据。按这个顺序测试，你能用最短时间覆盖大部分边界问题。

9. 面试中排序算法的高频考察点

如果你是在准备面试，排序算法几乎是必考项。这里整理一下面试中面试官真正想考察的点，以及准备时的优先级。

9.1 必会的手写：快排和归并

这两个是出现频率最高的手写排序。快排考的是partition的写法、pivot选择、退化分析；归并考的是合并逻辑的边界处理、稳定性判断。建议至少把这两个背到随手能写出来的程度，而且一定要写对while循环的边界。

关于手写代码，我有几条实用的建议：

• 写清楚循环不变量（每一步循环前后数组的状态是什么），有几行注释写几行，面试官非常看重思路清晰。
• 不要写"看似精简但看不懂"的代码。比如用切片方式写归并排序，看起来很干净，但实际工程上它空间开销大，面试官会追问这个问题，你答不上来就尴尬。
• 白板或在线编辑器里写完，主动提出"我用边界数据自测一下"，这个动作本身就是加分项。

9.2 复杂度分析要讲透"为什么"

面试官常问"快排为什么平均是O(n log n)"。合格的回答不是背结论，而是讲出分区过程：每次partition把数组分成两部分，平均每部分n/2，递归树高度约log n，每层合计比较约n次，所以总复杂度O(n log n)。同时要主动提退化条件，以及"为什么会退化"。

归并的复杂度分析跟快排类似，但要点是"即使数据如何分布，每次都能对半切分，所以最坏也是O(n log n)"。这里还能顺带讲外部排序的应用场景，展示你理解的真实场景比算法本身更深刻。

9.3 高频变种题：TopK、排序稳定性应用、多路归并

TopK问题几乎必考，用堆是标准解。此外，还有三个高频变种值得准备：

• 求中位数：快速选择算法（QuickSelect），本质是快排的partition只递归处理包含目标的一侧。
• 判断是否稳定：准备一个"按两个字段排序后检查稳定性"的测试代码。
• 有序链表合并：链表上的归并排序，空间O(1)版本的归并，比数组版本更考验编码功底。

这几个变种题，本质上考的都不是排序算法本身，而是你能不能把算法的核心思想迁移到另一个场景。理解了排序算法"分区"和"合并"的底层逻辑，这些变种基本就是顺水推舟的事。

写在最后：我的一点实际操作体会

排序算法是我认为最适合"一遍一遍手写练习"的算法类别。它不像图算法那样要建复杂的状态机，也不像动态规划那样需要很强的抽象建模能力，它只是涉及数组、递归、循环、边界条件，非常适合用来训练"把思路变成无bug代码"的基本功。

我自己的经历是：有段时间面试前突击练习排序，每天把快排、归并、堆排、插入排序各写两遍，坚持一周后，边界条件的直觉明显变强了。后来做业务项目里遇到TopK问题、分区排序问题、稳定性要求时，思考起来就像条件反射一样快。基础能力就是这样，练的时候花的是"死功夫"，但真正用起来才发现全是"捷径"。

最后留一个实践建议：别急着背模板。先不看任何参考代码，用语言描述思路，把排序算法的分区、合并、下沉这些核心操作想办法用最朴素的语言写出来，再对照标准模板改正。这个过程走完一遍，你对排序算法的理解深度会和"直接背下来"完全不同。如果这篇文章能在你啃排序算法的路上帮上一把，目的也就达到了。