简单选择排序：交换很少，为什么还是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. 把“先选后放”翻译成Cvoid 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。没有额外信息所有剩余候选都要看。轮次未排序元素数元素比较数第1轮nn-1第2轮n-1n-2最后一轮21每轮先把当前位置作为候选剩余每个元素比较一次因此总比较数是(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}只比较keyid记录原始下标。搬移或交换整个记录才能检查是否丢失、重复、身份与数值错配。验证器检查三件不同的事输出数值是否与独立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甲]故意让内层从i2开始跳过相邻候选必须在[2,1]上被拒绝。已知故障能被抓住才有理由相信检查不是摆设有限测试仍不等于一般正确性证明。本轮Windows x64、MinGW GCC 13.1.0、C11、-Wall -Wextra -Werror -O2实测断言开启4285个输入通过。没有sanitizer或CPU耗时测量。输入实现比较交换右移数组写入sorted5selection10000sorted5insertion4004reversed5selection10204reversed5insertion1001014equal5selection10000equal5insertion4004example5selection10306example5insertion90711unstable3selection3102unstable3insertion3024sorted5为[1,2,3,4,5]reversed5为[5,4,3,2,1]equal5为五个2example5为本文的[5,2,4,1,3]unstable3为[2甲,2乙,1]的数值部分。id在验证器内部保留。有序和全相等输入中选择比较始终是10次却没有数组写入。逆序输入中选择两次交换、四次数组写入插入十次右移加四次最终填入共十四次数组写入。比较计数固定与交换数随输入变化可以同时成立。负例也得到预期结果strict : still unstable; result1,2B,2A mutation ji2: rejected on [2,1] PASS cases4285; selection, insertion, plain_selection checked8. 从这里继续优化该问什么现在的主要成本已经清楚反复找最小值。每轮删掉一个最小元素却把之前的比较关系全忘了下一轮从头再挑。下一步可以问能不能保存一些比较结果拿走最小值后只修复受到影响的部分这会引向堆或胜者树等结构属于新的算法设计不是把循环下标改一下就消除了平方级扫描。如果数据已经大致有序直接插入可能更合适如果比较相对便宜、移动记录相对昂贵选择的少交换特点值得考虑但要结合记录大小、比较成本和真实计时而不是只凭复杂度表选实现。这里是在解释成本取舍不建议用教学实现替代成熟排序库。两篇文章的分工也由此明确前一篇讲找位置与跨步整理这一篇讲先选后放并追问为什么少交换仍不能代表低时间成本。附录完整程序与复现方法下面程序保存为verify.c即可编译包含前面的整数排序、带身份的选择与插入、用例生成器、计数断言和失败对照。容量256只是本验证程序的限制。不要加-DNDEBUG否则assert检查会被关闭。gcc -stdc11 -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; result1,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 ji2: 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; }