企业官网建设流程全解析

1. 实验目标拆解：堆排序和分治到底要验证什么

算法设计与分析这门课里的"堆排序与分治"实验，名字听着像两个不相干的题目被硬凑在一起，实际上它是一条完整的主线：堆排序解决的是"每次从一堆数据里取出最值"的成本问题，分治解决的是"把一个大问题拆成同类的小问题"的组织问题。前者是数据结构层面的技巧，后者是算法设计层面的范式，两者合起来正好覆盖了实验课最想训练的两件事——能不能把抽象思想翻译成可以跑起来的代码，以及能不能用数据和曲线证明它真的达到了理论上的复杂度。

我带过几轮这类实验的辅导，最常见的场景是：代码抄完了，排序结果也对，但一问"你这个建堆为什么是 O(n)"就卡住，一问"快排为什么比归并慢了三倍"就开始猜。这不是学生的问题，是实验设计本身没把验证点说清楚。多数实验指导书只写了"实现堆排序与归并排序并比较运行时间"，却没告诉你比较的时候要控制哪些变量、每个复杂度结论对应哪一段代码、哪些现象属于算法本质、哪些现象纯粹是语言实现带来的噪音。这篇内容就是想把这块补上，把堆排序和分治这两条线从原理到代码到测量完整走一遍，适合正在做实验的同学，也适合想复习一下基础算法工程化的朋友。

1.1 堆排序：三项必须落到代码里的验证点

堆排序这个主题，实验里真正需要验证的东西只有三样，缺一样这个实验就只算"跑通"而不算"做完"。

第一是正确性。不是随便生成一组随机数排一遍对上了就完事，而是要把边界数据全部过一遍：空数组、单元素、全部相同、已经升序、已经降序、只有两个元素且逆序。堆排序的 bug 极容易藏在这些地方，比如下沉循环的终止条件写成child < end而不是child <= end，随机数据下大概率看不出来，一遇到两个元素就露馅。

第二是复杂度曲线。O(n log n) 不是一个能直接观测的量，你要做的是取若干个规模 n，测出耗时，然后看 n 翻倍时耗时涨了多少倍。如果 n 从一万涨到两万，耗时涨了大约 2 倍出头（log 项的影响），说明符合预期；如果涨了 4 倍，那基本可以断定某处藏着 O(n²) 的循环没被发现。

第三是空间与原地性。堆排序的一大卖点就是原地，只需要常数个辅助变量。实验里验证这一点不需要测量内存，只需要在报告里把它和归并排序的辅助空间做个对照，说清楚"为什么归并必须开一个 n 长的辅助数组，而堆排序不用"。这三项做扎实，堆排序这部分就立住了。

1.2 分治：递归式、合并代价与递归深度

分治这一侧要验证的东西稍微抽象一些，因为它不是一个具体算法，而是一种组织方式。实验里通常会选归并排序、快速排序、二分查找，有的还会加一道最大子段和。选这些题目不是为了多写几个函数，而是因为它们各自展示了分治的一个侧面。

归并排序展示的是合并代价等于 O(n) 时会发生什么，递归式是 T(n) = 2T(n/2) + Θ(n)，解出来 Θ(n log n)，这个结论要求你能把递归树画出来并数清每层有多少工作量。快速排序展示的是划分不均时会发生什么，同一套分治骨架，合并代价变成 O(1)（因为划分时元素已经就位，不需要额外合并），但递归的两个子问题规模可能极不平衡，最坏退化到 O(n²)。二分查找展示的是子问题只有一个时会怎样，T(n) = T(n/2) + O(1)，直接降到 O(log n)。

还有一个容易被忽略的验证点是递归深度。分治靠递归实现，递归就要吃调用栈。归并排序的递归深度是 log₂n，n 等于一百万时也才 20 层，非常安全；快速排序在最坏情况下递归深度是 n，n 一万的时候就可能把默认的递归上限撑爆。实验里如果只用随机数据测快排，永远看不到这个坑，必须专门构造一组已经有序的数据跑一次，让栈溢出真实发生一次，这个知识点才算真的学到手。

