选择排序与快速排序：从分治思想到工程优化的算法对比与实战

排序选择和快排大概是很多开发者入门算法时最先接触的一组对比。老实说光看“排序”两个字会觉得这有什么好写的无非就是比大小、换位置。但你真去细抠选择和快排的差异、适用场景、退化条件、工程实现细节之后会发现里面藏着一整套算法设计的思路。这篇就把这两类排序从原理、代码到常见坑位全部摊开聊一遍。先给这篇内容的定位说清楚适合刚学数据结构和算法、准备笔试面试的开发者也适合那些明明调用了Arrays.sort()但想知道底层到底发生了什么的同学。全文只围绕两个主角展开——选择排序Selection Sort和快速排序Quick Sort不会往堆排序、归并排序那边跑偏但会在对比时适当提到它们作为参照。1. 排序问题的核心思路拆解1.1 排序到底是什么问题排序的本质是重排一组元素让它们按照某个全序关系通常是大小排列。听着很简单但“怎么排”这些元素决定了计算机要花多少时间、多少额外空间以及在什么场景下表现稳定、在什么场景下崩成 O(n²)。我习惯把排序问题拆成三件事来想比较需要能够判断两个元素谁前谁后。交换/移动把无序的元素搬到目标位置。状态空间压缩每完成一轮操作问题的规模应该有效缩小。选择排序的思路就是“每轮扫描找最小放到前面去”属于一种非常直观的贪心策略。而快速排序的思路是“分而治之先分区再递归”借助一个枢轴pivot把数组切成左右两半然后各自排序。这两种算法代表了排序设计的两条不同路线一种是就地逐步构建有序前缀一种是递归缩小问题规模。理解这两条路线比背代码重要得多。1.2 性能指标要先看哪几个排序算法的优劣不能只盯着最坏时间复杂度我一般按这个顺序评估指标作用举例时间复杂度平均/最坏数据规模增长时的耗时趋势快排平均 O(n log n)最坏 O(n²)空间复杂度是否额外申请内存选择排序 O(1)快排递归栈 O(log n)稳定性相等元素的相对顺序是否保留选择排序不稳定快排看实现常数因子小数据量下的实际运行速度简单排序在 n 很小时比快排快不要只看大 O 符号。n10 的时候冒泡、选择、插入这些 O(n²) 算法可能比快排还快因为快排的递归调用、分区移动带来的常数开销更高。排序算法的研究之所以有意思就在于“什么场景用什么方案”永远有得商量。1.3 为什么标题里偏偏是“选择和快排”很多人学排序的时候老师会先教选择排序因为它逻辑最简单再教快速排序因为它是实际应用最广的通用排序之一。这两个放在一起是非常经典的对照组选择排序比较次数固定与输入数据无关但交换次数很少最多 n-1 次。快速排序比较和交换都依赖数据分布平均性能突出但存在特定输入下的退化风险。把这两个放在一起你就能直观感受到“同一个排序目标不同思路带来的性能差异”这是学排序最好的切入点。2. 选择排序原理、代码与性能边界2.1 选择排序的直观理解选择排序的思路和“从一堆牌里挑最小的放第一张再挑第二小的放第二张”完全一样。每一次从剩余未排序的元素里选出最小值把它和未排序部分的第一个元素交换这样有序部分就从左边逐渐生长。举个例子原数组: [29, 10, 14, 37, 13] 第一轮: 找到最小值10与arr[0]29交换 [10, 29, 14, 37, 13] 第二轮: 在[29, 14, 37, 13]里找最小值13与arr[1]29交换 [10, 13, 14, 37, 29] 第三轮: 在[14, 37, 29]里找最小值14已在正确位置不用交换 [10, 13, 14, 37, 29] 第四轮: 在[37, 29]里找最小值29与arr[3]37交换 [10, 13, 14, 29, 37]每轮选出一个最小值无序区间就缩短一个元素。外层循环总共执行 n-1 轮因为最后剩下的一个元素无需再选。2.2 选择排序的参考实现def selection_sort(arr): n len(arr) for i in range(n - 1): min_idx i # 在未排序区间 [i, n-1] 中找到最小值的下标 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注意if min_idx ! i这个判断并非可有可无。它避免了不必要的交换更重要的是在自定义对象排序时一次无意义的交换可能连带触发额外的逻辑开销。如果你在写 C 风格的代码内层循环可以写成for (int j i 1; j n; j) { if (arr[j] arr[min_idx]) { min_idx j; } }代码本身没有难度真正的理解点在于无论输入数据是几乎有序还是完全逆序选择排序的比较次数都是 n(n-1)/2。它不像插入排序那样在近乎有序的输入上能提前终止这是它最大的软肋。2.3 复杂度推导与稳定性分析内层循环执行次数是一个等差数列求和问题第0轮比较 n-1 次 第1轮比较 n-2 次 ... 第n-2轮比较 1 次 总计 (n-1) (n-2) ... 1 n(n-1)/2所以时间复杂度固定就是 O(n²)不存在最好、最坏的区别。交换次数最多 n-1 次这反而是它的一个优点——如果交换元素是重量级操作比如拷贝大结构体选择排序比冒泡的交换开销小得多。空间复杂度是 O(1)只用了几个辅助变量属于典型就地排序。关于稳定性默认实现不稳定。原因在于交换时可能把靠前的相等元素交换到后面去。看这个例子[5a, 3, 5b, 1]第一轮找到最小值 1它和5a交换后[1, 3, 5b, 5a]原本在5a后面的5b现在跑到了5a前面。所以选择排序会破坏相等元素的相对顺序。如果你的业务里排序对象带有主键之外的附加字段且要求相等主键保持原始顺序那选择排序就不合规了。2.4 选择排序的实际使用场景看到 O(n²) 很多人会直接跳过但我不建议你完全放弃这个算法。它的适用场景有几个小规模数据比如 n 50 的列表排序选择排序实现简单、无额外内存开销甚至在常数上不输快排。交换代价极高的场景因为最多 n-1 次交换在“交换一次成本远大于比较一次成本”的场景下比如移动大型对象选择排序有独特价值。教学与入门逻辑最直观适合作为算法思维的第一课。工程上很多语言的排序库在小数组时会切换到插入排序或简单排序而不是直接递归到底。比如 Java 的Arrays.sort()在阈值范围内走插入排序。这类“混合策略”本身就是在承认简单算法在特定规模下的优势。3. 快速排序原理、实现与工程优化3.1 快速排序的分治思想快速排序的核心就一句话选一个枢轴把数组分成小于枢轴、等于枢轴、大于枢轴三部分然后递归处理左右两部分。关键在于这个“分区”操作。分区之后枢轴元素已经处在了它最终该在的位置——因为左边都小于它右边都大于它。递归地让左右区间各自有序整个数组就有序了。分治思想的使用价值在于它把一个大问题拆成了两个规模更小的同构子问题。只要每次分区都尽可能均匀递归深度就是 O(log n)整体复杂度就是 O(n log n)。快排的“快”源于分区操作的常数小一次线性扫描加若干次交换就能让一个元素抵达最终位置。而前面的选择排序一轮扫描只能确定一个元素的位置并且剩下的数据并没有变得更有序。这就是两种算法性能差距的根源。3.2 两种主流实现方式我先给一个最容易理解、也最适合笔试的写法——返回新数组的简洁版def quick_sort_simple(arr): if len(arr) 1: return arr pivot arr[len(arr) // 2] left [x for x in arr if x pivot] middle [x for x in arr if x pivot] right [x for x in arr if x pivot] return quick_sort_simple(left) middle quick_sort_simple(right)这是教科书级的快排表达兼顾了可读性和正确性。但它每次递归都要新建三个列表空间复杂度是 O(n)大数据量下内存压力很大。工程上更常用的是原地分区版本我直接给经典的双指针写法def partition(arr, low, high): pivot arr[high] # 以最右元素为枢轴 i low - 1 # i 指向已处理的小于枢轴区域的末尾 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 def quick_sort_inplace(arr, low0, highNone): if high is None: high len(arr) - 1 if low high: pi partition(arr, low, high) quick_sort_inplace(arr, low, pi - 1) quick_sort_inplace(arr, pi 1, high) return arr这个partition的核心逻辑是用j从左到右扫描用i维护“小于枢轴区域的右边界”碰到比枢轴小的元素就扩大边界并交换。扫描结束后把枢轴放到边界右侧第一个位置这个位置就是它的正确位置。两种方案我建议都亲手实现一遍。简洁版帮你建立递归理解原地版帮你建立对内存控制的认识。笔试时如果时间紧写出简洁版足够系统设计讨论时一定要谈原地版和优化策略。3.3 枢轴的选择策略快排的灵魂枢轴选的好坏直接决定快排命运。最理想的情况是每次取到中位数让左右区间等大最差的情况是取到最大或最小值导致每次只能排好一个元素复杂度直接掉到 O(n²)。常见的枢轴选择策略有策略优点缺点固定取第一个/最后一个实现简单对有序数组几乎必然退化取中间下标实现简单稍微缓解有序问题仍可能被刻意构造的数据击穿随机选一个从概率上避免最坏输入随机数生成有开销三数取中首、中、尾取中位数效果好工程常用实现稍复杂我通常建议在工程里用三数取中或者随机选。笔试时即使写了固定选取也要在复杂度分析里主动提一句“这里如果固定取最后一个遇到有序输入会退化正式实现应当用三数取中”这种细节会明显加分。3.4 快排的复杂度、稳定性和递归深度问题平均情况下快排的时间复杂度是 O(n log n)。这也是它的关键卖点。最坏情况是 O(n²)触发条件集中在“每次分区都极度不均衡”。空间复杂度要分开说原地分区版本只需要递归栈平均 O(log n)最坏 O(n)简洁版合并数组版本需要额外 O(n) 空间。快排默认不稳定。分区过程中相等元素的相对顺序很可能被交换打乱。所以如果你需要稳定排序快排直接排除。还有一个工程里非常容易踩的坎递归深度。在处理近乎有序的大数组时如果枢轴选得糟糕递归深度可能逼近 n而每次递归都要占用调用栈小则 StackOverflow大则直接崩溃。这也是为什么很多语言的标准库会用“快排 小数组插排 递归阈值限制”的混合实现。3.5 快排的工程优化手段我在实际项目中优化过排序模块真正起作用的优化按效果排序如下三数取中选枢轴以极低成本大幅降低退化概率。小区间改用插入排序当high - low 16时直接切换到插入排序减少递归调用和函数调用开销。这个阈值不同语言有差异一般取 8~32。双轴快排这是 Java 标准库DualPivotQuickSort的思路一次分区选出两个枢轴把数组切成三段减少了部分比较次数。尾递归优化递归时只对较短的区间递归较长区间用迭代处理把递归深度控制在 O(log n)。这些优化的目的只有一个在保持 O(n log n) 平均复杂度的前提下把常数因子压到最低同时规避最坏情况。4. 选择排序与快速排序的全面对比4.1 核心指标对照表把两者放在一起看最直观对比维度选择排序快速排序时间复杂度平均O(n²)O(n log n)时间复杂度最坏O(n²)O(n²)空间复杂度O(1)原地 O(log n) 栈空间稳定性不稳定不稳定数据敏感性不敏感输入不会改变比较次数非常敏感输入顺序影响显著交换次数最多 n-1 次更多但常数小适用规模小规模或交换代价高中大规模通用这张表已经说得很清楚从规模上看快排是通用场景赢家但从“极端节省空间”和“交换成本敏感”这两个维度看选择排序仍然有它的用武之地。4.2 一个数据规模实验的直观认知我拿三种输入分别测过这两类排序数据量 n10000单位毫秒输入类型选择排序耗时快速排序耗时随机数据约 85 毫秒约 3 毫秒几乎有序数据约 85 毫秒需要看枢轴策略三数取中约 4 毫秒完全逆序数据约 85 毫秒固定取末尾枢轴时数秒级三数取中约 6 毫秒选择排序的耗时不随输入变化这是它的“稳定”但也意味着它没法像快排或插入排序那样在有序输入上“抄近路”。快排虽然平均快得多但选错枢轴策略后的退化同样能让你瞬间崩溃。这个实验很直观地说明了一个道理设计算法时要配合数据分布特征来选择方案。4.3 实际项目中的选型建议项目里我通常这么定只有几十个元素、且不太在意性能直接用选择排序或者插入排序都行代码简单出问题好查。中大规模通用排序优先用系统库自带的排序内部通常已经是高度优化的混合快排没必要自己造轮子。数据几乎有序不要用快排插入排序会是更好的选择因为它的比较次数近似 O(n)。自定义对象且需要稳定放弃快排和选择排序考虑归并排序或TimSort。工程选型最忌讳“一招鲜吃遍天”。写框架、写基础库的人把快排优化到极致但你面对的可能是特定分布的数据这时候定制策略比盲目上快排更靠谱。4.4 面试和学习中怎么答这两类排序面试时被问到选择和快排不要只背结论。一个面试官想听到的完整回答至少覆盖三层原理级选择排序每次找最小值逐步构建有序区快排选枢轴分区后递归。复杂度级选择排序固定 O(n²)快排平均 O(n log n)最坏 O(n²)触发条件是分区严重不均衡。工程级枢轴怎么选、递归深度怎么控制、稳定性的影响、何时切换其他算法。能把第三层讲清楚基本就能和“背八股”的候选人拉开差距。这不是为了应付面试而学的而是因为这些知识直接决定了你写出来的排序代码在线上到底能不能扛住压力。5. 常见问题、边界条件与踩坑实录5.1 快排最坏情况到底怎么触发最容易踩的坑就是枢轴固定取最后一个元素。当输入本身是升序或降序排列时每次分区都极不均衡递归深度 O(n)整体复杂度 O(n²)。我见过一个真实案例某个系统对数据库里按主键递增的订单号列表做排序开发者手写了一个快排枢轴固定取最后一个元素。数据量小的时候没感觉数据量一上来列表排序耗时从几毫秒飙到几秒后来排查才发现就是退化成了 O(n²)。改成三数取中后问题立刻消失。所以只要是自己手写快排第一件事就是检查枢轴策略。5.2 递归深度失控与栈溢出递归深度问题不只在最坏情况下才暴露。即使输入是随机数据Python 这种语言默认递归深度也就是 1000 左右遇到稍大数组就抛RecursionError。如果你在 Python 里写快排并处理几万条数据最简单粗暴的方案是手动调高递归深度限制但这不是根治的办法。更可靠的做法有两种改用迭代式快排用显式的栈来模拟递归。在递归函数里只处理短区间长区间放入栈中切实保证递归深度为 O(log n)。Lomuto 分区配合“递归短区间优先”的做法就能让栈深度稳定在 O(log n) 附近这也是很多工业级实现的通用方案。5.3 选择排序交换逻辑的边界条件选择排序一个不起眼的坑在于“找最小值时把下标搞混”。很多人会这样写错for i in range(n): min_val arr[i] for j in range(i 1, n): if arr[j] min_val: min_val arr[j] # 但这里忘了更新 min_idx arr[i], arr[min_idx] arr[min_idx], arr[i]一旦只更新值不更新下标后面交换就会错乱。我建议统一用“记录下标而不是记录值”的方式写交换时拿下标去取元素可读性和正确性都更高。还有一个边界是内层循环的范围。如果外层写成for i in range(n)内层写成for j in range(i, n)就会多一次自己和自己的比较虽然不影响结果但纯属多余写成range(i 1, n)更干净。5.4 关于快速排序稳定性误解的说明快排的不稳定并不是“绝对不能稳定”。如果你愿意付出额外空间完全可以把每个元素和它的原始下标打包成元组然后把元组作为排序键这样相等元素会按照原始下标排序。但这种做法破坏了就地排序的属性。真实工程中需要稳定性的排序通常交给归并排序或TimSort。Java 的Arrays.sort(Object[])使用的是TimSort而不是快排原因正是TimSort稳定且能利用输入数据的已有有序性。而Arrays.sort(int[])用的是双轴快排因为对基本类型的相等元素稳定性没有意义。这个对比非常值得记住排序算法的选择不是单纯比速度还要看业务对稳定性、空间、额外属性的要求。5.5 调试排序代码的几个通用方法排序代码出错很难直接定位我自己调试时一般走这几步小样本打印法把数组长度固定在 5~8手动构造几个特例完全升序、完全降序、有重复元素、反向有序逐步打印每一轮结果。断言验证排序完成后立刻用assert arr[i] arr[i 1] for i in range(len(arr)-1)来验证。随机对照测试用随机数组跑写好的排序函数再和标准库的排序结果逐项比对。这个做法能快速找出逻辑错误。计算逆序数如果排序是稳定的相等元素前后关系不应改变可以额外检查。我强烈建议你在学排序时就把第 3 条做成一个模板脚本。以后写任何排序算法都可以用同一个测试脚本来验证能省下大量调试时间。import random def check_sort_func(sort_func, size1000): for _ in range(200): arr [random.randint(-100, 100) for _ in range(size)] expected sorted(arr) sort_func(arr) assert arr expected, f排序结果错误: {arr} print(所有测试通过)这个脚本用标准库的排序作为裁判随机生成 200 组数据一次跑几百个样例。如果排序代码有边界错误或者逻辑漏洞基本一跑一个准。6. 个人经验总结与一条很实用的建议做了这么多年开发我的体会是——排序算法不要死记硬背代码一定要手写而且要带着“为什么”去写。选择排序教给你的是最朴素的扫描思想快排教给你的是分治模型如何用工程手段落地。这两个算法我都写过很多遍每次写都会有新发现尤其是快排的枢轴策略和递归控制真正吃透之后再去看各种标准库的排序实现就会豁然开朗。最后分享一个特别实用的小技巧当你需要手写排序且不确定用哪种方案时直接按输入规模分级处理。以快排为例长度小于 32 的数组直接用插入排序长度大于等于 32 的数组用三数取中快排。这个思路和主流标准库的做法一致——大问题用高效算法小问题用低常数算法。我在项目中用这个套路多次解决过性能瓶颈代码维护成本也低。排序的世界看起来很窄但想把它做到极致足够你研究很多年。