简单选择排序：交换很少，为什么还是O(n²)？

简单选择排序：交换很少，为什么还是O(n²)？

直接插入排序拿到一个数，会问：它应该插在哪里？简单选择排序换了一个问题：这个位置应该放哪个数？

这个区别不只是名字。5个元素已经有序时，本文的选择排序仍比较10次，插入只比较4次；完全逆序时，选择只交换2次，插入却要右移10次。

为什么搬得少，时间复杂度还是平方级？我们从原始数组推导，再用程序核对。本文讨论的是每轮选择最小值、最后至多交换一次的经典实现，不把它的结论套到所有选择排序变体。

1. 先确定位置，再去挑数

从乱序数组开始：

[5, 2, 4, 1, 3]

第一个位置应该放整个数组的最小值。先扫描，记住最小值在哪里，扫描过程中不搬元素：

暂定最小：5，下标0 遇到2：改为2，下标1 遇到4：不变 遇到1：改为1，下标3 遇到3：不变

最后才把下标0与3的元素交换：

[1 | 2, 4, 5, 3]

为什么可以不再管1？因为没有剩余元素比它小，它已经处在一个正确的最终位置。后面的轮次只扫描竖线右边。

从[2,4,5,3]选2：已在当前位置，不交换 [1, 2 | 4, 5, 3] 从[4,5,3]选3：与4交换 [1, 2, 3 | 5, 4] 从[5,4]选4：与5交换 [1, 2, 3, 4 | 5]

只剩一个元素时，不用继续挑。这就是“选择”：每轮确定一个位置，选出应该放在那里的元素。

2. 左边都有序，为什么不是同一种思想？

直接插入也维护有序的左边，但有序的含义不同：

插入：[2, 5 | 4, 1, 3] 2和5只是已处理部分有序，后来遇到1，还得搬。 选择：[1, 2 | 4, 5, 3] 1和2已经是全数组最小的两个数，后面不会再动它们。

插入是给数找位置；选择是给位置找数。有序前缀相似，建立它的方式、知道的信息、下一轮的任务却不同。

3. 把“先选后放”翻译成C

void selection_sort(int a[], int n) { for (int i = 0; i < n - 1; i++) { int min_index = i; for (int j = i + 1; j < n; j++) { if (a[j] < a[min_index]) min_index = j; } if (min_index != i) { int temp = a[i]; a[i] = a[min_index]; a[min_index] = temp; } } }

外层i是这轮要填的位置；min_index暂存最小值的下标。内层只更新下标，不一发现较小值就交换。扫描结束后才交换。

如果最小值已经在i，跳过自交换；这会减少写入，却不会减少内层比较。本实现要求n非负，n大于0时a指向至少n个可写元素；长度0或1不进入循环。不要直接改成无符号n后仍照抄n-1，空数组时减法会下溢。

比较使用<而不是相减，避免把INT_MIN与INT_MAX相减造成有符号溢出。求元素个数、容量与大数组计数时，也要注意类型范围；下面验证器的计数使用uint64_t。

4. 少搬了，但比较并没消失

插入排序会为一个数腾位置，可能连续右移一串元素。选择排序先挑最小值，最后交换两个位置，不需要逐个腾位置。

但“我已经找到最小值”必须有依据。扫描[5,2,4,1,3]时，遇到2也不能停：后面可能有1。没有额外信息，所有剩余候选都要看。

每轮先把当前位置作为候选，剩余每个元素比较一次，因此总比较数是：

(n-1) + (n-2) + ... + 1 = n(n-1)/2

最后至多交换一次，每轮一个，合计至多n-1次交换；并非一定交换n-1次。逆序5元素时，中间的3本来就在最终位置，实际只交换两次。

所以不能只看交换很少，就说时间O(n)。计算总时间，要把内层寻找最小值的成本也算进去。

5. 为什么已经有序也要扫描？

看到[1,2,3,4,5]，人知道它已经有序，但程序不能凭感觉知道。第一轮仍要确认没有元素比1小，第二轮确认剩余没有元素比2小。

这个经典实现的比较次数不依赖初始排列，最好、平均、最坏时间都是Θ(n²)，额外空间O(1)。数据只影响交换次数，不能让固定的扫描消失。

直接插入却能利用已有的有序前缀：新元素不小于前缀最大值时，只比较一次就能停。最好Θ(n)，最坏Θ(n²)；在互异元素的各个排列等概率出现的模型下，平均Θ(n²)。但乱序不等于每次都最坏，实际右移数由逆序对数决定。

这不是说“任何选择类算法都不能检测有序”。额外加有序检测会改变实现与最好情况，这篇不偷偷加上它，再拿新结果冒充原来的算法。

6. 严格小于，为什么还是不稳定？

前一篇插入排序用严格大于，避免新元素越过前面相等的元素。选择用严格小于，遇到相同最小值时保留先遇到的候选，看起来也很谨慎。

但破坏稳定的地方不是挑选相等的最小值，而是最终交换：