1.3 把实验做成可复现的对照实验

实验报告里最没有信息量的一句话是"堆排序比归并排序快/慢"。脱离具体条件，这句话没有意义。要让结论站得住，你得把它做成一个对照实验，固定住所有可能影响结果的变量。

需要固定的变量至少有四个：数据规模（取一组梯度而不是一个点）、数据分布（随机、有序、逆序、大量重复，这四种分布下三个算法的表现差异巨大）、计时方式（重复几次取中位数，而不是跑一次就记下来）、运行环境（同一台机器、同一个解释器版本、关闭其他大负载程序）。这四条固定住之后，剩下的差异才能归因到算法本身。

我一般会建议实验里至少放两张表：一张是"同一数据分布下，不同规模、不同算法的耗时表"，用来观察增长趋势；另一张是"同一规模下，不同数据分布、不同算法的耗时表"，用来观察算法对输入分布的敏感度。这两张表一出来，堆排序的稳定、快排的偏科、归并的稳当，全都藏不住了。

2. 堆排序：数组下标、下沉调整与线性建堆的算术

堆排序的代码加起来不到三十行，但它是整个实验里"能背下来"和"真的懂了"差距最大的一段。绝大多数人卡在两个地方：一是数组下标和树的父子关系怎么对应，二是建堆为什么明明是循环里套循环，复杂度却是 O(n) 而不是 O(n log n)。这两块讲透了，堆排序就没什么神秘的了。

2.1 为什么堆能塞进一个数组：下标映射与完全二叉树

堆在逻辑上是一棵二叉树，但实现上完全不需要指针和节点对象，一个数组就够了。前提是这棵树必须是完全二叉树——除了最后一层，每一层都填满，最后一层从左往右连续填充。这个约束保证了树的形状是唯一的，节点和数组下标之间能建立一一映射，不会出现空位。

按 0 开始编号的话，映射关系是这样的：下标 i 的节点，它的父节点是 (i-1)//2，左孩子是 2i+1，右孩子是 2i+2。反过来说，如果 2i+1 已经越界，说明这个节点是叶子。这套关系不用背，画一棵七个节点的树，把 0 到 6 填进去，自己推一遍就再也不会忘。

这里有个新手特别容易踩的坑：不少教材和网上代码用 1 开始编号（父 i//2，左 2i，右 2i+1），看起来更对称。但你如果把这套公式直接搬到 Python 或 C 的 0 基数组上，结果就是全部错位。我见过最冤的一种情况是，建堆循环写对了，排序阶段也写对了，就是取孩子的时候用了2*i和2*i+1，跑出来的数组"看起来有点像排好了但又不对"。这种错最难查，因为逻辑上完全讲得通，只是差了个 1。

数组存储的另一个好处是完全不需要额外的结构开销。如果用节点对象加左右指针，每个节点至少多两个指针字段，内存占用翻倍不说，遍历时的指针跳转还会带来大量缓存不命中。堆排序之所以能在原地排序里占据一席之地，靠的就是这种紧凑存储。

2.2 下沉与上浮的分工，以及边界判断的三种写法

堆的调整操作只有两个：下沉和上浮。名字很形象，下沉是把一个偏小的元素往下压，直到它比两个孩子都大（大顶堆的情况）；上浮是把一个偏大的元素往上顶，直到它比父节点小。

关键在于搞清楚什么时候用哪个。建堆用下沉，插入用上浮，删除堆顶用"末尾换到堆顶再下沉"。为什么建堆不从上往下一个个上浮插入？因为那样做是 n 次插入，每次 O(log n)，总共 O(n log n)；而从最后一个非叶节点往前逐个下沉，总代价是 O(n)。这个差别后面会算。

下沉的实现有三个细节决定成败。第一个是循环的终止条件。比较稳妥的写法是：

def sift_down(a, start, end): root = start while True: child = 2 * root + 1 if child > end: # 没有孩子，到底了 break if child + 1 <= end and a[child + 1] > a[child]: child += 1 # 选出两个孩子里更大的那个 if a[root] < a[child]: a[root], a[child] = a[child], a[root] root = child # 继续往下沉 else: break # 已经比孩子大了，停 return

