企业官网建设流程全解析

• 教程

选择排序是计算机面试中最基础、被考察频率最高的排序算法之一。本文基于 InterviewGuide 仓库「算法基础与十大排序」系列文档，完整讲解选择排序的核心思想、逐步流程、稳定性分析与复杂度结论，并给出可编译运行的 C++ 实现，同时结合仓库中冒泡排序、插入排序、快速排序等兄弟文档与算法基础文档，帮助读者建立"稳定排序 / 原地排序 / 时间复杂度 / 空间复杂度"的整体知识框架，做到面试手撕不卡壳。

一、选择排序的核心思想

选择排序（Selection Sort）的思路非常直观：给每个位置选择当前元素中最小的那个。

具体来说：

1. 给第一个位置选择当前序列中最小的元素；
2. 在剩余元素里面给第二个位置选择第二小的元素；
3. 依次类推，直到第 n-1 个元素；
4. 第 n 个元素不用选择了，因为只剩下它一个最大的元素了。

也就是说，每一趟排序都会确定一个位置的最终元素，属于"一趟选一个、位置逐个落定"的典型思路。整个过程可以用下面这张示意图来理解：

1. 标准流程（四步走）

在未排序序列中完成一趟完整的选择排序，需要遵循以下步骤：

1. 在未排序序列中找到最小（大）元素，存放到排序序列的起始位置；
2. 从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾；
3. 以此类推，直到所有元素均排序完毕；
4. 时间复杂度：O(n²)，空间复杂度 O(1)，非稳定排序，原地排序。

外层循环负责"确定当前位置"，内层循环负责"在剩余区间内找出最值下标"，找到后通过一次swap将最值放到正确位置。这就是选择排序与冒泡排序最本质的区别：冒泡靠相邻元素两两比较、逐步交换把最值"冒"到末尾，而选择排序每趟只做一次交换。

二、稳定性分析：为什么选择排序是不稳定的

先复习一下稳定排序的定义（详见仓库 算法基础文档）：

• 稳定排序：如果 a 原本在 b 的前面，且 a == b，排序之后 a 仍然在 b 的前面；
• 非稳定排序：如果 a 原本在 b 的前面，且 a == b，排序之后 a 可能不在 b 的前面。

那么，在一趟选择中，如果当前元素比一个元素小，而该较小的元素又出现在一个和当前元素相等的元素后面，那么交换后稳定性就被破坏了。

这句话比较拗口，用序列5 8 5 2 9来举例说明：

• 原始序列中两个5的相对顺序是：第一个5在前，第二个5在后；
• 第一遍选择，第一个位置会与整个序列中最小的元素2交换，即5和2的位置对调；
• 交换后，原序列中两个5的相对前后顺序就被破坏了：原本靠后的第二个5现在排在了原本靠前的第一个5前面。

因此可以得出结论：选择排序不是一个稳定的排序算法。这个结论与仓库 算法基础文档 中"十大排序中的非稳定排序"一节的分类完全一致——选择排序（selection sort）属于非稳定排序，时间复杂度 O(n²)。

下面这张动图直观展示了选择排序每一趟的选择与交换过程：

三、复杂度分析：O(n²) 时间、O(1) 空间

选择排序的复杂度特征非常清晰，可以从代码结构直接推导：

• 时间复杂度：O(n²)。外层循环固定执行 n 趟，第 i 趟内层循环需要比较 n-1-i 次，总的比较次数为 (n-1) + (n-2) + … + 1 = n(n-1)/2，因此无论数组初始状态如何（有序、逆序还是乱序），比较次数都固定在 O(n²) 级别。这一点与冒泡排序不同：冒泡排序可以通过"某趟无交换即有序"的标记提前退出（见仓库 冒泡排序文档 中的优化版本），而选择排序没有天然的提前终止机制。
• 空间复杂度：O(1)。整个排序过程只借助常数个临时变量（如下标minIndex），不需要申请额外的数组，属于原地排序。
• 非稳定排序：如第二节所述，相等的元素在交换过程中相对顺序可能被破坏。

综合结论：时间 O(n²)，空间 O(1)，非稳定排序，原地排序。这四条结论是面试中被问到选择排序时必答的关键点。

四、C++ 代码实现（面试手撕版本）

1. 基础版本一

仓库 选择排序文档 给出的第一种写法如下：

void selectionSort(vector<int>& a, int n) { int minIndex; for (int i = 0; i < n; ++i) { minIndex = i; for (int j = i + 1; j < n; ++j) { if (a[j] < a[minIndex]) minIndex = j; } swap(a[i], a[minIndex]); } }

要点拆解：

• 外层循环i表示"当前要确定的位置"，从 0 到 n-1；
• 内层循环j从i + 1开始扫描剩余未排序区间，用minIndex记录最小元素的下标；
• 内层循环结束后，minIndex指向的是[i, n)区间内的最小值下标，执行一次swap(a[i], a[minIndex])即可把最小值放到第 i 个位置。

2. 基础版本二

