前言选择排序selection sort的思路很朴素每一轮在未排序区间里找到最小元素与区间首元素交换然后缩小未排序区间。迭代版本用两层循环即可完成递归版本则把「对区间[i, n)排序」拆成「把最小值换到i」加「对区间[i1, n)排序」。本文侧重递归写法本身递归函数如何设计、调用过程怎样展开、栈深度带来什么代价。常见的误解有三个。第一认为「递归版更高级」或「编译器一定会把尾递归优化成循环」。C 标准并不要求尾调用优化是否消除取决于编译器和优化选项不能作为设计前提。第二认为递归版的空间复杂度还是O(1)。递归深度为n栈空间是实打实的O(n)。第三认为选择排序是稳定排序。用交换实现的选择排序会打乱相等元素的相对顺序属于不稳定排序。本文以 C17 为准先对照迭代与递归两种形式再给出完整实现和递归调用树最后讨论栈深度、尾递归与适用边界。一、从迭代到递归同一件事的两种写法迭代版本// 适用于 C17void selectionSortIter(std::vectorint 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)表示待排序部分函数签名如下// 适用于 C17void selectionSort(std::vectorint 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递归永不收敛最终栈溢出。三、完整实现// 适用于 C17#include cstddef#include iostream#include utility#include vectorvoid selectionSort(std::vectorint 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::vectorint v) {selectionSort(v, 0);}int main() {std::vectorint 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 5begin 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)// 适用于 C17#include algorithmvoid 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::vectorint v, std::size_t begin)每层复制整个数组。 ✅ 传std::vectorint排序结果也才能反映到调用方。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)算法。