排序（选择和快排）大概是很多开发者入门算法时最先接触的一组对比。老实说，光看“排序”两个字会觉得这有什么好写的，无非就是比大小、换位置。但你真去细抠选择和快排的差异、适用场景、退化条件、工程实现细节之后，会发现里面藏着一整套算法设计的思路。这篇就把这两类排序从原理、代码到常见坑位全部摊开聊一遍。
先给这篇内容的定位说清楚：适合刚学数据结构和算法、准备笔试面试的开发者，也适合那些明明调用了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 符号。n=10 的时候，冒泡、选择、插入这些 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, low=0, high=None): 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 一个数据规模实验的直观认知
我拿三种输入分别测过这两类排序（数据量 n=10000，单位毫秒）：
| 输入类型 | 选择排序耗时 | 快速排序耗时 |
|---|---|---|
| 随机数据 | 约 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, size=1000): 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 的数组用三数取中快排。这个思路和主流标准库的做法一致——大问题用高效算法，小问题用低常数算法。我在项目中用这个套路多次解决过性能瓶颈，代码维护成本也低。排序的世界看起来很窄，但想把它做到极致，足够你研究很多年。