这里end是当前堆的有效范围的最后一个下标，是闭区间。写成闭区间还是开区间都行，但一定要统一。我见过最隐蔽的 bug 是建堆时传n-1、排序时传end-1，两个地方差一个，结果排序排到后面几个元素就乱了。

第二个细节是先选孩子再比较。必须先确定左右孩子里谁大，拿大的那个去和父节点比。如果直接拿左孩子比，右孩子更大却不管，堆性质就破了。

第三个细节是交换后要更新 root 并继续循环，而不是递归调用。递归写法更直观，但每次下沉都多一层函数调用，在 Python 里这个开销相当可观，跑到百万级数据时能明显看出差距。用循环（迭代）写，把当前节点一路沉到底，是工程上的标准做法。

2.3 建堆是 O(n) 的：把那个求和式亲手算一遍

这是整个实验里最值得亲手推一遍的东西。很多人第一反应是：建堆循环 n/2 次，每次下沉最多 log n 层，那不就是 O(n log n) 吗？错在"每次最多 log n 层"这个估计太松了，绝大多数节点根本沉不了那么深。

正确的算法是按高度分类计数。定义节点的高度为它到最远叶子的边数，叶子高度是 0。在一个完全二叉树里，高度为 h 的节点大约有 n / 2^(h+1) 个。为什么？因为高度为 h 意味着这个节点下面挂了 h 层，它所在的位置越靠上，数量越少，而且是按 2 的幂次递减。

一个高度为 h 的节点，下沉时最多走 h 步，所以总代价是：

总代价 = Σ (高度为 h 的节点数) × h ≈ Σ (n / 2^(h+1)) × h = (n/2) × Σ (h / 2^h)

现在算 Σ(h / 2^h)，h 从 0 到无穷。这是个标准的幂级数，利用 Σ x^h = 1/(1-x)（当 |x| < 1），求导得 Σ h·x^(h-1) = 1/(1-x)²，两边乘 x 得 Σ h·x^h = x/(1-x)²。代入 x = 1/2，得到 (1/2)/(1/2)² = 2。

所以总代价 ≈ (n/2) × 2 = n，也就是O(n)。

这个推导建议在实验报告里自己写一遍，别抄。写的过程中你会真正理解"为什么从最后一个非叶节点往前遍历"——不是随便挑了个顺序，而是这个顺序保证每个节点被下沉时，它下面的子树已经是合法堆了，下沉一次就能到位，不会出现"沉下去之后上面的结构又坏了"需要回头重来的情况。

注意：建堆是 O(n)，但整个堆排序不是 O(n)。排序阶段要做 n-1 次"堆顶换到末尾 + 堆顶下沉"，每次下沉 O(log n)，这一段才是 O(n log n)。两段加起来取大头，总复杂度 O(n log n)。实验报告里如果只写"堆排序 O(n log n)"，不区分建堆和排序两个阶段，说明还没吃透。

2.4 排序阶段的交换细节与稳定性问题

建堆完成之后，数组第一个元素就是全局最大值。排序阶段的思路很朴素：把这个最大值和数组末尾交换，末尾那个位置就永久确定了；然后堆的有效范围缩小一格，新的堆顶大概率不满足堆性质，下沉一次修复；重复这个过程直到堆里只剩一个元素。

有一个常见的实现分歧：外层循环到底写for end in range(n-1, 0, -1)还是range(n-1, -1, -1)。前者循环到 1 就停，最后剩下下标 0 的元素自然就是最小值，不用再处理；后者会多跑一次无意义的交换。两种写法结果都对，但前者少一次操作，也更符合"堆里剩一个元素时它必然有序"的逻辑。

