直接进入正题。这一章“排序”可以说是整个数据结构课程里最实用、也最容易被轻视的一章。说它实用是因为不管你以后写业务代码还是做底层框架排序都逃不掉说它被轻视是因为很多人背了快排的代码就以为掌握了排序结果一到面试问复杂度推导、稳定性选择、工程优化直接露馅。这篇内容我就按照“先搭框架、再拆细节、然后给实战经验、最后补坑”的思路把第八章的排序讲透。讲讲这一章到底解决什么问题。排序算法的本质就是把一组无序数据按照某种规则变成有序序列。你可能会说“这不就是排个序吗直接调用现成的sort函数不就行了”但真实场景远比这复杂数据量是几千还是几千万内存能不能放下数据基本有序还是完全乱序排序要求稳定还是无所谓这些条件直接决定了你该选哪种算法。学完这一章你不仅要能默写五六种排序代码更要能在面对具体问题时说出“这里用归并因为要稳定”或者“这里用快排因为平均最快”这种有判断力的答案。这一章适合三类人读正在学数据结构的学生刷了题但排序原理稀碎的求职者以及想在工程里优化排序性能的开发者。我尽量把代码、推导、坑点都放出来看完不用再去翻一堆资料。1. 排序算法全景先给这一章画张地图学排序最忌讳一上来就背代码。先搞清楚排序算法到底有哪些维度整个框架立住了后面所有算法都不过是往框架里填细节。第一个维度比较排序与非比较排序。比较排序靠元素之间的比较来决定顺序像冒泡、插入、快排、归并、堆排都是这一类非比较排序不靠比较而是利用数据本身的特性直接“放位置”比如计数排序、桶排序、基数排序。这两类的复杂度边界完全不同比较排序平均最快也就是O(n log n)而非比较排序在某些条件下能到O(nk)甚至O(n)。代价是非比较排序对数据范围和数据形态有苛刻要求。第二个维度稳定与不稳定。稳定指的是值相等的两个元素排序前后相对顺序不变。这一点在业务里特别重要比如你先按时间排了订单再按金额做稳定排序那金额相同的订单依然能保持时间顺序。稳定排序有冒泡、插入、归并不稳定排序有选择、快排、堆排。很多面试题就爱在稳定性上做文章。第三个维度原地与非原地。原地排序只使用O(1)的额外空间比如快排、堆排归并排序通常需要O(n)的额外空间。空间占用直接决定了你能不能在海量数据场景下用它。把这三个维度叠起来再配合时间复杂度整个排序全景就清楚了。我也建议你自己画一张表把每个算法的“最好/平均/最坏时间复杂度、空间复杂度、稳定性、是否原地、适用场景”填进去这张表就是你接下来几天的复习总纲。排序算法平均时间最坏时间额外空间稳定性原地冒泡O(n²)O(n²)O(1)稳定是插入O(n²)O(n²)O(1)稳定是选择O(n²)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(nk)O(nk)O(k)稳定否基数O(d(nk))O(d(nk))O(nk)稳定否2. 五大经典排序原理拆解与实现细节这一节我按教学顺序逐个过一遍每个都给核心实现、复杂度原因以及我实际使用中遇到的关键点。2.1 冒泡排序最直白但不建议真用冒泡排序的思路一句话就能说清从头开始相邻两个元素比较如果顺序不对就交换一趟下来最大的元素就像气泡一样“浮”到最后面。重复n-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)但平均和最坏还是O(n²)。只要你学过任何一种更快的排序就不会在生产代码里写冒泡它最大的价值是教学——帮你理解“交换排序”这一基本范式。2.2 插入排序小规模数据的隐形王者插入排序的思路像打扑克时理牌你从桌上摸一张牌把它插到手里已经排好序的牌堆里正确的位置。实现上从第二个元素开始逐个往前比较找到合适的位置插入。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²)但在数据量小比如十几二十个元素或者数据“基本有序”的场景下它的实际速度经常吊打快排。原因在于它的常数极小操作是连续的内存移动缓存命中率高。也正因为这个特性你会看到很多成熟语言的标准库排序里在递归切分到小规模子数组后直接改用插入排序来收尾——这是真实工程里的常见优化后面第五章我会再展开。2.3 选择排序最稳定字面意义上也最死板选择排序的思路最简单直白每次从剩余元素里选出最小的那个放到当前该放的位置。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 arr[i], arr[min_idx] arr[min_idx], arr[i] return arr这段代码有个很值得注意的点arr[i]和arr[min_idx]交换可能把后面的某个相同元素换到前面所以选择排序是不稳定的。你可以试着构造一个例子[5a, 3, 5b, 1]第一趟选出1和5a交换变成[1, 3, 5b, 5a]两个5的相对顺序就反了。选择排序的固定特点就是无论如何都要做完整的n²/2次比较没有“最好情况”一说所以实际用途很小。学它的意义在于它是“选择类排序”思想的起点堆排序就是从这个思路进化来的。2.4 归并排序稳定性的标准答案归并排序的核心是分治把数组从中间一分为二分别排序再合并两个有序数组。分解是递归的直到子数组只剩一个元素——单个元素天然有序——然后往上合并。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): result [] i j 0 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 log n)没有最坏情况这一点比快排稳。第二合并时遇到相等的元素先取左边的所以它是稳定排序。代价就是需要一个和原数组等长的辅助数组空间复杂度是O(n)。在做“求逆序对”“链表排序”“外部排序”这类题目时归并基本是首选方案。2.5 快速排序实际应用中最常见的排序快排也是分治思路但和归并的侧重点不同归并是先递归后合并快排是先分区后递归。快排的核心操作是partition——选一个基准值pivot把比pivot小的元素放到左边大的放右边然后递归处理左右两边。def quick_sort(arr, low, high): if low high: pi partition(arr, low, high) quick_sort(arr, low, pi - 1) quick_sort(arr, pi 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分区方案代码短适合教学和面试默写。快排的平均复杂度是O(n log n)而且分区是原地的额外空间主要是递归栈平均O(log n)。但它有个致命弱点如果每次选的pivot恰好是最大或最小值分区极不平衡递归深度退化成O(n)时间复杂度直接跌到O(n²)。所以工程实现里绝不会这样简单选pivot而是用“三数取中”或者干脆随机选后面第五部分我专门讲。3. 进阶排序与复杂度边界什么时候该放弃比较排序理解了五大经典你可能会想既然快排已经这么快了为什么还要学堆排和非比较排序因为工程里有很多场景快排并不是正确选项。3.1 堆排序用堆选极值原地完成堆排序是利用堆这种数据结构进行选数的一种排序。它分两步先把数组构建成一个大顶堆然后反复把堆顶最大值和堆末元素交换缩小堆的范围再调整堆。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(n log n)不像快排可能退化到O(n²)而且是原地排序额外空间O(1)。但它有一个容易被忽略的问题——不稳定而且常数比快排大实际速度一般不如快排。它最适合的场景是“不能额外开大数组同时要保证最坏性能有下限”的时候。面试里出现“用堆排序找TopK”这类题考的不是排序本身而是你能不能把“堆”这个数据结构用在“只关心最大/最小值”的场景里。3.2 计数排序、桶排序、基数排序非比较排序的真面目这一组算法不靠比较靠的是数据本身的范围和分布。计数排序的原理很简单如果我知道数据范围是0到k先数每个数字出现了几次再按顺序累加、回填。它的时间复杂度是O(nk)关键限制是k不能太大否则辅助数组根本开不下。桶排序是把数据按范围分到几个桶里桶内再分别排序。它假设数据在区间内近似均匀分布比如一组成绩分布在0到100分分10个桶每个桶里再快排。数据越均匀效果越好一旦数据全部堆到一个桶里就退化成普通排序。基数排序的思路更有意思把数字按位拆开从最低位开始逐位做稳定排序。比如对三位数先按个位稳定排再按十位排最后按百位排排完就整体有序了。它的复杂度是O(d(nk))d是数字位数k是每一位的范围。基数排序要求数据能够被拆分成“位”所以对字符串、固定位数的数字特别合适。这三者的共同点是快但都有苛刻的前提条件。做工程时我会先问自己数据范围可不可控分布大致什么样位数固定吗如果答案是否定的就别碰它们老老实实用快排。3.3 复杂度下界为什么比较排序最快只有O(n log n)很多人觉得“快排就是最快的排序”是个默认事实但不知道它背后的理论依据。这里有个非常漂亮的推导值得你花十分钟理解。任何一个比较排序算法都可以抽象成一颗决策树每次比较是一个节点比较结果决定走左子树还是右子树叶子节点对应一种输入的全排列可能。对于n个不同元素一共有n!种排列方式所以决策树至少有n!个叶子。二叉树第h层最多有2^h个叶子因此树高h必须满足2^h ≥ n!即h ≥ log2(n!)。再用斯特林公式n!大约等于(n/e)^n所以log2(n!) ≈ n log2 n。这意味着任何基于比较的排序算法在最坏情况下至少要执行Ω(n log n)次比较。这个结论不是经验是数学上证明的边界。所以当你看到“某种比较排序突破了O(n log n)”之类的说法可以直接判定是伪科学。需要更快只有一条路——放弃比较排序利用数据本身的额外信息。4. 排序面试算法题到底在考什么这一章单纯考默写的时代已经过去了。现在的面试题都是把排序算法跟具体业务场景、数据结构结合起来看你能不能灵活迁移。我整理几个最高频的题目模型。TopK问题。在一堆数据里找最大或最小的K个。你当然可以把全量数据排个序然后取前K个但那是O(n log n)。用小顶堆找最大的K个维护一个大小为K的堆遍历一遍数据遇到比堆顶大的就替换复杂度只有O(n log K)。如果K远小于n这个优势非常明显。这道题背后考的是堆排序的“部分排序”能力而不是全排序能力识破这一点面试题就解了一半。数组中的逆序对。逆序对指i j且arr[i] arr[j]的数对。暴力法是双重循环O(n²)但用归并排序可以降到O(n log n)。思路是在合并两个有序子数组时如果左边某个元素大于右边某个元素那么左边剩余的所有元素都和这个右边元素构成逆序对一次就能数出一大片。这题是归并排序骨架下的经典应用。排序后相邻元素的最大差值。给你一个无序数组要求排序后相邻两个数的最大差值而且时间复杂度要求O(n)。这就逼迫你不能用普通排序得用桶思想。做法是找出最大值和最小值把区间等分成n-1个桶每个桶记录桶内最小值和最大值然后只检查相邻桶之间最大和最小的差值即可。这里排序只是背景真正考的是你能不能越过“排序必须全排”的思维定式。合并两个有序数组或链表。这题直接把归并排序的merge核心抽出来考。常规做法是从后往前填充数组避免额外空间。链表版本是递归或者迭代地比较两个头节点。这题考的不是背代码而是归并思想能不能剥离排序外套独立使用。区间合并。给一堆区间把重叠的合并。解法是先按区间起点排序然后顺序扫描维护当前合并区间的右端点。这题明面上是贪心但第一步排序动作是整个解题的前提排序的稳定性、复杂度在这个问题上直接决定后续算法的成本。把这些题刷完你会发现一个规律考排序不是在考排序本身而是在考“你手里有哪些工具、知道每个工具的边界并能把工具组合到具体问题上”。所以我的建议是刷题时不要为了过而过每个题做完都问一句“这题为什么用这个排序而不是那个排序”想明白这个问题比多刷十题有用。5. 工程排序调优真实项目中的排序选择从考试回到真实世界。你在代码里写sort()底层到底是怎么排的很多编程语言的标准库排序实现绝不是单一算法而是一种混合策略。以某个经典的标准库实现为例元素数量小于特定阈值比如几十个时直接用插入排序数量较大时使用快速排序但pivot的选择不是取最后一个元素而是取首、中、尾三个数的中位数甚至随机选防止最坏情况递归过程中如果检测到递归深度超过某个限制就切换到堆排序“兜底”确保整体复杂度不会退化到O(n²)。这个策略有个专门的名字叫“内省排序”本质上是快排为主体、插入排序优化小数组、堆排序兜底退化的组合拳。这个混合策略背后有三个工程思考。第一小数组用插入排序是因为它常数极小递归调用快排反而浪费函数调用开销第二快排虽然平均快但不能接受最坏情况用堆排做保底第三稳定性的问题标准库里也有专门做稳定排序的分支通常基于归并排序来实现代价是额外空间。再说说对象排序。如果排序的不是整数而是对象那就会涉及一个关键问题你用什么字段来比较大小。比如有一个人名单你既要按姓名排序又希望同名的人按年龄排序那就必须调用两次排序而且第二次必须是稳定的否则同名人的年龄顺序就丢了。这就是为什么理解稳定性不只是考试概念它在真实业务里直接决定结果是否正确。再看海量数据场景。当数据量大到内存放不下时快排、归并这些内存排序算法全部失效这时候用的是“外部排序”。经典的外部排序做法是先把大文件切分成多个能装入内存的小块每块分别排序后写入临时文件然后做多路归并把多个有序文件合并成一个大的有序文件。你看这个过程的每个“小块排序”还是内存排序但整体框架已经变成归并排序思路了。所以归并排序的实际价值绝对大于它在教科书里那两页纸的地位。工程上做排序选型我一般按这个逻辑走先确认数据规模能不能放进内存再确认数据形态数值范围是否可控、分布是否均匀然后确认业务是否需要稳定排序最后看最坏情况能不能接受。这四个问题问完排序方案基本就定下来了根本不需要凭感觉拍脑袋。6. 常见问题与排查实录这一节我把学习排序和工程用排序时最容易踩的坑整理一遍每个都是我看别人写代码、自己排查时反复遇到的典型问题。问题一快排写成最坏情况还不自知。最常见的写法就是每次固定取最后一个元素当pivot然后输入恰好是一个基本有序的数组。此时每一次分区都极度不平衡递归深度接近n函数调用栈直接爆炸时间复杂度退化成O(n²)。排查方法很简单在递归函数里打印当前区间的low和high观察递归深度或者输入一组升序排列的数据做测试如果排序1万个数就要好几秒基本可以断定退化了。解决方法也直接pivot用三数取中或者随机选取不要让数据分布来支配你的算法命运。问题二排序不稳定导致业务结果异常。我举一个真实场景。某业务系统需要对一个订单列表做二次排序先按订单状态分桶再在桶内按创建时间排序。如果第二次用的是不稳定排序那么相同创建时间的订单可能被打乱原有顺序如果早期已经按优先级排过序这个顺序就会丢失。排查时最容易被忽略因为单独看排序结果“是有序的”你得对比排序前后相同键元素的相对顺序才能发现问题。解法是严格区分“值相等但语义不同”的数据用(key, 原始索引)这种复合键来做排序或者干脆用稳定排序。问题三递归深度造成的栈溢出。归并排序和快速排序都是递归实现数据量大的时候递归深度可能达到几千甚至上万层。在很多运行时环境里默认栈大小是固定的递归太深直接StackOverflow。这个问题在面试里很隐蔽因为面试官给你的测试数据可能很小你根本不会触发。排查方式是估算递归深度快排优化后平均O(log n)最坏O(n)归并稳定O(log n)。如果深度不可控解决方案有几个快排及时转堆排序兜底、把递归改成循环显式用栈模拟、或者调整运行时栈大小。我遇到过的最粗暴解法是——直接换迭代式排序一了百了。问题四归并排序的额外空间被忽略导致OOM。归并排序需要一个与原数组等长的辅助数组。如果你对一个大数组做归并排序空间占用是原数组的两倍内存敏感场景下这可能直接导致内存溢出。很多人只记得归并是O(n log n)的时间复杂度完全忘了空间复杂度这回事。排查时看内存曲线就能定位。解决方法是换原地排序堆排序对空间极度友好或者把数据量拆小、分批归并也就是外部排序的思路。问题五Comparator逻辑写反或忽略相等情况。这个话题看起来基础但特别容易出事。比如你要按分数降序排列结果写成了升序数据看似有序但方向全反或者Comparator里只处理了 0和 0漏掉了 0的情况导致某些语言的标准排序认为比较函数传递性不成立排序结果变成“薛定谔的有序”。排查经验是先拿一个只有两三个元素的最小数据集测试人脑模拟一遍排序过程再用大量随机数据跑一遍如果结果异常八成是Comparator的边界条件处理不全。问题六非比较排序的边界条件踩坑。计数排序如果不知道数据最小值直接按最大值开数组可能浪费海量空间基数排序如果位数不一致短的数需要补零处理否则位数不同的数字会排错。这类问题最让人头疼的地方是它对大多数数据表现正常但只要出现一个特殊值整个结果就是错的。所以用非比较排序前务必对数据做一次边界审查宁可先扫描一遍拿到最小值和最大值再决定开多大的桶。结尾的一些实践体会排序这东西学到后面你会发现它的魅力不在于“会写十种排序”而在于“面对一个问题你能判断哪种排序根本不值得尝试”。我个人最大的进步发生在一个项目里当时要处理几千万个订单记录按时间排序再分页展示直接全字段排序慢到不可接受后来换成“先按时间分桶、桶内走插入排序、再归并合并”的组合方案整个过程快了一个数量级。这个经历让我彻底理解了第八章的价值——排序是数据结构与算法思维的浓缩同一个数组不同的排序方式背后是完全不同的性能天梯。最后分享一个实用建议学完每类排序自己动手维护一份“排序算法速查表”把复杂度、稳定性、最优场景、最坏场景写清楚面试前拿出来过一遍比临时翻书有用得多。排序考点万变不离其宗复杂度边界和稳定性这两把刷子握稳了不管题目怎么变你都能找到切入点。
直接进入正题。这一章“排序”可以说是整个数据结构课程里最实用、也最容易被轻视的一章。说它实用是因为不管你以后写业务代码还是做底层框架排序都逃不掉说它被轻视是因为很多人背了快排的代码就以为掌握了排序结果一到面试问复杂度推导、稳定性选择、工程优化直接露馅。这篇内容我就按照“先搭框架、再拆细节、然后给实战经验、最后补坑”的思路把第八章的排序讲透。讲讲这一章到底解决什么问题。排序算法的本质就是把一组无序数据按照某种规则变成有序序列。你可能会说“这不就是排个序吗直接调用现成的sort函数不就行了”但真实场景远比这复杂数据量是几千还是几千万内存能不能放下数据基本有序还是完全乱序排序要求稳定还是无所谓这些条件直接决定了你该选哪种算法。学完这一章你不仅要能默写五六种排序代码更要能在面对具体问题时说出“这里用归并因为要稳定”或者“这里用快排因为平均最快”这种有判断力的答案。这一章适合三类人读正在学数据结构的学生刷了题但排序原理稀碎的求职者以及想在工程里优化排序性能的开发者。我尽量把代码、推导、坑点都放出来看完不用再去翻一堆资料。1. 排序算法全景先给这一章画张地图学排序最忌讳一上来就背代码。先搞清楚排序算法到底有哪些维度整个框架立住了后面所有算法都不过是往框架里填细节。第一个维度比较排序与非比较排序。比较排序靠元素之间的比较来决定顺序像冒泡、插入、快排、归并、堆排都是这一类非比较排序不靠比较而是利用数据本身的特性直接“放位置”比如计数排序、桶排序、基数排序。这两类的复杂度边界完全不同比较排序平均最快也就是O(n log n)而非比较排序在某些条件下能到O(nk)甚至O(n)。代价是非比较排序对数据范围和数据形态有苛刻要求。第二个维度稳定与不稳定。稳定指的是值相等的两个元素排序前后相对顺序不变。这一点在业务里特别重要比如你先按时间排了订单再按金额做稳定排序那金额相同的订单依然能保持时间顺序。稳定排序有冒泡、插入、归并不稳定排序有选择、快排、堆排。很多面试题就爱在稳定性上做文章。第三个维度原地与非原地。原地排序只使用O(1)的额外空间比如快排、堆排归并排序通常需要O(n)的额外空间。空间占用直接决定了你能不能在海量数据场景下用它。把这三个维度叠起来再配合时间复杂度整个排序全景就清楚了。我也建议你自己画一张表把每个算法的“最好/平均/最坏时间复杂度、空间复杂度、稳定性、是否原地、适用场景”填进去这张表就是你接下来几天的复习总纲。排序算法平均时间最坏时间额外空间稳定性原地冒泡O(n²)O(n²)O(1)稳定是插入O(n²)O(n²)O(1)稳定是选择O(n²)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(nk)O(nk)O(k)稳定否基数O(d(nk))O(d(nk))O(nk)稳定否2. 五大经典排序原理拆解与实现细节这一节我按教学顺序逐个过一遍每个都给核心实现、复杂度原因以及我实际使用中遇到的关键点。2.1 冒泡排序最直白但不建议真用冒泡排序的思路一句话就能说清从头开始相邻两个元素比较如果顺序不对就交换一趟下来最大的元素就像气泡一样“浮”到最后面。重复n-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)但平均和最坏还是O(n²)。只要你学过任何一种更快的排序就不会在生产代码里写冒泡它最大的价值是教学——帮你理解“交换排序”这一基本范式。2.2 插入排序小规模数据的隐形王者插入排序的思路像打扑克时理牌你从桌上摸一张牌把它插到手里已经排好序的牌堆里正确的位置。实现上从第二个元素开始逐个往前比较找到合适的位置插入。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²)但在数据量小比如十几二十个元素或者数据“基本有序”的场景下它的实际速度经常吊打快排。原因在于它的常数极小操作是连续的内存移动缓存命中率高。也正因为这个特性你会看到很多成熟语言的标准库排序里在递归切分到小规模子数组后直接改用插入排序来收尾——这是真实工程里的常见优化后面第五章我会再展开。2.3 选择排序最稳定字面意义上也最死板选择排序的思路最简单直白每次从剩余元素里选出最小的那个放到当前该放的位置。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 arr[i], arr[min_idx] arr[min_idx], arr[i] return arr这段代码有个很值得注意的点arr[i]和arr[min_idx]交换可能把后面的某个相同元素换到前面所以选择排序是不稳定的。你可以试着构造一个例子[5a, 3, 5b, 1]第一趟选出1和5a交换变成[1, 3, 5b, 5a]两个5的相对顺序就反了。选择排序的固定特点就是无论如何都要做完整的n²/2次比较没有“最好情况”一说所以实际用途很小。学它的意义在于它是“选择类排序”思想的起点堆排序就是从这个思路进化来的。2.4 归并排序稳定性的标准答案归并排序的核心是分治把数组从中间一分为二分别排序再合并两个有序数组。分解是递归的直到子数组只剩一个元素——单个元素天然有序——然后往上合并。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): result [] i j 0 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 log n)没有最坏情况这一点比快排稳。第二合并时遇到相等的元素先取左边的所以它是稳定排序。代价就是需要一个和原数组等长的辅助数组空间复杂度是O(n)。在做“求逆序对”“链表排序”“外部排序”这类题目时归并基本是首选方案。2.5 快速排序实际应用中最常见的排序快排也是分治思路但和归并的侧重点不同归并是先递归后合并快排是先分区后递归。快排的核心操作是partition——选一个基准值pivot把比pivot小的元素放到左边大的放右边然后递归处理左右两边。def quick_sort(arr, low, high): if low high: pi partition(arr, low, high) quick_sort(arr, low, pi - 1) quick_sort(arr, pi 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分区方案代码短适合教学和面试默写。快排的平均复杂度是O(n log n)而且分区是原地的额外空间主要是递归栈平均O(log n)。但它有个致命弱点如果每次选的pivot恰好是最大或最小值分区极不平衡递归深度退化成O(n)时间复杂度直接跌到O(n²)。所以工程实现里绝不会这样简单选pivot而是用“三数取中”或者干脆随机选后面第五部分我专门讲。3. 进阶排序与复杂度边界什么时候该放弃比较排序理解了五大经典你可能会想既然快排已经这么快了为什么还要学堆排和非比较排序因为工程里有很多场景快排并不是正确选项。3.1 堆排序用堆选极值原地完成堆排序是利用堆这种数据结构进行选数的一种排序。它分两步先把数组构建成一个大顶堆然后反复把堆顶最大值和堆末元素交换缩小堆的范围再调整堆。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(n log n)不像快排可能退化到O(n²)而且是原地排序额外空间O(1)。但它有一个容易被忽略的问题——不稳定而且常数比快排大实际速度一般不如快排。它最适合的场景是“不能额外开大数组同时要保证最坏性能有下限”的时候。面试里出现“用堆排序找TopK”这类题考的不是排序本身而是你能不能把“堆”这个数据结构用在“只关心最大/最小值”的场景里。3.2 计数排序、桶排序、基数排序非比较排序的真面目这一组算法不靠比较靠的是数据本身的范围和分布。计数排序的原理很简单如果我知道数据范围是0到k先数每个数字出现了几次再按顺序累加、回填。它的时间复杂度是O(nk)关键限制是k不能太大否则辅助数组根本开不下。桶排序是把数据按范围分到几个桶里桶内再分别排序。它假设数据在区间内近似均匀分布比如一组成绩分布在0到100分分10个桶每个桶里再快排。数据越均匀效果越好一旦数据全部堆到一个桶里就退化成普通排序。基数排序的思路更有意思把数字按位拆开从最低位开始逐位做稳定排序。比如对三位数先按个位稳定排再按十位排最后按百位排排完就整体有序了。它的复杂度是O(d(nk))d是数字位数k是每一位的范围。基数排序要求数据能够被拆分成“位”所以对字符串、固定位数的数字特别合适。这三者的共同点是快但都有苛刻的前提条件。做工程时我会先问自己数据范围可不可控分布大致什么样位数固定吗如果答案是否定的就别碰它们老老实实用快排。3.3 复杂度下界为什么比较排序最快只有O(n log n)很多人觉得“快排就是最快的排序”是个默认事实但不知道它背后的理论依据。这里有个非常漂亮的推导值得你花十分钟理解。任何一个比较排序算法都可以抽象成一颗决策树每次比较是一个节点比较结果决定走左子树还是右子树叶子节点对应一种输入的全排列可能。对于n个不同元素一共有n!种排列方式所以决策树至少有n!个叶子。二叉树第h层最多有2^h个叶子因此树高h必须满足2^h ≥ n!即h ≥ log2(n!)。再用斯特林公式n!大约等于(n/e)^n所以log2(n!) ≈ n log2 n。这意味着任何基于比较的排序算法在最坏情况下至少要执行Ω(n log n)次比较。这个结论不是经验是数学上证明的边界。所以当你看到“某种比较排序突破了O(n log n)”之类的说法可以直接判定是伪科学。需要更快只有一条路——放弃比较排序利用数据本身的额外信息。4. 排序面试算法题到底在考什么这一章单纯考默写的时代已经过去了。现在的面试题都是把排序算法跟具体业务场景、数据结构结合起来看你能不能灵活迁移。我整理几个最高频的题目模型。TopK问题。在一堆数据里找最大或最小的K个。你当然可以把全量数据排个序然后取前K个但那是O(n log n)。用小顶堆找最大的K个维护一个大小为K的堆遍历一遍数据遇到比堆顶大的就替换复杂度只有O(n log K)。如果K远小于n这个优势非常明显。这道题背后考的是堆排序的“部分排序”能力而不是全排序能力识破这一点面试题就解了一半。数组中的逆序对。逆序对指i j且arr[i] arr[j]的数对。暴力法是双重循环O(n²)但用归并排序可以降到O(n log n)。思路是在合并两个有序子数组时如果左边某个元素大于右边某个元素那么左边剩余的所有元素都和这个右边元素构成逆序对一次就能数出一大片。这题是归并排序骨架下的经典应用。排序后相邻元素的最大差值。给你一个无序数组要求排序后相邻两个数的最大差值而且时间复杂度要求O(n)。这就逼迫你不能用普通排序得用桶思想。做法是找出最大值和最小值把区间等分成n-1个桶每个桶记录桶内最小值和最大值然后只检查相邻桶之间最大和最小的差值即可。这里排序只是背景真正考的是你能不能越过“排序必须全排”的思维定式。合并两个有序数组或链表。这题直接把归并排序的merge核心抽出来考。常规做法是从后往前填充数组避免额外空间。链表版本是递归或者迭代地比较两个头节点。这题考的不是背代码而是归并思想能不能剥离排序外套独立使用。区间合并。给一堆区间把重叠的合并。解法是先按区间起点排序然后顺序扫描维护当前合并区间的右端点。这题明面上是贪心但第一步排序动作是整个解题的前提排序的稳定性、复杂度在这个问题上直接决定后续算法的成本。把这些题刷完你会发现一个规律考排序不是在考排序本身而是在考“你手里有哪些工具、知道每个工具的边界并能把工具组合到具体问题上”。所以我的建议是刷题时不要为了过而过每个题做完都问一句“这题为什么用这个排序而不是那个排序”想明白这个问题比多刷十题有用。5. 工程排序调优真实项目中的排序选择从考试回到真实世界。你在代码里写sort()底层到底是怎么排的很多编程语言的标准库排序实现绝不是单一算法而是一种混合策略。以某个经典的标准库实现为例元素数量小于特定阈值比如几十个时直接用插入排序数量较大时使用快速排序但pivot的选择不是取最后一个元素而是取首、中、尾三个数的中位数甚至随机选防止最坏情况递归过程中如果检测到递归深度超过某个限制就切换到堆排序“兜底”确保整体复杂度不会退化到O(n²)。这个策略有个专门的名字叫“内省排序”本质上是快排为主体、插入排序优化小数组、堆排序兜底退化的组合拳。这个混合策略背后有三个工程思考。第一小数组用插入排序是因为它常数极小递归调用快排反而浪费函数调用开销第二快排虽然平均快但不能接受最坏情况用堆排做保底第三稳定性的问题标准库里也有专门做稳定排序的分支通常基于归并排序来实现代价是额外空间。再说说对象排序。如果排序的不是整数而是对象那就会涉及一个关键问题你用什么字段来比较大小。比如有一个人名单你既要按姓名排序又希望同名的人按年龄排序那就必须调用两次排序而且第二次必须是稳定的否则同名人的年龄顺序就丢了。这就是为什么理解稳定性不只是考试概念它在真实业务里直接决定结果是否正确。再看海量数据场景。当数据量大到内存放不下时快排、归并这些内存排序算法全部失效这时候用的是“外部排序”。经典的外部排序做法是先把大文件切分成多个能装入内存的小块每块分别排序后写入临时文件然后做多路归并把多个有序文件合并成一个大的有序文件。你看这个过程的每个“小块排序”还是内存排序但整体框架已经变成归并排序思路了。所以归并排序的实际价值绝对大于它在教科书里那两页纸的地位。工程上做排序选型我一般按这个逻辑走先确认数据规模能不能放进内存再确认数据形态数值范围是否可控、分布是否均匀然后确认业务是否需要稳定排序最后看最坏情况能不能接受。这四个问题问完排序方案基本就定下来了根本不需要凭感觉拍脑袋。6. 常见问题与排查实录这一节我把学习排序和工程用排序时最容易踩的坑整理一遍每个都是我看别人写代码、自己排查时反复遇到的典型问题。问题一快排写成最坏情况还不自知。最常见的写法就是每次固定取最后一个元素当pivot然后输入恰好是一个基本有序的数组。此时每一次分区都极度不平衡递归深度接近n函数调用栈直接爆炸时间复杂度退化成O(n²)。排查方法很简单在递归函数里打印当前区间的low和high观察递归深度或者输入一组升序排列的数据做测试如果排序1万个数就要好几秒基本可以断定退化了。解决方法也直接pivot用三数取中或者随机选取不要让数据分布来支配你的算法命运。问题二排序不稳定导致业务结果异常。我举一个真实场景。某业务系统需要对一个订单列表做二次排序先按订单状态分桶再在桶内按创建时间排序。如果第二次用的是不稳定排序那么相同创建时间的订单可能被打乱原有顺序如果早期已经按优先级排过序这个顺序就会丢失。排查时最容易被忽略因为单独看排序结果“是有序的”你得对比排序前后相同键元素的相对顺序才能发现问题。解法是严格区分“值相等但语义不同”的数据用(key, 原始索引)这种复合键来做排序或者干脆用稳定排序。问题三递归深度造成的栈溢出。归并排序和快速排序都是递归实现数据量大的时候递归深度可能达到几千甚至上万层。在很多运行时环境里默认栈大小是固定的递归太深直接StackOverflow。这个问题在面试里很隐蔽因为面试官给你的测试数据可能很小你根本不会触发。排查方式是估算递归深度快排优化后平均O(log n)最坏O(n)归并稳定O(log n)。如果深度不可控解决方案有几个快排及时转堆排序兜底、把递归改成循环显式用栈模拟、或者调整运行时栈大小。我遇到过的最粗暴解法是——直接换迭代式排序一了百了。问题四归并排序的额外空间被忽略导致OOM。归并排序需要一个与原数组等长的辅助数组。如果你对一个大数组做归并排序空间占用是原数组的两倍内存敏感场景下这可能直接导致内存溢出。很多人只记得归并是O(n log n)的时间复杂度完全忘了空间复杂度这回事。排查时看内存曲线就能定位。解决方法是换原地排序堆排序对空间极度友好或者把数据量拆小、分批归并也就是外部排序的思路。问题五Comparator逻辑写反或忽略相等情况。这个话题看起来基础但特别容易出事。比如你要按分数降序排列结果写成了升序数据看似有序但方向全反或者Comparator里只处理了 0和 0漏掉了 0的情况导致某些语言的标准排序认为比较函数传递性不成立排序结果变成“薛定谔的有序”。排查经验是先拿一个只有两三个元素的最小数据集测试人脑模拟一遍排序过程再用大量随机数据跑一遍如果结果异常八成是Comparator的边界条件处理不全。问题六非比较排序的边界条件踩坑。计数排序如果不知道数据最小值直接按最大值开数组可能浪费海量空间基数排序如果位数不一致短的数需要补零处理否则位数不同的数字会排错。这类问题最让人头疼的地方是它对大多数数据表现正常但只要出现一个特殊值整个结果就是错的。所以用非比较排序前务必对数据做一次边界审查宁可先扫描一遍拿到最小值和最大值再决定开多大的桶。结尾的一些实践体会排序这东西学到后面你会发现它的魅力不在于“会写十种排序”而在于“面对一个问题你能判断哪种排序根本不值得尝试”。我个人最大的进步发生在一个项目里当时要处理几千万个订单记录按时间排序再分页展示直接全字段排序慢到不可接受后来换成“先按时间分桶、桶内走插入排序、再归并合并”的组合方案整个过程快了一个数量级。这个经历让我彻底理解了第八章的价值——排序是数据结构与算法思维的浓缩同一个数组不同的排序方式背后是完全不同的性能天梯。最后分享一个实用建议学完每类排序自己动手维护一份“排序算法速查表”把复杂度、稳定性、最优场景、最坏场景写清楚面试前拿出来过一遍比临时翻书有用得多。排序考点万变不离其宗复杂度边界和稳定性这两把刷子握稳了不管题目怎么变你都能找到切入点。
