选择排序的核心原理与工作方式
什么是选择排序
选择排序是一种简单直观的排序算法，其核心思想是每次从未排序的部分中选出最小（或最大）元素，放到已排序端的末尾，以此逐步构建有序序列。关键点在于每次都定位未排序区的最小值并进行一次交换，从而把最小元素“逐步提到”序列的前端。该过程不依赖数据的初始顺序，但需要对每一轮未排序区进行扫描来确定最小值。
在实现上，算法维护一个已经排序好的前缀和一个未排序的后缀。通过不断更新未排序区的起点并寻找其中的最小值，最终得到从小到大排列的数组。由于每次都要进行一个或零个交换，算法的思路简单、实现易懂，适合教学与快速原型实现。
时间复杂度与稳定性
该算法的时间复杂度为O(n^2)，无论数据初始如何，外层循环与内层遍历总是进行相同数量的比较。空间复杂度为O(1)，不需要额外的辅助结构。关于稳定性，默认情况下选取最小值后进行一次交换会破坏相同元素的相对顺序，属于不稳定排序。如果采用移位而非直接交换来把最小值移动到前端，可以在一定程度上保持稳定性，但实现复杂度会提升。
对于需要稳定性的场景，通常会将交换改为将未排序区的最小元素逐个向后移动一位，直至放到正确位置；这样能维护相同元素的相对位置，但涉及多次移动操作，效率会略低于直接交换的一次性操作。
适用场景与对比要点
在数据规模较小、对内存占用要求极低的嵌入式或教学场景下，选择排序因实现简单、可读性好而有优势。与冒泡排序相比，仍然是O(n^2)的时间复杂度，优势并不显著，但实现逻辑更明确且对比测试容易。与快速排序、归并排序等高效排序相比，性能明显逊色，通常不用于大规模数据排序。
在比较排序算法时，选择排序对数据结构的影响较小，且不需要额外的辅助空间，这是一大优点；但由于稳定性与速度方面的局限性，往往只作为入门教学或小型数据集的缓存排序使用。
从原理到实现的完整步骤
步骤概览
排序过程从左到右建立一个已排序区，初始时该区长度为0，未排序区为整个数组。每一轮都在未排序区中寻找最小值的下标，若该下标不等于当前已排序区的起始位置，则进行一次交换，将最小值放置到已排序区的末端。
直到未排序区的长度减为0，整个序列就完成从小到大的排序。遍历与交换的组合是关键，决定了最终的排序结果与成本。
步骤要点
1. 设定起始下标 i，表示已排序区的末端，相应的未排序区为 [i, n)。
2. 在 [i, n) 内寻找最小值的下标 min_idx，通过逐元素比较找到全局最小值的位置。
3. 如果 min_idx 与 i 不同，将 arr[i] 与 arr[min_idx] 交换，使最小值进入已排序区的正确位置。
4. 将 i 向右移动一位，重复上述过程直到 n-1，最终得到有序序列。
边界条件与实现注意
对于空数组或单元素数组，直接返回即可，循环边界需谨慎处理以避免越界。在 min_idx == i 的情况下无需进行交换，避免不必要的操作。若希望得到稳定排序，需要采用移动而非直接交换的方法来将最小值放到前端，这涉及额外的元素移动成本。
代码演示：Python与C++实现
Python实现
以下实现直接遵循原理：每一轮找到未排序区的最小值下标，然后交换至当前已排序区末端。通过注释标识关键步骤，便于快速理解。
def selection_sort(arr):n = len(arr)for i in range(n - 1):min_idx = ifor j in range(i + 1, n):if arr[j] < arr[min_idx]:min_idx = jif min_idx != i:arr[i], arr[min_idx] = arr[min_idx], arr[i]return arrC++实现
下面给出 C++ 的实现示例，使用标准库 vector 作为容器。核心逻辑与 Python 版本一致，差异在于语法与数据结构。
#include <vector>
#include <algorithm>
using namespace std;void selectionSort(vector<int>& a) {int n = (int)a.size();for (int i = 0; i < n - 1; ++i) {int min_idx = i;for (int j = i + 1; j < n; ++j) {if (a[j] < a[min_idx]) min_idx = j;}if (min_idx != i) std::swap(a[i], a[min_idx]);}
}