插入排序为什么这样写？从腾位置到二分，再到希尔排序

插入排序为什么这样写从腾位置到二分再到希尔排序如果不先背代码直接插入排序其实很好想到先整理好一部分每拿到一个新数就给它找个位置插进去。但“插进去”在数组里怎么实现二分到底省了什么希尔排序每组都用稳定的插入操作为什么整体却不稳定间隔为什么选4、2、1而不是其他数沿着这些问题我们从乱序数组开始最后用程序核对推导。先声明实验边界这里统计元素比较与右移操作不测CPU耗时也不把少量样例的结果当成性能排名。1. 从乱序数组开始而不是从循环开始假设数组是[5, 2, 4, 1, 3]第一个数5自己就已经有序。用竖线区分有序前缀和未处理部分[5 | 2, 4, 1, 3]接下来每次只拿右边的第一个数插入左边插入2[2, 5 | 4, 1, 3] 插入4[2, 4, 5 | 1, 3] 插入1[1, 2, 4, 5 | 3] 插入3[1, 2, 3, 4, 5 | ]不是每次重新排左边而是利用左边已经有序只安置新来的一个数。每轮有序前缀增长一个元素全部处理完就得到了有序数组。2. 数组不能直接塞暂存再腾位置想把3插入[1, 2, 4, 5]一个自然的做法是暂存3把比它大的数从后往前右移再填进空位。temp 3 [1, 2, 4, 5, □] 5右移 [1, 2, 4, □, 5] 4右移 [1, 2, □, 4, 5] 2不大于3停止 [1, 2, 3, 4, 5]空位只是理解模型代码不需要真的清空数组。暂存保证待插入值不会被覆盖从后往前搬保证尚未搬走的元素不被覆盖。void insertion_sort(int a[], int n) { for (int i 1; i n; i) { int temp a[i]; int j i - 1; while (j 0 a[j] temp) { a[j 1] a[j]; j--; } a[j 1] temp; } }为什么填入j1停止时j指向不大于temp的元素应该插在它后面。如果一路搬到头j-1仍然填入j10。j0是边界判断a[j]temp才是元素大小比较。C的从左到右短路求值必须先确认下标合法再访问元素。本实现约定n非负n大于0时a指向至少n个可写元素。3. 严格大于不只是一种写法给两个相等的元素加身份标记[3甲, 3乙, 2] → [2, 3甲, 3乙]插入3乙时3甲并不严格大于它因此不搬。相等元素保持原相对顺序这就是稳定。若改成插入3乙时会搬走3甲得到[3乙, 3甲]。数值仍有序身份顺序却变了。有序和稳定是两件事。直接插入属于比较排序它通过元素之间的大小比较决定位置。利用数值作为计数数组下标是另一条路线本文先不展开。4. 把成本拆开找位置和腾位置如果数组已经有序每个新数只需和前一个比较就停止[1, 2, 3, 4, 5]4次元素比较0次右移若完全逆序待插入元素元素比较右移411322233144合计1010长度n的逆序数组需要12...(n-1)n(n-1)/2次右移。最好时间O(n)最坏O(n²)额外空间O(1)。这里的0次右移不等于0次赋值代码仍执行暂存与最后写回。更精确地说直接插入的右移总数等于原数组的逆序对数量。逆序对是下标i小于j却有a[i]a[j]的一对元素不包括相等值。插入当前元素时每个比它大的前驱都必须右移一次恰好对应以当前元素为右端点的逆序对。遍历所有元素就把全部逆序对各数了一次。这不是“数值相差越大越费劲”而是“需要越过多少个前驱”。5. 折半插入有序前缀不该白白浪费待插入3左边已经是[1, 2, 4, 5, 7, 8, 9]为什么还必须逐个找位置可以二分看中间值排除一半候选位置再继续。但稳定版本找的不是任意一个相等元素而是第一个严格大于temp的位置。例如[1, 3甲, 3乙, 5]中新来的3丙应放在3乙后、5前。下面使用左闭右开的搜索区间[left,right)初始righti位置i也可能是最终答案表示无需右移。int left 0, right i; while (left right) { int mid left (right - left) / 2; if (a[mid] temp) right mid; else left mid 1; } for (int j i; j left; j--) a[j] a[j - 1]; a[left] temp;这段替换直接插入每轮的查找、搬移部分即可i和temp沿用外层循环。相等时向右找才不会越过已有的相等元素。二分减少搜索位置的比较没有减少必须右移的元素数。最坏整体时间仍O(n²)额外空间O(1)。而且本文不加“已在末尾就跳过二分”的提前判断有序输入时原版每轮只比较一次无条件二分反而可能比较更多。优化要明确数据条件不能只看算法名字。6. 希尔排序先跨大步整理即使瞬间知道1该放最前面[2,3,4,5,6|1]还是要搬走前面的五个数。能不能让偏后的小数提前向前跨几步让最后的插入更轻松看这个例子下标 0 1 2 3 4 5 6 7 原值[9, 2, 3, 4, 5, 6, 7, 1]间隔4原位置上的四组分别是0 → 4[9,5] → [5,9] 1 → 5[2,6] → 不变 2 → 6[3,7] → 不变 3 → 7[4,1] → [1,4]写回原位置得到[5,2,3,1,9,6,7,4]。不是前面四个数都小于后面四个数只保证a[0]a[4]等对应关系。也不用开新数组组只是访问下标的规则。间隔2把两条完整的链分别排好0 → 2 → 4 → 6[5,3,9,7] → [3,5,7,9] 1 → 3 → 5 → 7[2,1,6,4] → [1,2,4,6] 写回[3,1,5,2,7,4,9,6]比如原来0和4有序现在要把0、2、4、6整条链排好前一轮不会自动排好这一轮但提供了整理过的起点。这里4是2的倍数小间隔链包含原来的大间隔链不要把这一分组关系套到所有增量序列上。最后间隔1所有元素同组直接插入后得到[1,2,3,4,5,6,7,9]。大间隔调整也有成本不能只数最后一轮就宣称更快。下面是完整整数版希尔排序供理解循环void shell_sort(int a[], int n) { for (int gap n / 2; gap 0; gap / 2) { for (int i gap; i n; i) { int temp a[i]; int j i - gap; while (j 0 a[j] temp) { a[j gap] a[j]; j - gap; } a[j gap] temp; } } }i仍然每次加1是让不同组交替处理j每次减gap保证当前插入只访问同一组。gap1时代码正是直接插入。希尔排序属于插入排序类但不是直接插入排序中间轮次只维护各组有序不维护整个连续前缀有序。7. 组内稳定保护不到另一组只需四个元素就能验证整体不稳定原数组[2甲, 2乙, 1, 3] gap2 下标0、2[2甲,1] → [1,2甲] 下标1、3[2乙,3] → 不变 写回[1, 2乙, 2甲, 3]2甲为了给1腾位置跨过另一组的2乙根本没和它比较。gap1时两个2相等不再搬无法恢复原身份顺序。因此严格大于只能保护本组的相等顺序不能保证全局稳定。这也是验证时不能只检查最终数值有序的原因。8. 间隔怎么选公式、理论和实验都有但不是万能口诀先分清正确性与效率。本文使用正整数间隔逐渐缩小并以1结束。最后完整做一次间隔1的插入就能保证排序正确只有[4,2]不够奇偶下标两组可能仍交错无序。两种容易落地的选择选择生成方法用途与边界每次减半从n/2开始整数除2直到1便于理解不能保证高性能最坏仍可能O(n²)Knuth序列从1开始反复h3h1排序时从大到小使用例如1、4、13、40、121有理论分析但不表示每种输入都胜过减半Knuth的生成规则及具体实现可对照普林斯顿的Shell源码。该资料给出了这一实现的最坏O(n^(3/2))界不能把它当成所有希尔排序的统一复杂度。减半序列的问题可以亲自构造。当n是2的幂时最后的1之前间隔都是偶数。偶数下标只和偶数下标整理奇数下标只和奇数下标整理[64,0,65,1,66,2,...,127,63]每个偶数间隔组已经有序前几轮没有右移两种下标之间却有大量逆序对只能留到最后一轮处理。不是“减半不能排序”而是“前面的整理可能没有解决这一输入的主要错位”。所以间隔并非只靠随手选也不是套一个公式就找到最优有便于实现的规则、有带理论界的构造也可以对目标数据做实验选择。只试一种随机数组、只统计最后一轮或只看到某篇文章里的时间表都不足以认定某个序列普遍最好。基础排序课程资料也将增量选择和具体界联系起来而非给希尔排序一个通用耗时公式。9. 验证程序为什么这样设计验证对象分成两层。整数版检查数值顺序带身份的Item版只按key比较整个记录一起搬id保存原下标不参与排序决策。如果把id也加入比较相当于人为加入了第二排序键会遮住我们想观察的不稳定现象。这里qsort仅生成正确的数值序列不用它判定稳定性。四个Item实现直接插入、折半插入、减半希尔、Knuth希尔。统一统计comparisons实际执行的两个key的大小比较包括导致停止的那次不包括下标检查。shifts较大记录右移一次算一次希尔跨gap搬一次也只算一次。暂存与最后填入不计入shifts所以这个数不等于全部赋值次数、移动距离或运行时间。每个用例同时检查输出等于参考数值序列原id无丢失、无重复key与id对应关系未损坏。直接、折半还必须保持稳定并且右移数等于暴力计算的原始逆序对数。测试包括长度0至7、值域{-1,0,1}的全部数组固定种子的1000组随机数组部分包含INT_MIN/INT_MAX有序、逆序、教学例子和奇偶对抗输入。独立暴力逆序对计数器故意保持简单不复用待测算法。失败对照也要测把直接插入的条件改成身份检查必须拒绝它希尔的四元素例子必须真的得到[1,2乙,2甲,3]。这些检查通过表示验证器抓住了预设错误不等于证明所有未来修改正确。本轮实际环境Windows x64MinGW GCC 13.1.0C11-Wall -Wextra -Werror -O2。4285个输入用例通过四个Item实现、正文直接整数版和希尔整数版均核对正确输出。断言开启随机种子固定为20261005。Ubuntu运行尝试因缺少GCC未完成本轮没有sanitizer检查。输入实现元素比较右移原逆序对sorted5direct400sorted5binary600sorted5shell_half700sorted5shell_knuth400reversed5direct101010reversed5binary81010reversed5shell_half8410reversed5shell_knuth101010example8direct181313example8binary161313example8shell_half251313example8shell_knuth201313parity128direct220620802080parity128binary64920802080parity128shell_half284820802080parity128shell_knuth8333842080random128direct409439713971random128binary72539713971random128shell_half12565493971random128shell_knuth10676583971example8是前面的8元素教学数组parity128是奇偶错位输入random128是完整测试流程之后继续取样的固定种子数组。完整程序可重现这些计数表格不是墙钟时间。三个值得保留的观察有序5元素时二分比直接插入多比较两次教学8元素中减半希尔右移与直接插入相同比较还更多奇偶输入中减半的2080次右移全留到gap1而Knuth共384次右移。单个随机样例里Knuth比较更少却右移更多连“少比较”和“少搬移”也未必同时发生。稳定性负例和三轮中间数组也已核对不只是看最终排序结果trace gap4: 5 2 3 1 9 6 7 4 trace gap2: 3 1 5 2 7 4 9 6 trace gap1: 1 2 3 4 5 6 7 9 mutation : rejected; shell counterexample: 1,2B,2A,3 PASS cases4285; methods4; plain_integer_sortchecked10. 回到这条思考路线先理解怎样保持有序再理解怎样在数组里腾位置。然后拆开比较与搬移二分让找位置更省希尔改变整理顺序允许提前跨步调整却失去稳定性效果也依赖间隔。这不是背三个名字而是问清现在正确的做法哪部分贵修改后省了什么又失去了什么附录可复现的完整验证源码下面的sorts.h与verify.c一起保存到同一目录。C11编译测试上限为256个元素这是验证程序的容量限制不是排序算法只能处理256个元素。不要添加-DNDEBUG测试使用assert关闭断言会使检查失效。gcc -stdc11 -Wall -Wextra -Werror -O1 -g \ -fsanitizeaddress,undefined verify.c -o verify ./verify不支持上述sanitizer的编译器可去掉该选项但那次运行便不能声称做了sanitizer检查。sorts.h#ifndef SORTS_H #define SORTS_H #include stdint.h typedef struct { int key; int id; } Item; typedef struct { uint64_t comparisons; uint64_t shifts; } Stats; static void insertion_sort(int a[], int n) { for (int i 1; i n; i) { int temp a[i]; int j i - 1; while (j 0 a[j] temp) { a[j 1] a[j]; j--; } a[j 1] temp; } } static void direct(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; j--; } a[j 1] temp; } } static void binary_insertion(Item a[], int n, Stats *s) { for (int i 1; i n; i) { Item temp a[i]; int left 0, right i; // [left, right): find the first key strictly greater than temp.key. while (left right) { int mid left (right - left) / 2; s-comparisons; if (a[mid].key temp.key) right mid; else left mid 1; } for (int j i; j left; j--) { a[j] a[j - 1]; s-shifts; } a[left] temp; } } static void gap_pass(Item a[], int n, int gap, Stats *s) { for (int i gap; i n; i) { Item temp a[i]; int j i - gap; while (j 0) { s-comparisons; if (!(a[j].key temp.key)) break; a[j gap] a[j]; s-shifts; j - gap; } a[j gap] temp; } } static void shell_half(Item a[], int n, Stats *s) { for (int gap n / 2; gap 0; gap / 2) gap_pass(a, n, gap, s); } static void shell_knuth(Item a[], int n, Stats *s) { if (n 2) return; int gap 1; while (gap n / 3) gap 3 * gap 1; for (; gap 0; gap / 3) gap_pass(a, n, gap, s); } #endifverify.c#include sorts.h #include assert.h #include limits.h #include stdio.h #include stdlib.h #include string.h enum { CAP 256 }; typedef void (*Sort)(Item *, int, Stats *); static Sort methods[] {direct, binary_insertion, shell_half, shell_knuth}; static const char *names[] {direct, binary, shell_half, shell_knuth}; static unsigned cases; static uint32_t state 20261005u; static uint32_t next_random(void) { state ^ state 13; state ^ state 17; state ^ state 5; return state; } 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 uint64_t inversions(const int a[], int n) { uint64_t total 0; for (int i 0; i n; i) for (int j i 1; j n; j) total a[i] a[j]; return total; } 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 void check(const int input[], int n, const char *label) { int expected[CAP], plain[CAP]; assert(n 0 n 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); insertion_sort(plain, n); assert(memcmp(plain, expected, (size_t)n * sizeof(int)) 0); uint64_t inv inversions(input, n); for (int method 0; method 4; method) { Item a[CAP]; int seen[CAP] {0}; for (int i 0; i n; i) a[i] (Item){input[i], i}; Stats s {0}; methods[method](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 2) { assert(stable(a, n)); assert(s.shifts inv); } if (label) printf(%s,%s,%d,%llu,%llu,%llu\n, label, names[method], n, (unsigned long long)s.comparisons, (unsigned long long)s.shifts, (unsigned long long)inv); } cases; } static void mutation_and_counterexample(void) { Item bad[] {{2, 0}, {2, 1}}; Item temp bad[1]; int j 0; while (j 0 bad[j].key temp.key) { bad[j 1] bad[j]; j--; } bad[j 1] temp; assert(!stable(bad, 2)); Item a[] {{2, 0}, {2, 1}, {1, 2}, {3, 3}}; Stats s {0}; shell_half(a, 4, s); assert(a[0].key 1 a[1].id 1 a[2].id 0 a[3].key 3); assert(!stable(a, 4)); puts(mutation : rejected; shell counterexample: 1,2B,2A,3); } int main(void) { puts(case,method,n,comparisons,shifts,inversions); int a[CAP] {0}; 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 example[] {9,2,3,4,5,6,7,1}; check(sorted, 5, sorted5); check(reversed, 5, reversed5); check(example, 8, example8); for (int i 0; i 128; i) a[i] i % 2 ? i / 2 : 64 i / 2; check(a, 128, parity128); for (int i 0; i 128; i) a[i] (int)(next_random() % 101) - 50; check(a, 128, random128); Item trace[8]; for (int i 0; i 8; i) trace[i] (Item){example[i], i}; for (int gap 4; gap 0; gap / 2) { Stats s {0}; gap_pass(trace, 8, gap, s); printf(trace gap%d:, gap); for (int i 0; i 8; i) printf( %d, trace[i].key); puts(); } mutation_and_counterexample(); printf(PASS cases%u; methods4; plain_integer_sortchecked\n, cases); return 0; }