下标： 0 1 2 原值：[2甲, 2乙, 1] 最小 交换下标0、2 结果：[1, 2乙, 2甲]

2甲被换到末尾，越过了2乙。第二轮两个2相等，不再交换，也无法恢复顺序。所以严格比较并不是所有排序都稳定的通用条件，要看整个移动过程。

想让这条思路稳定，可以取出最小元素，把它前面的未排序元素整体右移，再填到当前位置。其他记录的顺序就保住了；但这又增加了搬移，已经不是本文的少交换实现。

7. 验证器不只检查最终有序

整数版排序与带身份版本都参与验证。记录类型为{key,id}，只比较key，id记录原始下标。搬移或交换整个记录，才能检查是否丢失、重复、身份与数值错配。

验证器检查三件不同的事：

• 输出数值是否与独立qsort参考一致。参考比较器用关系判断，不用整数相减。
• 元素是否完整保留。不能只检查有序，否则[1,1,1]也可能蒙混过关。
• 比较数是否恰好n(n-1)/2，实际交换是否不超过n-1。插入对照还必须保持相等记录的原顺序。

qsort只作为数值序列的参考，不拿它判断稳定性；它自己的稳定性没有作为前提。也不把id加进排序键，否则会遮住我们想观察的不稳定。

统一计数口径：comparisons只数元素大小比较；swaps只数不同下标之间的交换；shifts是插入的右移次数；array_writes数源码中对数组槽位的赋值。一交换有两次数组写入，另有一次暂存变量赋值，后者不算数组写入。

数组写入计数是算法层面的口径，不等于CPU实际存储指令、缓存行为或物理设备写入量。本轮没有计时，不能把这些次数直接换成“快了几倍”。

测试覆盖长度0至7、值域{-1,0,1}的全部3280个数组；固定种子1000组随机输入，部分包含INT_MIN、INT_MAX；以及5个定向样例。

失败对照包括：严格<的选择确实把[2甲,2乙,1]排成[1,2乙,2甲]；故意让内层从i+2开始，跳过相邻候选，必须在[2,1]上被拒绝。已知故障能被抓住，才有理由相信检查不是摆设；有限测试仍不等于一般正确性证明。

本轮Windows x64、MinGW GCC 13.1.0、C11、-Wall -Wextra -Werror -O2实测，断言开启，4285个输入通过。没有sanitizer或CPU耗时测量。

sorted5为[1,2,3,4,5]，reversed5为[5,4,3,2,1]，equal5为五个2，example5为本文的[5,2,4,1,3]，unstable3为[2甲,2乙,1]的数值部分。id在验证器内部保留。

有序和全相等输入中，选择比较始终是10次，却没有数组写入。逆序输入中选择两次交换、四次数组写入；插入十次右移，加四次最终填入，共十四次数组写入。比较计数固定，与交换数随输入变化，可以同时成立。

负例也得到预期结果：

strict <: still unstable; result=1,2B,2A mutation j=i+2: rejected on [2,1] PASS cases=4285; selection, insertion, plain_selection checked

8. 从这里继续优化，该问什么？

现在的主要成本已经清楚：反复找最小值。每轮删掉一个最小元素，却把之前的比较关系全忘了，下一轮从头再挑。

下一步可以问：能不能保存一些比较结果，拿走最小值后只修复受到影响的部分？这会引向堆或胜者树等结构，属于新的算法设计，不是把循环下标改一下就消除了平方级扫描。

如果数据已经大致有序，直接插入可能更合适；如果比较相对便宜、移动记录相对昂贵，选择的少交换特点值得考虑，但要结合记录大小、比较成本和真实计时，而不是只凭复杂度表选实现。这里是在解释成本取舍，不建议用教学实现替代成熟排序库。

两篇文章的分工也由此明确：前一篇讲找位置与跨步整理；这一篇讲先选后放，并追问为什么少交换仍不能代表低时间成本。

附录：完整程序与复现方法

下面程序保存为verify.c即可编译，包含前面的整数排序、带身份的选择与插入、用例生成器、计数断言和失败对照。容量256只是本验证程序的限制。不要加-DNDEBUG，否则assert检查会被关闭。

gcc -std=c11 -Wall -Wextra -Werror -O2 verify.c -o verify ./verify

