排序算法看到第五遍，合上书还是写不出一个没有bug的快排？这不是你手生，是练习的方式不对。我当年也有过这个阶段，动画看了一堆，笔记抄了三页，一到白板写代码就卡在边界条件上。后来想明白一件事：排序算法这玩意，靠的是"解题肌肉记忆"，读书不如做题，做题不如写代码调试。这篇"习题篇"不打算复读概念，也不打算甩十个排序源码让你收藏吃灰，而是把排序算法拆成概念判断题、手写实现题、变形应用题和实测验证题四个层次，每个层次都有对应的思考题、完整解答和踩坑说明。适合学完基础排序但想真正内化的人，也适合准备面试前最后一轮专项复习的人，甚至适合想给新人出题的老手直接抄作业。
1. 为什么排序算法值得专门做一批习题
1.1 只看不练，代码能力会停留在"假懂"状态
很多人觉得排序算法是老掉牙的东西，会调库就行。但真遇到问题时会发现，面试官不会让你直接调用排序函数，实际问题里也很少出现"把数组排好序"这种干净需求，反而是"按某个key排序且保持相对顺序""数据量太大放不进内存""链表不能随机访问"这些变形情况。这时候你脑子里的排序算法必须是活的，不是一段背下来的代码。
我自己带过几个刚入行的新人，问冒泡排序的稳定性都能答上来，让手写一个快排就容易在递归终止条件上翻车。原因很简单：能说出概念只代表大脑理解了逻辑，而写代码需要同时保证循环边界、指针移动、递归出口三个层面不出错。这种能力只能靠批量练题培养，看书是看不出来的。
1.2 习题的四个层次：概念、实现、应用、实验
我给排序算法练习分了四个层次，这篇习题篇也会按这个框架走：
- 第一层是概念判断题，练的是对排序算法底层性质的敏感度，比如稳定性、原地性、最坏情况、比较次数。
- 第二层是手写实现题，练的是循环、递归、指针边界这些基本功，重音在"一次写对"。
- 第三层是变形应用题，练的是把经典算法迁移到新场景的能力，比如链表排序、TopK、近乎有序数组。
- 第四层是实测验证题，练的是用数据验证实现正确性，以及理解复杂度在真实机器上的表现。
这四个层次相互支撑。忽视第一层，写出来的代码可能跑得对但语义不对；忽视第二层，后面所有变形题都会卡在基础实现上；忽视第三层，就只会在面试里背模板；忽视第四层，你对复杂度的理解永远是纸面的。所以别只挑自己舒服的部分做。
2. 概念辨析练习：稳定性、原地性与比较次数
2.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) / 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 log n) / O(n log n) / O(n log n) | O(1) |
填表本身不难，真正容易丢分的是解释"为什么"。以选择排序为例，它的不稳定不是因为交换本身，而是因为每次选择最小值和当前位置交换时，可能把相同值的相对顺序打乱。比如数组[5a, 3, 5b]，第一次选择会找到3，把它和第一个位置的5a交换，结果变成[3, 5a, 5b]，到这里还没问题；但如果最小值位于一个相同值之后，交换就会让相同值的顺序改变。堆排序的不稳定性也是同一类问题，父节点和子节点的远距离交换很容易跨越相同值的相对位置。
快速排序的不稳定则来自分区过程。分区时会把小于枢轴的元素挪到前面，大于枢轴的挪到后面，相同值虽然理论上可以不交换，但标准Lomuto分区会在交换时把后面的相同值换到前面去。很多人记不清这个，我建议别死记"快排不稳定"，而是亲手用小数组模拟一次分区过程，模拟完就永远记住了。
2.2 改造题：把选择排序变成稳定版本
第二道概念题稍微难一点：选择排序默认不稳定，你能不能把它改成稳定版本？这题考的不是算法设计能力，而是对"稳定性"定义的理解。
思路很简单：既然不稳定是因为"远距离交换"打乱了相对顺序，那就不要用交换，改用插入。每一轮找到最小值之后，把最小值到当前位置之间的所有元素整体后移一位，再把最小值放到当前位置。这样相同值元素的相对位置就不会被跨越，因为最小值前面相等的那些值都只是右移，没有被跳过去。
def stable_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[min_idx] 移动到 arr[i]，中间元素整体右移 temp = arr[min_idx] for k in range(min_idx, i, -1): arr[k] = arr[k - 1] arr[i] = temp return arr这段代码的本质是"用插入代替交换"，代价是每轮移动元素的次数变多，时间复杂度从经典的比较次数O(n²)变成O(n²)比较加O(n²)移动，常数更大。但它证明了一个重要结论：稳定性不是一个算法天生的宿命，而是实现细节决定的。同样一段冒泡排序，如果判断条件是<就是稳定，改成<=就会变成不稳定，因为相等元素也会发生交换。
2.3 比较次数细节题：插入排序为什么对"接近有序"数据表现特别好
第三道概念题是考察对比较次数的感知：对一个几乎有序的数组，插入排序的比较次数大概是多少？很多人第一反应是"反正最好情况O(n)"，但最好情况是指完全有序。更实际的情况是数组中每个元素离最终位置都不远，这时候每个元素的内层循环只会比较几次就停下，所以总比较次数接近O(n)，而不是O(n²)。
这就是为什么很多生产环境里，当数据量小或者数据接近有序时，插入排序反而比快排还快。快排的递归开销和分区开销在数据量小的时候会掩盖它的理论复杂度优势。这个点经常作为脑筋急转弯出现在面试里：一个长度1000且基本有序的数组，让你选一个排序算法，很多人脱口而出快排，实际上插入排序常会更优。
3. 手写实现练习：四种排序的边界陷阱
3.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易错点有两处。第一，外层循环范围写成range(n)会导致一次多余的空扫描，虽然不报错，但不干净。第二，内层循环写成for j in range(n - 1)而不减去i，会让排好序的后半段反复参与比较，虽然也能跑，但提前退出的判断会变得不准确。我见过不少新手在提前退出优化上翻车，就是因为忽略了内层循环上界应该随着i收缩。
3.2 插入排序：把"交换"改成"平移"才是精髓
第二道手写题：插入排序，要求不能用交换实现，只能用平移。这个要求逼着你理解插入排序的真实动作：把当前元素暂存，把前面所有比它大的元素依次往后挪，最后在空出来的位置放入暂存元素。
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初写者最容易漏掉最后的arr[j + 1] = cur，因为前面while结束的时候j已经指向了一个不满足条件的位置，必须回到j+1去放元素。另外，while j >= 0这个条件不能省略，否则数组越界。用交换实现插入排序虽然也能得到结果，但交换会产生不必要的赋值操作，在数据量大时性能差距明显。这道题练的不只是代码，还是对"移动 vs 交换"两种内存操作差异的理解。
3.3 归并排序：合并区间和临时数组的索引对应关系
第三道手写题归并排序很少人第一遍能写对，问题通常集中在合并函数里临时数组索引和原数组索引的错位。这里给一个容易理解的写法：
def merge_sort(arr, left, right): if left >= right: return mid = (left + right) // 2 merge_sort(arr, left, mid) merge_sort(arr, mid + 1, right) merge(arr, left, mid, right) def merge(arr, left, mid, right): temp = [] i, j = left, mid + 1 while i <= mid and j <= right: if arr[i] <= arr[j]: temp.append(arr[i]) i += 1 else: temp.append(arr[j]) j += 1 while i <= mid: temp.append(arr[i]) i += 1 while j <= right: temp.append(arr[j]) j += 1 for idx, val in enumerate(temp): arr[left + idx] = val这个写法用Python列表当临时区，索引对应简单，但要注意条件if left >= right不能改成==，因为归并排序递归时可能出现left > right吗？实际上在正确实现里不会，但保留>=更安全。另一个坑是合并时的等号：如果希望归并排序保持稳定，合并两个有序区间时，左区间元素等于右区间元素时，必须先取左区间的元素，也就是用<=而不是<。如果用<，相同元素的相对顺序会被破坏，排序就变成不稳定了。
3.4 快速排序：随机枢轴、分区指针与递归出口
第四道手写题自然落到快速排序。我建议写Hoare版本的少一点，先掌握Lomuto分区，因为后者和"把小于枢轴的元素放左边"这个直观语义更贴合。
import random def quick_sort(arr, left, right): if left >= right: return pivot_idx = random.randint(left, right) arr[left], arr[pivot_idx] = arr[pivot_idx], arr[left] pivot = arr[left] i = left # i 指向小于等于枢轴区域的右边界 for j in range(left + 1, right + 1): if arr[j] <= pivot: i += 1 arr[i], arr[j] = arr[j], arr[i] arr[left], arr[i] = arr[i], arr[left] quick_sort(arr, left, i - 1) quick_sort(arr, i + 1, right)这段代码里最关键的变量是i，它维护的是"已经扫描过的、小于等于枢轴的元素区间的右边界"。每发现一个新元素小于等于枢轴，就把它换到i+1的位置，同时扩张边界。分区结束后，枢轴从left换到i，此时枢轴左边全是小于等于它的元素，右边全是大于它的元素。递归区间分别是[left, i-1]和[i+1, right]，注意两个区间都不包含枢轴本身，这样递归才能终止。
快排的经典坑有两个。第一个是不加随机化，对已经有序的数组退化成O(n²)，这里用random.randint选枢轴来规避。第二个是递归边界写成if left == right，在某些分区边界下会导致无限递归。比如当枢轴刚好是区间最小值时，i等于left，左区间是[left, left-1]，右区间是[left+1, right]；如果递归出口是==，左区间会被继续调用一次，但此时left > right，需要额外判断。直接用>=可以一次性避免。
4. 变形应用：TopK、链表排序与近乎有序数组
4.1 快速选择：在O(n)平均时间内找到第K大的元素
变形题第一道：找出无序数组里第K大的元素，要求平均时间复杂度O(n)。很多人的第一反应是先排序再取下标，但排序是O(n log n)，不符合要求。正确思路是基于快排的partition做快速选择。
def quick_select(nums, left, right, k): if left == right: return nums[left] pivot_idx = random.randint(left, right) nums[left], nums[pivot_idx] = nums[pivot_idx], nums[left] pivot = nums[left] i = left for j in range(left + 1, right + 1): if nums[j] <= pivot: i += 1 nums[i], nums[j] = nums[j], nums[i] nums[left], nums[i] = nums[i], nums[left] if i == k: return nums[i] elif i > k: return quick_select(nums, left, i - 1, k) else: return quick_select(nums, i + 1, right, k)这里k是第K大元素在升序排序后的下标。你只需要记住一个判断：分区后枢轴所在位置i如果正好是目标下标，直接返回；如果目标下标在左边，只递归左区间；在右边，只递归右区间。因为每轮只处理一侧，平均时间和快排的分区轮数一致，都是O(n)。最坏情况仍然是O(n²)，但随机化枢轴能让最坏情况概率低到可以忽略。这道题的价值在于让你理解分区操作比完整排序便宜得多，它能复用到很多"只关心某个位置"的问题里。
4.2 链表归并：摆脱数组思维的随机访问依赖
变形题第二道：对单链表做归并排序，要求空间复杂度O(1)（不计递归栈）。链表没有随机访问，所以你不能直接搬数组版的归并排序，需要先用快慢指针找到中点，再递归排序左右两半，最后合并两个有序链表。
class ListNode: def __init__(self, val=0, next=None): self.val = val self.next = next def sort_list(head): if not head or not head.next: return head slow, fast = head, head.next while fast and fast.next: slow = slow.next fast = fast.next.next mid = slow.next slow.next = None left = sort_list(head) right = sort_list(mid) return merge_two_lists(left, right) def merge_two_lists(l1, l2): dummy = ListNode() tail = dummy while l1 and l2: if l1.val <= l2.val: tail.next = l1 l1 = l1.next else: tail.next = l2 l2 = l2.next tail = tail.next tail.next = l1 if l1 else l2 return dummy.next这道题最常见的错误是用数组思路：先遍历链表存到列表里，排完序再重建链表。虽然结果正确，但不满足"排序链表"这道题的考察本意。链表版归并的核心是切断：找到中点后要把slow.next置为None，否则递归左半部分时会向后蔓延到右半部分，造成无法终止。快慢指针的初始位置也有讲究，slow从head开始，fast从head.next开始，这样在偶数长度链表上，中点会偏左，避免递归死循环。这道题的价值是逼迫你抛弃"下标"思维，转而用指针和引用关系来描述算法。
4.3 近乎有序数组：插入排序的用武之地
变形题第三道：一个长度为10万的数组，每个元素离最终排序位置不超过10，用什么排序最快？这题考的不是某个算法的背诵，而是对插入排序特性的迁移理解。
前面概念题已经提过，插入排序的比较次数和"每个元素需要往回移动的距离"直接相关。如果每个元素离最终位置不超过10，那么内层while循环最多比较10多次就会停下，总比较次数约等于O(10n)，也就是线性级别。这是其他O(n log n)算法做不到的，因为快排和归并的log n因子比10要大。实测里，对这种数据运行插入排序，会比快排快。
更实用的场景是混排优化：很多生产排序实现会对小规模子数组改用插入排序。当递归分区把数组切到长度小于某个阈值（比如16或32）时，直接插入排序，能省掉大量递归调用和分区开销。这是快排在工程实现里常见的优化点，原理和近乎有序数组节省比较次数同源。
5. 用随机测试与性能对比验证排序实现
5.1 对数器：用随机小数组快速揪出排序bug
写完排序代码之后，很多人直接拿大数组跑一遍，发现结果没报错就认为正确了。这种方式非常不可靠，因为排序的错误往往只出现在特定排列、特定重复值、特定长度下。正确做法是写一个对数器：随机生成大量小数组，分别用你的实现和语言内置的稳定排序结果对比，一旦不一致就打印出错用例。
import random import copy def check_sort(sort_func, trials=10000, max_len=20): for _ in range(trials): n = random.randint(0, max_len) arr = [random.randint(-10, 10) for _ in range(n)] expected = sorted(arr) got = sort_func(copy.deepcopy(arr)) if got != expected: print("出错了！", arr) print("内置结果：", expected) print("你的结果：", got) return False print("所有测试通过") return True这个工具最妙的地方是max_len设得小，再加上重复值范围压缩，能让相等的元素大量出现，从而快速暴露不稳定问题。比如你的归并排序合并时用了<而不是<=，对数器会在[2,2,1]这样的用例上立刻报错。很多人总觉得测试要大数据量大样本，实际上小数组加多种随机分布才是定位逻辑错误的最快路径。
5.2 性能实测：分别测试随机、有序、重复数据
验证正确性之后，下一步是理解复杂度不是纸面数字。我建议用四类数据做性能对比：随机数组、完全有序数组、全部相同数组、大量重复值数组。分别测冒泡、插入、归并、快排的运行时间，记录中等规模比如5万条数据的耗时。
实测结果通常很有意思。完全有序数组上，插入排序可能跑得比快排还快，因为比较次数是n而快排还要吃分区开销。全部相同数组上，冒泡的提前退出会在第一轮就停止，耗时接近O(n)，而快排如果不做随机化会退化成O(n²)级别的交换。大量重复值数组上，归并排序因为有稳定性和<=比较，表现比较稳定；快排的分区在这种场景下会把大量等于枢轴的元素反复移动，效率下降，这时可以引入三路分区优化。做一次这样的实验，你对"平均复杂度""最坏复杂度"的理解会从记忆变成直觉。
5.3 压力测试里的时间陷阱：递归深度与内存分配
最后必须提醒一个容易被忽略的坑：递归深度和内存分配。快排递归深度在理想情况下是O(log n)，但如果写错了分区逻辑，在特定输入下可能递归上万层，直接栈溢出。归并排序每轮都新建临时数组，在Python里会频繁触发内存分配，数据量一大就会明显变慢。
我建议测试时加入一个数据监控：记录递归最大深度、临时数组总大小、实际运行时间三组数据。递归最大深度可以用一个全局计数器实现，每进入递归函数加一、退出减一，峰值就是最大深度。临时数组大小可以通过在merge里累加len(temp)统计。这样一旦某个用例运行缓慢，你能立刻判断瓶颈是"比较次数太多""递归太深"还是"内存分配太频繁"，而不是盲目换算法。
6. 从这批习题里提炼的排序调试经验
6.1 开闭区间不一致是90%越界bug的根源
做完上面所有题，我发现最值得写进笔记的经验只有一条：区间表示一旦混用，代码必出问题。冒泡排序的range(n - 1 - i)、插入排序的while j >= 0、归并排序的i <= mid、快排的递归区间[left, i-1]和[i+1, right]，每一处都隐含一套开闭区间约定。如果你在脑子里没有明确"当前用的是左闭右闭还是左闭右开"，写到一半很容易把<=写成<，把mid+1写成mid，把i-1写成i。
我的做法是写代码前先用注释标出区间约定，比如# 排序区间 [left, right]，左右都包含。这样递归到下一层时，left = i + 1和right = i - 1这两个写法才不会搞混。这个习惯不仅对排序有用，对二分查找、树遍历、滑动窗口同样适用。
6.2 用"小样本打印"定位递归分治中的区间错误
排查递归排序的bug时，不要直接断点调试深层的递归调用，先做小样本打印。比如让数组长度固定为5，在每次分区或合并后打印当前区间、当前数组状态。你会很直观地看到左半部分和右半部分是否被正确处理，枢轴最终落到了哪里。这个方法在快排上尤其好用，因为一次错误的分区会立刻让后续递归区间出现负长度或者越界下标。
我当时调试一个新写的三路快排时，就是靠着打印每个分区的边界值找到问题：中间区间的下界写错了，导致大量等于枢轴的元素被扔到右侧。这个bug如果不用打印，盯着代码看半小时都看不出来。
6.3 对象排序的比较器陷阱：稳定排序只是必要条件
最后一类常见错误不在算法本身，而在使用场景。当你用自定义对象做排序时，比较器的写法会直接影响结果语义。比如你有若干个对象，每个对象有两个字段，第一关键字是分组id，第二关键字是权重。要实现"按id分组同时组内保持原始顺序"，你必须用稳定排序，并且比较器只比较id。如果比较器里顺手把权重也放进去了，稳定性就被破坏了，即使调用的是稳定排序，组内顺序也会变成按权重排。
有人会问，那直接按id和权重排序不就行吗？不行，因为这会改变组的相对顺序。稳定排序的语义是"相同id保持原顺序"，而比较器里加入权重会让相同id的元素不再相等，稳定的前提就不存在了。这个点在写业务代码时经常踩，我建议大家在测试排序逻辑时，除了验证有序性，还要专门验证相同键元素的相对顺序。很多题库只检查结果是否有序，不检查稳定性，导致代码里的稳定性缺陷被掩盖，一上生产就出事。
排序算法这份习题做到这里，你能拿走的不是几段代码，而是每次动手前先在草稿上模拟一遍分区的习惯，是写完后用对数器验证而不是用肉眼扫一遍的纪律，是看到"节点坐标离最终位置不超过10"这类条件时立刻想到插入排序的条件反射。这些东西比记住哪个排序是稳定的更有用，因为它们在算法之外，才是真正让代码可靠的能力。