文档还给出了另一种等价写法，逻辑完全一致，只是变量命名不同，更贴近 vector 容器的使用习惯：

void selectSort(vector<int>& nums) { int len = nums.size(); int minIndex = 0; for (int i = 0; i < len; ++i) { minIndex = i; for (int j = i + 1; j < len; ++j) { if (nums[j] < nums[minIndex]) minIndex = j; } swap(nums[i], nums[minIndex]); } }

面试中推荐以第二种写法为模板：用nums.size()直接取长度，代码更简洁、不易出错。

3. 手撕时的易错点提醒

• minIndex必须在每趟外层循环开始时重置为i，否则会沿用上一趟的最小值下标，导致排序结果错误；
• 内层循环从i + 1开始，不需要和自己比较；
• 比较符号统一用<（找最小）或>（找最大），注意与"升序/降序"需求对应；
• swap可以在i == minIndex时多做一次无意义的自我交换，不影响正确性；若想进一步优化，可以加上if (minIndex != i)判断再交换（这是从代码结构上可以推断的常规优化，并不会改变算法复杂度）。

五、选择排序在十大排序中的定位

选择排序并不是孤立的算法，它与冒泡、插入、希尔、归并、快速、堆、计数、桶、基数排序共同构成面试中的"十大排序"。了解它在整个体系中的位置，有助于回答"为什么选它 / 为什么不选它"这类对比类问题。

1. 十大排序中的稳定排序与非稳定排序

根据仓库 算法基础文档 的总览：

面试考察中一般重点问快排、选择、希尔、堆这几种非稳定排序。

2. 与冒泡排序、插入排序的对比

• 与冒泡排序对比（见仓库 冒泡排序文档）：冒泡排序只交换相邻元素，相等元素不会被交换，因此是稳定的；选择排序每趟可能把一个较远位置的元素交换到前面，容易破坏相等元素的相对顺序，因此是不稳定的。此外，冒泡排序在序列基本有序时可通过"无交换标记"提前退出，而选择排序的比较次数固定为 n(n-1)/2，无法利用输入的有序性。
• 与插入排序对比（见仓库 插入排序文档）：插入排序在已有序的小序列上逐个插入新元素，相等元素会被放在后面，因此是稳定的；选择排序的交换策略决定了它不稳定。
• 适用场景：从代码结构可以推断，选择排序的主要优势是"交换次数最少"（每趟至多一次交换，总共最多 n-1 次交换），在"交换代价远高于比较代价"的场景下有一定意义；但在绝大多数普通场景下，面对 O(n²) 的固定比较次数，其实际表现通常不如插入排序（插入排序在接近有序的数据上可以显著提前结束内层循环）。

六、选择排序在面试考察中的位置

十大排序在面试考察中出现的频率非常高，特别是冒泡排序、快速排序、归并排序等，选择排序则常作为"手撕入门题"或"稳定性辨析题"出现。仓库 面试高频算法真题 中列出了大厂手撕算法中频率较高的题目，其中快速排序、归并排序、堆排序都是对选择排序思想的延伸与升级：

• 快速排序：选择排序"每趟确定一个位置"的思路，在快速排序中演化为"每趟确定一个基准元素的位置，然后对左右区间递归处理"（见仓库 快速排序文档）；
• 堆排序：把"线性扫描找最值"升级为"借助堆结构 O(log n) 找最值"，将时间复杂度优化到 O(n log n)（见仓库 堆排序文档）；
• Top K 问题：仓库 面试高频算法真题 中提到，求解 Top K 可以"使用选择排序的思想，对前 K 个元素部分排序"，时间复杂度为 O(N×K)。

理解选择排序，等于同时理解了"选择式排序"这一类算法的骨架，后续学习堆排序、Quick Select（快排衍生算法）时会轻松很多。

七、回顾与总结

最后，把选择排序的关键结论汇总如下，方便面试前快速过一遍：

1. 思想：每趟从未排序区间选出最小（大）元素，放到已排序区间的末尾，总共 n-1 趟即可完成排序；
2. 流程：找最小（大）→ 放起始位置 → 剩余区间继续找 → 直到全部排完；
3. 复杂度：时间复杂度 O(n²)（比较次数固定为 n(n-1)/2），空间复杂度 O(1)；
4. 性质：非稳定排序、原地排序；
5. 稳定性反例：序列5 8 5 2 9，第一趟5与2交换后，两个5的相对顺序被破坏；
6. 手撕模板：外层for (int i = 0; i < len; ++i)+ 内层扫描记录minIndex+ 一次swap。

相关文档索引：

• 选择排序（本文主题文档）
• 算法基础：稳定/原地/复杂度概念与十大排序总览
• 冒泡排序（含优化版本）
• 插入排序
• 快速排序
• 希尔排序
• 归并排序
• 堆排序
• 计数排序
• 桶排序
• 基数排序
• 面试高频算法真题（含快排、归并、堆、Top K）
• 算法模块食用指南（按人群选择刷题路径）

• 教程