#include <assert.h> #include <limits.h> #include <stdint.h> #include <stdio.h> #include <stdlib.h> #include <string.h> void selection_sort(int a[], int n) { for (int i = 0; i < n - 1; i++) { int min_index = i; for (int j = i + 1; j < n; j++) { if (a[j] < a[min_index]) min_index = j; } if (min_index != i) { int temp = a[i]; a[i] = a[min_index]; a[min_index] = temp; } } } typedef struct { int key; int id; } Item; typedef struct { uint64_t comparisons, swaps, shifts, writes; } Stats; enum { CAP = 256 }; static unsigned cases; static uint32_t random_state = 20261005u; static void select_items(Item a[], int n, Stats *s) { for (int i = 0; i < n - 1; i++) { int min_index = i; for (int j = i + 1; j < n; j++) { s->comparisons++; if (a[j].key < a[min_index].key) min_index = j; } if (min_index != i) { Item temp = a[i]; a[i] = a[min_index]; a[min_index] = temp; s->swaps++; s->writes += 2; } } } static void insert_items(Item a[], int n, Stats *s) { for (int i = 1; i < n; i++) { Item temp = a[i]; int j = i - 1; while (j >= 0) { s->comparisons++; if (!(a[j].key > temp.key)) break; a[j + 1] = a[j]; s->shifts++; s->writes++; j--; } a[j + 1] = temp; s->writes++; } } static int compare_int(const void *p, const void *q) { int a = *(const int *)p, b = *(const int *)q; return (a > b) - (a < b); } static int stable(const Item a[], int n) { for (int i = 1; i < n; i++) if (a[i - 1].key == a[i].key && a[i - 1].id > a[i].id) return 0; return 1; } static uint32_t next_random(void) { random_state ^= random_state << 13; random_state ^= random_state >> 17; random_state ^= random_state << 5; return random_state; } static void check(const int input[], int n, const char *label) { assert(n >= 0 && n <= CAP); int expected[CAP], plain[CAP]; memcpy(expected, input, (size_t)n * sizeof(int)); memcpy(plain, input, (size_t)n * sizeof(int)); qsort(expected, (size_t)n, sizeof(int), compare_int); selection_sort(plain, n); assert(memcmp(plain, expected, (size_t)n * sizeof(int)) == 0); for (int method = 0; method < 2; method++) { Item a[CAP]; int seen[CAP] = {0}; Stats s = {0}; for (int i = 0; i < n; i++) a[i] = (Item){input[i], i}; if (method == 0) select_items(a, n, &s); else insert_items(a, n, &s); for (int i = 0; i < n; i++) { assert(a[i].key == expected[i]); assert(a[i].id >= 0 && a[i].id < n); assert(!seen[a[i].id]++); assert(a[i].key == input[a[i].id]); } if (method == 0) { uint64_t count = n < 2 ? 0 : (uint64_t)n * (uint64_t)(n - 1) / 2; assert(s.comparisons == count); assert(s.swaps <= (uint64_t)(n > 0 ? n - 1 : 0)); assert(s.writes == 2 * s.swaps); } else { assert(stable(a, n)); assert(s.writes == s.shifts + (uint64_t)(n > 0 ? n - 1 : 0)); } if (label) printf("%s,%s,%d,%llu,%llu,%llu,%llu\n", label, method == 0 ? "selection" : "insertion", n, (unsigned long long)s.comparisons, (unsigned long long)s.swaps, (unsigned long long)s.shifts, (unsigned long long)s.writes); } cases++; } static void negative_controls(void) { Item a[] = {{2, 0}, {2, 1}, {1, 2}}; Stats s = {0}; select_items(a, 3, &s); assert(a[0].key == 1 && a[1].id == 1 && a[2].id == 0); assert(!stable(a, 3)); puts("strict <: still unstable; result=1,2B,2A"); // Deliberately skip the adjacent candidate: the two-item test must reject it. int bad[] = {2, 1}; for (int i = 0; i < 1; i++) { int min_index = i; for (int j = i + 2; j < 2; j++) if (bad[j] < bad[min_index]) min_index = j; int temp = bad[i]; bad[i] = bad[min_index]; bad[min_index] = temp; } assert(bad[0] > bad[1]); puts("mutation j=i+2: rejected on [2,1]"); } int main(void) { int a[CAP] = {0}; puts("case,method,n,comparisons,swaps,shifts,array_writes"); for (int n = 0; n <= 7; n++) { int combinations = 1; for (int i = 0; i < n; i++) combinations *= 3; for (int code = 0; code < combinations; code++) { int rest = code; for (int i = 0; i < n; i++) { a[i] = rest % 3 - 1; rest /= 3; } check(a, n, NULL); } } for (int trial = 0; trial < 1000; trial++) { int n = (int)(next_random() % (CAP + 1)); for (int i = 0; i < n; i++) a[i] = (int)(next_random() % 101) - 50; if (n > 0 && trial % 10 == 0) a[0] = INT_MIN; if (n > 1 && trial % 10 == 0) a[1] = INT_MAX; check(a, n, NULL); } const int sorted[] = {1, 2, 3, 4, 5}; const int reversed[] = {5, 4, 3, 2, 1}; const int equal[] = {2, 2, 2, 2, 2}; const int example[] = {5, 2, 4, 1, 3}; const int unstable[] = {2, 2, 1}; check(sorted, 5, "sorted5"); check(reversed, 5, "reversed5"); check(equal, 5, "equal5"); check(example, 5, "example5"); check(unstable, 3, "unstable3"); negative_controls(); printf("PASS cases=%u; selection, insertion, plain_selection checked\n", cases); return 0; }