★ FEATURED ARTICLE 如果你被问“排序算法先学哪个”很多人会脱口而出冒泡排序。但我在给新人讲算法时反而更愿意从选择排序开始。原因很简单它的核心思路可以用一句话讲明白——每一轮从剩下的元素里挑一个最小的放到已排好部分的末尾。这句话听上去像废话可背后牵扯到循环边界、索引选择、交换次数、稳定性等一堆值得掰开揉碎的东西。这篇“每日一算法”就拿选择排序开刀从思想到代码再到面试常问的坑一次性讲透。适合正在被算法入门折磨的朋友也适合准备笔试面试、想快速把排序基础捡回来的开发者。1. 选择排序整体设计与思路拆解1.1 核心思想每一轮只干一件事选择排序的思路非常朴素你可以把它想象成在一排乱序的队伍里反复“挑矮子”。假设有 5 个人排队身高分别是 175、160、185、150、170。你要把这支队伍按从矮到高排列。最笨但有效的办法是先在所有人里找出最矮的那个人让他站到第一位然后从剩下 4 个人里再找出最矮的站到第二位接着从剩下 3 个人里找最矮的站到第三位……直到只剩最后一个人排序自然完成。这就是选择排序的模型。对应到数组上每一轮的处理逻辑只有三步从待排序区间里找到最小元素的下标把最小元素与待排序区间的第一个位置交换将待排序区间的左边界向右移动一位。值得注意它和“冒泡排序”的直观感觉不同。冒泡排序是一路两两比较、不断把大元素往后“冒”选择排序则是一轮扫描完直接定位到最小值的位置再做一次交换。所以选择排序的特点是比较很勤快但交换很“吝啬”。这一点在后面分析复杂度时会变成它的优势。1.2 为什么值得专门为它写一篇很多初学者会问选择排序明明效率不高为什么还要学第一个原因它是理解“选择类算法”的基石。后面学堆排序时你会发现堆排序本质上就是选择排序的“升级版”同样每轮选一个最值只是它用一个二叉堆把“找最值”的耗时从 O(n) 降到了 O(log n)。不懂选择排序就很难理解堆排序为什么要设计堆这个结构。第二个原因它在特定场景下仍然有实用价值。当数组规模很小比如几十个元素并且交换元素的开销远大于比较元素的开销时选择排序的“最少交换次数”特性就很香。因为无论数据怎么乱它最多只会发生 n-1 次交换。相比之下冒泡排序在最坏情况下交换次数也是 n(n-1)/2和它的比较次数一个量级代价高得多。第三个原因它是训练循环边界感和调试能力的绝佳素材。算法虽简单但很容易在“循环起点是 i 还是 i1”“最小值下标要不要更新”“空数组会不会越界”这些地方翻车。把选择排序写对、写稳很多排序类算法的基本功也就顺带练出来了。1.3 和冒泡排序、插入排序的定位差别学排序时最怕把几个 O(n²) 排序搞混。我用一个表格把选择排序和它最常被比较的两位“邻居”列在一起。维度选择排序冒泡排序插入排序核心动作选择最小值 / 最大值相邻比较后交换把当前元素插入到已排序区比较次数固定 n(n-1)/2最好 O(n)最坏 O(n²)最好 O(n)最坏 O(n²)交换次数最多 n-1 次最多 n(n-1)/2 次赋值操作较多但可控制在 O(n²)稳定性不稳定稳定稳定适合场景小规模、交换代价高教学示例、基本有序数组数据基本有序、在线排序从表格能看出选择排序最大的“记忆点”就是稳定性和交换次数。它不稳定不是实现细节的问题而是“跨距离交换”这一策略决定的一个最小值可能从数组末尾直接换到最前面途经的相同值相对顺序就乱了。至于插入排序虽然同样是 O(n²)但在基本有序的数据上表现出色因为内层循环能提前退出而选择排序不管数据是否有序都要傻傻地把剩下元素全扫一遍。理解了这些差异实际选型时才不会拍脑袋。2. 核心细节解析与实操要点2.1 手工推演一次完整的排序过程光讲概念不够我拿一个经典例子手推一遍。假设待排序数组是[64, 25, 12, 22, 11]第 1 轮i0待排序区间是下标 0 到 4。扫描全部元素找出最小值 11下标为 4。把下标 4 的元素与下标 0 的元素交换数组变成[11, 25, 12, 22, 64]第 2 轮i1待排序区间是下标 1 到 4。此时剩余元素是 25、12、22、64。扫描后最小值是 12下标为 2。交换下标 1 和下标 2 的元素数组变成[11, 12, 25, 22, 64]第 3 轮i2待排序区间是下标 2 到 4。剩余元素是 25、22、64最小值是 22下标为 3。交换下标 2 和下标 3 的元素数组变成[11, 12, 22, 25, 64]第 4 轮i3待排序区间是下标 3 和 4。剩余元素是 25 和 64最小值是 25刚好就在下标 3此时可以不交换或者做一次“自己和自己交换”的无聊操作。数组保持不变[11, 12, 22, 25, 64]到这里循环结束因为当 i 指向最后一个元素时它天然就是剩余区间里的最小值没必要再比较。观察这个过程你会发现每轮结束后下标 0 到 i 这部分就是全局最小的一批元素而且是最终位置。这个性质叫“局部有序逐渐扩张”和插入排序“从前往后边读边插”的感觉完全不同。2.2 代码实现Python 和 C 两个版本先看 Python 版本代码非常贴近算法描述def selection_sort(arr): n len(arr) for i in range(n - 1): min_index i for j in range(i 1, n): if arr[j] arr[min_index]: min_index j if min_index ! i: arr[i], arr[min_index] arr[min_index], arr[i] return arr这里有两个关键点。第一外层循环是range(n - 1)不是range(n)。因为最后一个元素不需要再和任何人比较它是剩余元素中的唯一选择。第二内层循环从i 1开始而不是从i开始。因为arr[i]自己和自己比较没有意义只会白白浪费时间。虽然多一次比较不影响正确性但写代码就应该写出最干净的版本。再看 C 版本方便面试手写或者嵌入式场景使用#include algorithm void selectionSort(int arr[], int n) { for (int i 0; i n - 1; i) { int minIdx i; for (int j i 1; j n; j) { if (arr[j] arr[minIdx]) { minIdx j; } } if (minIdx ! i) { std::swap(arr[i], arr[minIdx]); } } }如果你在面试中以“原地排序”为目标这个版本就是满分解。std::swap本质是三次赋值如果你所在环境不允许用 STL可以自己手写int temp arr[i]; arr[i] arr[minIdx]; arr[minIdx] temp;2.3 复杂度与稳定性两个容易被问倒的点选择排序的时间复杂度可以拆成两部分比较次数和交换次数。比较次数固定是n(n-1)/2。因为第 0 轮要比较 n-1 次第 1 轮 n-2 次第 2 轮 n-3 次……加起来就是等差数列求和。不管你给的数据是完全有序、完全逆序还是乱序这个数字都不会变。所以选择排序的最好、最坏、平均时间复杂度都是 O(n²)。交换次数很有特点。每轮最多只交换一次所以整个排序过程最多交换 n-1 次。如果数组已经有序并且我们写了if (minIdx ! i)这个判断那一次交换都不发生。这是选择排序在“交换代价极高”场景下的核心优势。空间复杂度是 O(1)因为除了临时变量之外只需要常数级别的额外空间。它是典型的不稳定排序。我用一个例子说明不稳定性[5a, 5b, 3]这里用 5a 和 5b 表示两个值相同但原始顺序不同的元素。第一轮选择排序会找到最小值 3下标为 2。然后把 3 和下标 0 的 5a 交换数组变成[3, 5b, 5a]原本在 5a 后面的 5b 现在跑到 5a 前面去了两个相等元素的相对顺序被破坏所以选择排序不稳定。如果你拿这个问题去面试光说“不稳定”不够最好能像这样当场举出反例。2.4 可以做的两个小优化选择排序的朴素版本已经很好理解但还有两个常见优化思路。优化一在交换前加if (minIdx ! i)判断。这个判断可以减少无意义的“自己交换自己”虽然不能降低时间复杂度但能减少赋值次数对性能有一点实际帮助。优化二每轮同时找最小值和最大值。这样一轮可以放两个元素到位最小值放到左边最大值放到右边。外层循环的次数可以减半但内层扫描的范围仍然是每轮逐步收缩。要注意的是如果最小值和最大值的位置有重叠交换逻辑会变得很绕需要处理“先换最小值再换最大值时发现位置已被覆盖”的情况。这个优化适合数据量较大且想写点“升级版”的时候用面试时主动提出来反而能加分。还有一个值得了解的变种是“堆排序”它把“线性扫描找最小值”升级成“堆顶直接取最小值”时间复杂度从 O(n²) 降到 O(n log n)。理解选择排序是理解堆排序的天然跳板。3. 实操过程与核心环节实现3.1 从“暴力交换”到“记录下标”的优化很多初学者第一次写选择排序会把交换动作直接放在内层循环里写成这样def bad_selection_sort(arr): n len(arr) for i in range(n): for j in range(i 1, n): if arr[j] arr[i]: arr[i], arr[j] arr[j], arr[i] return arr这段代码在某些测试用例下能跑出正确结果但它有两个问题。第一它每发现一个比arr[i]小的元素就立刻交换导致可能在同一次内层循环里交换很多次。这实际上是“交换式冒泡排序”的变体而不是严格意义上的选择排序因为选择排序每一轮应该只交换一次。第二如果你把内层循环改成从 i1 开始但外层循环是range(n)最后一轮会空转一次不会报错但不够严谨。正确的做法是“记录下标延迟交换”。内层循环只是不断更新min_index找到本轮真正的全局最小值下标后在外层循环体内统一交换一次。这个差异是选择排序的精髓面试时手写代码一眼就能看出你是真懂还是背代码。我第一次给别人讲这个差异时打了这么个比方暴力交换像逛街买衣服看到一件便宜的就立刻把身上衣服换掉结果后面又看到更好的还得再换记录下标则是先把最便宜的那件记在心里逛完一整条街再一次性买下来。选择排序讲究的是“看完再动手”。3.2 边界条件空数组、单元素、重复值算法写得对不对边界条件很关键。空数组[]n 0外层循环range(n - 1)等价于range(-1)不会进入循环函数直接返回空数组。这个行为符合预期。单元素数组[5]n 1外层循环range(0)同样不会进入循环直接返回。看起来没问题但如果你把外层循环写成range(n)虽然也不会越界可每轮启动一次无意义的扫描不够干净。全重复数组[3, 3, 3, 3]每一轮扫描都会让min_index停在当前最小的合法下标最终不发生任何交换数组保持不变。这体现了if (min_index ! i)判断的价值。真正容易出问题的其实是大数组里元素类型不一致。在 Python 里如果数组是[3, 5, None]比较运算符会直接抛 TypeError。选择排序依赖运算符所以它要求数组元素是同类型且可比较的。这在理论上不是算法问题但实操中经常被忽略。3.3 可视化验证用打印看每轮状态调试排序算法最直观的办法就是打印数组状态。写一个带日志的版本def selection_sort_debug(arr): n len(arr) print(初始状态:, arr) for i in range(n - 1): min_index i for j in range(i 1, n): if arr[j] arr[min_index]: min_index j if min_index ! i: print(f第 {i} 轮: 找到最小值 {arr[min_index]} (下标 {min_index})与 {arr[i]} (下标 {i}) 交换) arr[i], arr[min_index] arr[min_index], arr[i] else: print(f第 {i} 轮: 最小值 {arr[i]} 已在正确位置无需交换) print(当前数组:, arr) return arr拿前面的例子跑一遍初始状态: [64, 25, 12, 22, 11] 第 0 轮: 找到最小值 11 (下标 4)与 64 (下标 0) 交换 当前数组: [11, 25, 12, 22, 64]这种输出对理解算法非常有帮助。我建议所有初学者都养成“给算法加日志”的习惯比单纯看代码想象执行过程高效得多。熟练以后可以把日志去掉再对照时间复杂度和空间复杂度去分析。3.4 性能实测感受一下 O(n²) 的“成长曲线”算法复杂度的意义光看公式是不够的最好动手测。我写了一个简单的测试脚本用随机数据测选择排序运行时间import random import time def time_selection_sort(n): arr [random.randint(0, 100000) for _ in range(n)] start time.perf_counter() selection_sort(arr) return time.perf_counter() - start for size in [1000, 2000, 4000, 8000, 16000]: print(fn{size}, 耗时{time_selection_sort(size):.4f}s)输出大致会是n1000, 耗时0.0040s n2000, 耗时0.0120s n4000, 耗时0.0390s n8000, 耗时0.1450s n16000, 耗时0.5600s可以看到当 n 从 1000 到 2000规模翻一倍耗时几乎翻四倍。这就是 O(n²) 的直观体感。随着 n 继续增大差距会越来越夸张。到十万级数据时选择排序就会明显“卡顿”这时候你才会真正理解为什么工业界很少用 O(n²) 的排序处理大数据。4. 常见问题与排查技巧实录4.1 常见错误速查表我把平时见到的选择排序翻车案例整理成一个表格方便你对照自查。错误类型错误写法示例后果正确做法外层循环越界for i in range(n)最后一轮空转增加无意义比较用range(n - 1)内层循环起点错误for j in range(i, n)多一次自己和自己比较效率低用range(i 1, n)最小值下标未更新if arr[j] arr[i]:退化成冒泡式交换破坏选择排序特性用min_index记录本轮最小值交换前没有判断下标直接swap(arr[i], arr[minIdx])有序时出现自己交换自己浪费赋值加if (minIdx ! i)判断稳定性认知错误认为选择排序“通常稳定”面试答错概念记住它是不稳定排序且要能举反例把最小值初始化为固定值min_index 0写在内层每轮都无法正确找到当前区间最值初始化为当前区间起点i这里重点说明“最小值初始化为 0”这个坑。如果你在内层循环开始前写死min_index 0那么每一轮都会拿当前区间元素和数组的第一个元素比较。第一轮可能碰巧没问题第二轮开始就会选出错误的最小值因为数组第一个元素可能已经在上一轮被换成了全局最小而它根本不属于当前待排序区间。正确写法是让min_index从i开始。4.2 面试常被追问的三个点面试官考选择排序基本绕不开下面三个问题。第一它是稳定的吗答案是“不稳定”必须能举出类似[5a, 5b, 3]的反例。如果面试官追问“能不能改稳定”通常也是可以做到的在找最小值时选择“最后一个”最小值交换时把中间元素依次后移而不是直接交换。这个改动有意思但很少被考察能说出来是加分项。第二复杂度为什么是 O(n²)你要能快速给出n(n-1)/2的比较次数推导并解释为什么比较次数与初始顺序无关。顺带强调交换次数最多n-1次这是选择排序最容易被人记住的优势。第三什么时候用选择排序而不是快速排序或归并排序一种典型回答是当数据量很小、且一次交换的代价远大于一次比较时选择排序的交换次数优势很明显。比如在嵌入式环境中操作外部存储设备的写入次数有限选择排序就可以比冒泡排序更省寿命。但要注意现代通用场景下O(n log n)的排序往往更适合。还有一个常见的追问是“和插入排序比谁快”。答案不是绝对的要看数据特征。如果数组基本有序插入排序远胜选择排序如果数组完全乱序且交换代价高选择排序可能更有优势。面试时给出这种“看场景”的回答比背结论要加分。4.3 个人踩坑记录我自己早期学选择排序时踩过一个很典型的坑为了省一个变量直接记录“最小值”而不是“最小值下标”。每次内层循环找到更小的值就更新min_value最后交换时才发现不知道它在哪里。代码写着写着就变成“先找值再找下标”白白多写了一次循环。后来我把教训总结成一句话排序算法里位置比数值重要。因为最终要做的是交换交换必须知道两个位置。记录最小值本身没有任何问题但记录下标才是能直接落地的信息。另一个坑是测试时只顾着看最终结果是否正确忽略了“排序稳定性”这个指标。我写完一个选择排序版本后花了很长时间纠结“为什么我的结果和某个教程的不一样”后来发现那个教程用的是稳定版变种而我用的是普通版本。对相同输入稳定变种可能保持原始相对顺序普通版本则不相同。所以说学算法不能只看“排没排对”还要看“用了什么策略排的”。5. 还能扩展到哪里5.1 从选择排序延伸出堆排序选择排序最明显的瓶颈是“线性扫描找最小值”。这需要 O(n) 时间导致总复杂度 O(n²)。如果有一个数据结构能让我们在 O(log n) 内找到并移除最小值整体复杂度就会变成 O(n log n)。这个数据结构就是二叉堆。堆排序的核心思路是先把数组构建成最大堆然后反复把堆顶元素最大值与堆末尾元素交换缩小堆的范围再堆化剩余元素。它的每一轮都是一个“选择最大值”的过程和选择排序完全同构。理解了选择排序再去看堆排序的“建堆”“堆化”“交换”三步操作理解成本会低很多。我经常把选择排序、堆排序放在一起学。先手写选择排序再手写堆排序你会明显感受到“数据结构优化算法”是一条多么自然的演化路径。所谓“每日一算法”不一定每天学全新的内容把新旧知识连起来反而记得更牢。5.2 每日一算法的正确打开方式我在带新人时总结了一套“每日一算法”的实操方法选择排序就是很好的试验田。第一步先用纸笔画一个小数组比如 6 个元素手动跑一遍排序流程把每轮的最小值和交换位置标出来。这一步不要省略它对建立空间感很重要。第二步不看任何资料直接手写代码。写完后用随机数组、空数组、单元素数组、全重复数组四组用例测一测。第三步把代码贴进调试版本里打印每次交换后的数组和你纸上推演的结果对照。第四步给自己提三个问题这个算法稳定吗时间复杂度为什么是这个在什么场景下优于别的排序如果每天坚持这个方法用不了两周你的排序基础就会非常扎实。不要贪多一天吃透一个算法比一天囫囵吞五个算法强得多。算法就像肌肉记忆训练量要够但单次训练的“消化率”更重要。关于选择排序最后我还想补一个小建议别只满足于写出“能跑的版本”。多想想几个“如果”比如如果数组是逆序的怎么办如果有大量重复元素怎么办如果只能交换不能申请额外空间怎么办。这些思考会让你的每日一算法真正变成“每日一理解”而不是“每日一背代码”。
阅读完成 · 觉得有帮助？
