前言
选择排序（selection sort）的思路很朴素：每一轮在未排序区间里找到最小元素，与区间首元素交换，然后缩小未排序区间。迭代版本用两层循环即可完成；递归版本则把「对区间[i, n)排序」拆成「把最小值换到i」加「对区间[i+1, n)排序」。本文侧重递归写法本身：递归函数如何设计、调用过程怎样展开、栈深度带来什么代价。
常见的误解有三个。第一，认为「递归版更高级」或「编译器一定会把尾递归优化成循环」。C++ 标准并不要求尾调用优化，是否消除取决于编译器和优化选项，不能作为设计前提。第二，认为递归版的空间复杂度还是O(1)。递归深度为n，栈空间是实打实的O(n)。第三，认为选择排序是稳定排序。用交换实现的选择排序会打乱相等元素的相对顺序，属于不稳定排序。
本文以 C++17 为准，先对照迭代与递归两种形式，再给出完整实现和递归调用树，最后讨论栈深度、尾递归与适用边界。
一、从迭代到递归：同一件事的两种写法
迭代版本：
// 适用于 C++17
void selectionSortIter(std::vector<int>& v) {
const std::size_t n = v.size();
for (std::size_t i = 0; i + 1 < n; ++i) {
std::size_t minIndex = i;
for (std::size_t j = i + 1; j < n; ++j) {
if (v[j] < v[minIndex]) minIndex = j;
}
if (minIndex != i) std::swap(v[i], v[minIndex]);
}
}外层循环的每一轮做两件事：在[i, n)中找最小值下标，把它换到i。递归版本把外层循环换成递归调用，内层扫描保持不变：
selectionSort(v, i):
如果 i 已经是最后一个位置，返回
在 [i, n) 中找到最小值的下标 minIndex
交换 v[i] 与 v[minIndex]
selectionSort(v, i + 1)这里递归承担的是「处理剩余区间」的职责，而不是把内层扫描也递归化。理解这一点很重要：递归深度等于元素个数，每层的工作量是「扫描剩余区间」，总比较次数仍然是(n-1) + (n-2) + ... + 1 = n(n-1)/2，时间复杂度O(n^2)，与迭代版一致。
二、递归函数的设计
递归函数需要两个要素：基准情形和向基准推进。
- 基准情形：区间只剩一个元素（或为空）时，天然有序，直接返回。
- 向基准推进：处理完位置
i后，以i + 1递归，区间长度减一。
用半开区间[begin, n)表示待排序部分，函数签名如下：
// 适用于 C++17
void selectionSort(std::vector<int>& v, std::size_t begin);基准条件写成begin + 1 >= v.size()，覆盖两种情况：begin == v.size()（空区间，虽然正常调用不会出现）和begin == v.size() - 1（只剩一个元素）。如果写成begin == v.size() - 1，空 vector 时v.size() - 1会下溢成极大的size_t，条件永远不成立，随后访问v[begin]就越界了。
推进方式是selectionSort(v, begin + 1)。少了这个+ 1，递归永不收敛，最终栈溢出。
三、完整实现
// 适用于 C++17
#include <cstddef>
#include <iostream>
#include <utility>
#include <vector>
void selectionSort(std::vector<int>& v, std::size_t begin) {
if (begin + 1 >= v.size()) return; // 0 或 1 个元素，已有序
std::size_t minIndex = begin;
for (std::size_t j = begin + 1; j < v.size(); ++j) {
if (v[j] < v[minIndex]) {
minIndex = j;
}
}
if (minIndex != begin) {
std::swap(v[begin], v[minIndex]);
}
selectionSort(v, begin + 1); // 处理剩余区间
}
void selectionSort(std::vector<int>& v) {
selectionSort(v, 0);
}
int main() {
std::vector<int> data{5, 2, 9, 1, 5, 6};
selectionSort(data);
for (int x : data) std::cout << x << ' ';
std::cout << '\n';
return 0;
}按标准语义推演{5, 2, 9, 1, 5, 6}：
begin = 0，区间最小值是 1（下标 3），交换后{1, 2, 9, 5, 5, 6}，递归begin = 1。begin = 1，区间[1, 6)最小值是 2（下标 1），不交换，递归begin = 2。begin = 2，区间[2, 6)最小值是 5（下标 3），交换后{1, 2, 5, 9, 5, 6}，递归begin = 3。begin = 3，区间[3, 6)最小值是 5（下标 4），交换后{1, 2, 5, 5, 9, 6}，递归begin = 4。begin = 4，区间[4, 6)最小值是 6（下标 5），交换后{1, 2, 5, 5, 6, 9}，递归begin = 5。begin = 5，begin + 1 == 6，返回。
结果升序。注意第 3 步到第 4 步之间，两个 5 的相对位置发生了变化：原本下标 3 的 5 被换到了下标 2，原本下标 4 的 5 留在原位。这正是选择排序不稳定的来源。
四、递归调用树、代价与指针区间改写
对长度 5 的数组，调用链是：
sort(0)
└── sort(1)
└── sort(2)
└── sort(3)
└── sort(4) → 返回每一层在递归之前完成一次「找最小值 + 交换」，递归返回后没有额外工作。因此这是尾递归形式：递归调用是函数的最后一条语句。但「尾递归」不等于「尾递归优化」：标准没有强制编译器消除栈帧，GCC、Clang、MSVC 在开启优化时通常会做尾调用消除，但这不是可移植保证。关闭优化或递归调用后面还有析构、清理代码时，栈帧仍会累积。
即便编译器做了尾调用优化，算法本身的比较次数仍是O(n^2)，不会因为递归而变快。递归在这里主要是表达方式，不是性能手段。
栈空间方面，深度为n，每层保存返回地址、参数和局部变量。n达到数万级时，是否超出栈上限取决于平台默认栈大小和链接选项，不能想当然。真实工程里对可能很大的数组应使用迭代版，或显式维护一个栈。
用指针区间改写
如果不想依赖std::vector，可以用指针表示半开区间[first, last)：
// 适用于 C++17
#include <algorithm>
void selectionSort(int* first, int* last) {
if (last - first <= 1) return;
int* smallest = std::min_element(first, last);
std::iter_swap(first, smallest);
selectionSort(first + 1, last);
}std::min_element返回区间内第一个最小元素的迭代器（指针也是迭代器），std::iter_swap交换两个迭代器指向的值。基准条件last - first <= 1同时覆盖空区间和单元素区间。这个版本对原生数组和std::vector的data()都适用，但调用方必须保证[first, last)有效。
常见坑点
1. 基准条件写错
❌if (begin == v.size() - 1) return;，空 vector 时v.size() - 1下溢，条件永不成立。 ✅if (begin + 1 >= v.size()) return;，同时覆盖空区间与单元素。
2. 递归参数没有推进
❌selectionSort(v, begin);，同一区间反复递归，栈溢出。 ✅ 递归调用传begin + 1，保证区间每次缩小。
3. vector 按值传递
❌void selectionSort(std::vector<int> v, std::size_t begin)，每层复制整个数组。 ✅ 传std::vector<int>&，排序结果也才能反映到调用方。
4. 在递归之后才交换
❌ 先selectionSort(v, begin + 1)，再找最小值交换v[begin]，破坏了子区间的有序性。 ✅ 先处理当前位置，再递归处理剩余区间。
5. 忘记处理只剩一个元素的情况
❌ 基准条件写成begin == v.size()，当begin == v.size() - 1时仍进入循环并递归到越界。 ✅ 用begin + 1 >= v.size()提前返回。
6. 认为递归版空间是 O(1)
❌ 宣称「只用了一个临时变量，空间复杂度 O(1)」。 ✅ 递归深度为n，栈空间O(n)；迭代版才是O(1)额外空间。
7. 宣称选择排序稳定
❌ 认为相等元素不会改变相对顺序。 ✅ 交换会跨过相等元素，选择排序不稳定；需要稳定排序用std::stable_sort。
8. 依赖尾递归优化
❌ 用递归处理十万级数组，指望编译器一定把尾调用变成循环。 ✅ 标准不保证尾调用优化；大规模数据改用迭代或显式栈。
总结
| 维度 | 迭代版 | 递归版 |
|---|
| 时间复杂度 | O(n^2) | O(n^2) |
| 额外空间 | O(1) | O(n)栈 |
| 可读性 | 循环直观 | 分治表达清晰 |
| 大数组风险 | 无栈溢出 | 深度大时可能溢出 |
| 稳定性 | 不稳定 | 不稳定 |
递归实现选择排序，价值在于练习「把循环不变量翻译成递归不变量」：区间[i, n)之前已有序，[i, n)待处理。把基准情形、推进方式、处理顺序三处写对，结果就与迭代版一致。至于实际项目，除非明确需要递归表达，排序应优先用标准库的std::sort或std::stable_sort，而不是手写O(n^2)算法。