def heap_sort(a): n = len(a) if n <= 1: return a for i in range(n // 2 - 1, -1, -1): # 建堆，从最后一个非叶节点开始 sift_down(a, i, n - 1) for end in range(n - 1, 0, -1): # 每次把堆顶送到末尾 a[0], a[end] = a[end], a[0] sift_down(a, 0, end - 1) # 有效范围缩小一格 return a

再说稳定性。堆排序是不稳定的。举个具体例子：数组[5a, 5b, 3]（用 a、b 区分两个 5 的原始顺序）。建堆后堆顶是 5a，排序阶段把它换到末尾，变成[3, 5b, 5a]，两个 5 的相对顺序直接颠倒了。更普遍地说，堆排序里存在大量"跨越整个数组的远距离交换"，任何依赖相邻关系的顺序保证都会被破坏。

稳定性在实际业务里重要吗？看你排的是什么。排纯数字无所谓，排的是"按分数排序但同分要保持提交先后"这种带附属信息的记录时，不稳定就会出问题。实验里如果想验证这一点，可以构造(key, index)的元组列表，排序后检查同 key 的元素 index 是否还递增。这个验证花不了五分钟，但能让你对"稳定性"这个词有实感。

另外值得在报告里提一句的是堆排序的缓存不友好。下沉的时候访问的是 2i+1 和 2i+2，随着层数加深，访问位置的跨度越来越大，CPU 缓存基本帮不上忙。这一点在 C 语言里影响明显，在 Python 里被解释器开销盖住了不太看得出来，但它是堆排序在实践中常常跑不过快排的重要原因之一。

3. 分治：从递归式到复杂度，再到工程取舍

分治这三个字听起来像句废话——把问题分成小问题分别解决再合并，谁不会？真正的门槛在于判断"这个划分划得值不值"。划完之后子问题是不是同类、合并的成本有多大、递归会不会失控，这三个问题决定了分治是让复杂度降一个量级，还是白忙一场。

3.1 分治三步里，真正决定成败的是合并

标准的分治三步是：分解（把问题切成若干规模更小的同类子问题）、解决（递归处理子问题，规模够小时直接求解）、合并（把子问题的解拼成原问题的解）。教材里三步写得一样长，实际上难度分布极不均匀。

分解通常是最简单的，归并排序取中点、二分查找取中点、快排选个基准值，都是 O(1) 的操作。解决那一步是递归调用，代码上就是两行，没什么可写的。真正的功夫全在合并上，而且合并的代价直接决定了整个算法的复杂度。

拿归并排序来说，合并两个已排序的数组，最坏要比较 2n 次左右，代价是 Θ(n)。代进递归式 T(n) = 2T(n/2) + Θ(n)，解出来 Θ(n log n)——比朴素排序的 O(n²) 好，但没好到 O(n)。而快速排序呢，它压根没有合并步骤，划分的时候元素已经各就各位了，合并代价是 O(1)，所以递归式是 T(n) = T(k) + T(n-k) + Θ(n)，复杂度完全取决于划分是否均匀。

这里有个很好的反例可以放进实验报告：如果合并代价是 O(n²)，分治就白分了。假设你设计了一个算法，划分很漂亮，但合并要把左右两半两两配对比较，那总复杂度就是 O(n²)，和暴力法一样，还多了递归开销。所以判断一个分治设计好不好，先看合并那一步的代价，这一条比什么都重要。

3.2 递归树和主定理：两种算复杂度的手法对照

算分治复杂度有两个常用工具，实验里最好两个都用一遍，互相印证。

递归树法是画图。以归并排序为例，根节点是规模 n、代价 n；第一层两个节点各是 n/2、代价合计 n；第二层四个节点各 n/4、代价合计还是 n；一直分到规模为 1，一共 log₂n + 1 层。每层代价都是 n，层数是 log n，乘起来 Θ(n log n)。这个方法直观，能看清"每层工作量是否恒定"这个关键点，缺点是层数一多画起来累。

主定理是套公式。形式是 T(n) = aT(n/b) + f(n)，其中 a 是子问题个数，b 是规模缩小的倍数，f(n) 是分解加合并的代价。然后拿 f(n) 和 n^(log_b a) 比大小：

代进去算一遍归并排序：a=2，b=2，n^(log₂2) = n，f(n) = Θ(n)，两者同量级，落在第二种情况，结论 Θ(n log n)。二分查找：a=1，b=2，n^(log₂1) = n⁰ = 1，f(n) = O(1)，同量级，结论 Θ(log n)。

主定理用起来快，但它有前提条件：子问题规模必须严格等分，f(n) 要满足正则性条件。快速排序的平均情况就不满足"严格等分"，所以不能直接套，得用期望分析或者递归树法。实验报告里如果写了"快排用主定理得 O(n log n)"，严格说是不严谨的，这一点值得单独说明一句。

3.3 归并、快排、二分：三个分治样本的取舍逻辑

同样是分治，三个算法在工程上的取舍完全不同，这个对比是实验里最有价值的部分。

归并排序的标签是：稳定、O(n log n) 稳定保证、需要 O(n) 辅助空间、递归深度只有 log n。它的复杂度不随输入分布变化，无论数据是随机、有序还是逆序，都是 n log n 量级。适合的场景是外部排序（数据大到内存装不下，必须分块排序再归并）和需要稳定性的场合。

快速排序的标签是：不稳定、原地（辅助空间 O(log n) 的栈）、平均最快、最坏退化。它在实际中常常是通用排序里跑得最快的，原因不在复杂度而在常数：划分过程是顺序扫描，缓存友好；没有额外数组分配；内层循环极其紧凑。但一旦遇到已经有序的数据加上"取第一个元素当基准"这种朴素写法，直接退化到 O(n²)，并且递归深度达到 n。

二分查找展示的是另一个极端：子问题只有一个，所以复杂度从线性直接降到对数。它提醒我们，分治的威力不来自"分"，而来自"每分一次能扔掉多少"。扔掉一半，就是 log；扔掉一个，还是 n。

除了这三个，实验里加一道最大子段和会让分治的理解更完整，因为它的合并步骤不是简单的拼接，而是需要额外计算：

def max_subarray(a, lo, hi): if hi - lo == 1: return a[lo] mid = (lo + hi) // 2 best = max(max_subarray(a, lo, mid), max_subarray(a, mid, hi)) # 跨中点的情况：从中点往两边扫，取最大后缀 + 最大前缀 s = 0 left_best = float('-inf') for i in range(mid - 1, lo - 1, -1): s += a[i] left_best = max(left_best, s) s = 0 right_best = float('-inf') for i in range(mid, hi): s += a[i] right_best = max(right_best, s) return max(best, left_best + right_best)

这个算法的精妙之处在于：最大子段要么整段在左半边、要么整段在右半边、要么横跨中点。前两种靠递归，第三种靠从中间向两边扫一遍 O(n) 求出。递归式 T(n) = 2T(n/2) + O(n)，解出来 O(n log n)——比专门设计的 O(n) 动态规划解法慢，但它把"合并代价"这个概念演示得非常清楚，非常适合放进实验报告做对比。

3.4 递归深度与栈：怎么在 Python 里把递归写安全

分治离不开递归，递归离不开调用栈，而栈是有上限的。Python 默认的递归上限是 1000 层左右，超过就抛 RecursionError。归并排序的深度是 log₂n，n 等于十亿也才 30 层，完全不用担心；快排在最坏情况下深度是 n，n 过千就危险了。

处理办法有三个，按推荐程度排序。

第一个办法是把递归改成"先处理小的那一半，大的那一半用循环"。这是快排的标准优化，效果立竿见影：无论划分多不均衡，每次至少把较小的一侧彻底解决掉，栈深度上界从 O(n) 降到 O(log n)。

def quick_sort(a, lo=0, hi=None): if hi is None: hi = len(a) - 1 while lo < hi: pivot = a[(lo + hi) // 2] lt, i, gt = lo, lo, hi while i <= gt: if a[i] < pivot: a[lt], a[i] = a[i], a[lt] lt += 1 i += 1 elif a[i] > pivot: a[gt], a[i] = a[i], a[gt] gt -= 1 else: i += 1 # 短的一边递归，长的一边继续循环 if lt - lo < hi - gt: quick_sort(a, lo, lt - 1) lo = gt + 1 else: quick_sort(a, gt + 1, hi) hi = lt - 1

这段代码还顺带解决了另一个问题：大量重复元素。三路划分把数组分成"小于基准、等于基准、大于基准"三段，等于基准的那一段直接跳过不再递归。如果用的是两路划分，一千万个全是 5 的数组会把快排拖成 O(n²)，因为每次划分只能切掉一个元素。这个坑在真实数据里非常常见（比如按性别、按省份统计），实验里加一组"大量重复"的数据分布专门测一下，能看出巨大差异。

第二个办法是调高递归上限：sys.setrecursionlimit(100000)。这个办法能用，但风险不小——Python 的栈帧在堆上分配，调得太高会把内存吃光，真到极限时可能直接崩溃而不是抛出可捕获的异常。当作临时手段可以，别当常规方案。

第三个办法是完全迭代化，比如归并排序用自底向上的写法，从长度 1 开始两两归并，再四四归并，一层层往上推，完全没有递归。这个版本代码稍微绕一点，但没有任何栈风险，在大规模数据上还更快（少了函数调用开销）。实验里如果能同时给出递归版和迭代版归并排序的耗时对比，是个不错的加分项。

4. 实验现场：代码实现、计时框架与数据记录

原理讲完了，接下来是实验真正花时间的地方——把代码写对、把时间测准、把数据记下来。这一段是很多人实验报告拿不到高分的重灾区，代码能跑，但测出来的数据全是噪音。

4.1 三个排序实现（关键位置都写了注释）

先说一个原则：对比实验里所有算法必须用同一套接口、同一份输入、同样的复制方式。差异只能来自算法本身，不能来自输入构造方式的不同。

堆排序的完整实现前面给过了，这里补一个不依赖切片的归并排序。注意别用merge_sort(a[:mid])这种切片递归的写法，虽然代码短得像诗，但它每层都要拷贝一遍数组，总拷贝量是 O(n log n)，会让归并排序在大数据下额外多出一大块开销，拿这种版本去和堆排序比时间是不公平的——你测出来的是"归并排序加大量内存拷贝"的耗时，不是归并排序的真实水平。

def merge_sort(a): n = len(a) if n <= 1: return a buf = [0] * n def _sort(lo, hi): if hi - lo <= 1: return mid = (lo + hi) // 2 _sort(lo, mid) _sort(mid, hi) i, j, k = lo, mid, lo while i < mid and j < hi: # 用 <= 保证稳定性：左边相等时优先取左边 if a[i] <= a[j]: buf[k] = a[i] i += 1 else: buf[k] = a[j] j += 1 k += 1 while i < mid: buf[k] = a[i] i += 1 k += 1 while j < hi: buf[k] = a[j] j += 1 k += 1 for t in range(lo, hi): a[t] = buf[t] _sort(0, n) return a

if a[i] <= a[j]里的等号就是稳定性的来源，去掉等号（写成<）归并排序立刻变成不稳定的。这个细节小到一行，但它是"稳定排序"和"不稳定排序"的唯一区别，实验报告里值得单独标注。

验证正确性的最小闭环，我一般这么写：

import random def check(fn, n, dist='random'): if dist == 'random': data = [random.randint(-1000, 1000) for _ in range(n)] elif dist == 'sorted': data = list(range(n)) elif dist == 'reverse': data = list(range(n, 0, -1)) elif dist == 'duplicate': data = [random.randint(0, 9) for _ in range(n)] elif dist == 'single': data = [1] * n expect = sorted(data) got = fn(data[:]) assert got == expect, f"fail: n={n}, dist={dist}" return True

注意传进去的是data[:]，也就是副本。如果直接传data，函数会原地修改它，下一轮验证就全乱了。这个坑我见过不止一次，表现为"第一个算法测对了，第二个算法全错"，其实是第一个算法把原数组排好序了，第二个算法拿到的是有序输入。

4.2 计时框架：中位数采样与 GC 干扰

计时这件事，随便写个time.time()就记下来是最不可靠的做法。原因有三个：单次测量受系统调度影响可能偏出几倍；Python 的垃圾回收可能在某个时刻突然启动，吃掉一大块时间；time.time()的精度在某些平台上是毫秒级，测小规模数据时误差比真实值还大。

我用的模板是这样的：

import time, gc, statistics def bench(fn, base, repeat=7): times = [] for _ in range(repeat): arr = base.copy() # 复制放在计时窗口外 gc.disable() # 关掉 GC，避免中途触发 t0 = time.perf_counter() fn(arr) t1 = time.perf_counter() gc.enable() times.append(t1 - t0) return statistics.median(times), times

几个要点解释一下。复制必须放在计时窗口之外，否则你测的是"复制加排序"的时间，规模越大复制占比越高，把 O(n) 的复制混进 O(n log n) 的排序里，会拉平不同算法之间的差距。gc.disable()是关键一步，Python 的分代垃圾回收会在分配对象时随机触发，一次回收可能耗时几十毫秒，足以让某个算法的某次测量彻底失真。关掉之后再手动enable()，保证下一轮正常。perf_counter比time()精度高，它基于高精度计时器，适合测毫秒甚至微秒级的时间。取中位数而不是平均值，是因为平均值容易被个别异常值拉偏，中位数对离群点更稳健。

还有一条容易被忽略：每个算法要跑足够多次，但每次都用全新的数据副本。如果重复跑同一份数据，第一遍是随机数据，第二遍就已经是有序数据了，快排的耗时会掉一大截，堆排序则变化不大，比出来的结果毫无意义。

4.3 数据分布与规模梯度怎么设

数据规模我一般取六个点：1000、2000、5000、10000、20000、50000。再大不是不行，但 Python 里百万级的整数列表排序要几秒钟，四种分布乘以三个算法乘以七次重复，跑完要小半天，性价比不高。六个点足够看出增长趋势——尤其是 1000 到 2000、20000 到 50000 这两段的倍数关系，能明显区分 n log n 和 n²。

数据分布取五种，每种都有明确的验证目的：

注意"升序"和"逆序"两组在堆排序上不是完全对称的。升序输入建堆时几乎不需要下沉，因为每个父节点天然就比孩子大；逆序输入建堆时每个节点都要沉到底，建堆阶段的耗时明显更高。这个细微差别如果能在报告里点出来，说明你是真的观察了数据而不是抄了个表。

4.4 一张结果表和它背后的三个现象

下面这组数据是我在一次实验环境（普通笔记本、某版本的 Python 解释器、单线程）下跑出来的量级参考。具体数值会因为机器和版本差异很大，所以我不列精确数字，只给相对的倍数关系，你按这个趋势去对照自己的结果就行。

三个值得写进结论的现象：

第一，堆排序稳定但慢半拍。它和归并的复杂度一样，但 Python 里通常略慢于三路快排，主要原因是下沉时的跳访问对缓存不友好，而且每次交换都涉及两次赋值。这个差距不大，属于"合理范围"，不能说明堆排序没用——它的优势在空间上。

第二，归并排序的耗时随规模增长得比堆排序更明显。因为它要多分配一个 n 长的辅助数组，Python 里创建一个 n 元素列表的开销是可观的，规模越大这个开销占比越高。换成 C 语言写，两者会接近很多。

第三，朴素快排在特定输入下的崩溃是断崖式的。随机输入下它和优化版差不多，一旦换成升序或全部相同，耗时直接翻几十倍甚至直接栈溢出。这个对比比任何文字描述都有说服力，一定要在实验里跑出来。

5. 常见问题与排查技巧实录

这部分是我在实验室里被问得最多的问题的汇总，基本都是"代码跑得通但结果不对劲"这一类。按症状分类整理，配上排查路径，遇到问题时逐条对一遍，大多数 bug 十分钟内能定位。

5.1 正确性出问题：八成是下标和边界

排序结果不对，别急着怀疑算法思想，先怀疑下标。下面这几条是最常见的。

堆排序排出来"前面几个对，后面全乱"。这几乎可以断定是排序阶段的end参数传错了。下沉函数里end是闭区间上限，排序时第一次要传n-1，交换之后有效范围变成[0, end-1]，所以调用应该是sift_down(a, 0, end - 1)。如果写成sift_down(a, 0, end)，会在下沉时访问到已经被换到末尾的那个最大元素，把它又拖回堆里，堆性质就乱了。

归并排序结果里出现重复元素或者丢失元素。查合并循环的边界。三个 while 循环的分工是：第一个处理两边都还有元素的情况，后两个各自把剩下的一边搬完。常见的错误是第一个循环写成了while i < hi and j < hi，或者合并完成后忘了把buf里的内容写回a，或者写回时范围写成range(0, hi)而不是range(lo, hi)。最后这个最坑，因为它只在递归的右半边出错，而右半边的数据在小规模时可能"碰巧"是对的。

快速排序在某些输入下无限递归。检查划分后递归的区间。三路划分结束后，[lo, lt-1]是小于区，[lt, gt]是等于区，[gt+1, hi]是大于区。递归必须是(lo, lt-1)和(gt+1, hi)，绝对不能写成(lo, lt)或(lt, hi)，否则等于区被重复处理，如果等于区非空且不缩小，就是死递归。

边界数据的检查清单，每次改完代码都过一遍：

• []空数组，会不会因为n//2 - 1等于 -1 导致range(-1, -1, -1)正常跳过（这个其实安全）但其他语言里会数组越界；
• [1]单元素，range(0, 0, -1)为空，排序阶段range(0, 0, -1)也为空，直接返回；
• [2, 1]两元素逆序，验证交换和下沉；
• [1, 1, 1, 1]全相同，验证重复元素处理；
• [5, 4, 3, 2, 1]完全逆序，验证最坏输入。

5.2 性能数据反常：先怀疑测量方法

数据看起来不符合理论，先别改算法，先查测量。以下四种情况我遇到过很多次。

测出来快排永远最快，归并永远最慢。这通常是因为归并用了切片递归版本（a[:mid]），多出来的拷贝开销被算进了排序时间。换成带缓冲区的版本再测一次，差距会小很多。

同一算法两次测量差一倍。检查是不是没有关 GC，或者是在一个还有后台任务在跑的机器上测的。也可以看看是不是没有取中位数，直接用了第一次的结果。

小规模数据下归并反而比堆排序快。这是正常的，Python 内置的sorted是 Timsort，在短数组上会切换到插入排序，而你自己写的归并并没有这个优化。小规模数据（n 小于 100）的对比意义不大，从 1000 起步更合适。

规模翻倍，耗时涨了四倍。这是最需要警惕的信号，说明某处有隐藏的 O(n²)。常见来源：快排的朴素划分遇到重复元素；最大子段和的分治里"跨中点扫描"写成了双重循环；验证正确性时用了in或者list.index这种线性查找。

5.3 速查表：症状、病因、处理

再说两个不太容易想到的实操心得。

一个是别在计时区间里做任何格式化输出。有人喜欢在下沉函数里加个计数器统计交换次数，顺便print出来看看，这个print的开销足以让整个测量废掉。要统计操作次数，用变量累加，测完再一次性输出。

另一个是大规模测试前先做小规模正确性验证。五万规模的数据跑出错结果，你根本没法定位是哪一步错的；先用 10 个元素、20 个元素把结果和sorted()对上，再往上加规模。这个顺序反过来做，往往会浪费一两个小时。

最后分享一个我在实验报告里常用的呈现方式：不要只给一张耗时表，而是给"耗时除以 n log n"的归一化表。理论上这个比值应该接近常数，如果某一行的值突然变大，说明那个规模下出现了理论之外的开销（比如内存不够开始换页，或者递归太深受限）。这个方法能让你从一堆数字里一眼看出异常点，比盯着原始耗时表有效得多。堆排序和分治这两块内容，原理都不复杂，真正拉开差距的是你有没有把每一个"为什么"追问到底——为什么建堆是线性的、为什么快排在最坏情况下会崩、为什么归并必须开辅助数组。把这三个问题用自己的话讲清楚，这个实验就没白做。