希尔排序让插入排序不再怕逆序一个算法的短板通常是下一个算法的问题意识。为什么需要上一篇把直接插入排序的三种情况摊开了最好 O(N)、最坏 O(N²)、平均介于两者之间。它的表现取决于输入数据的逆序程度——数据越接近有序它就快得越像 O(N)。那么它的死穴也就很清楚了一旦数据是逆序的效率立刻掉下来。逆序时每个元素都要从当前位置一路挪到最前面挪动的步数分别是 n、n−1、n−2……累加就是 O(N²)。而且这些挪动全是一格一格走的——一个本该在数组末尾的大数要跟前面每个数比较一次、后移一次才能到位。于是问题变成了既然插入排序在有秩序的数据上快得惊人能不能先花点力气把数据变得接近有序再交给它收尾希尔排序Shell Sort就是这个思路。它是对直接插入排序的优化做法很简单先分组、每组内部插入排序让整个数组接近有序最后再走一趟完整的插入排序。一个自然的质疑是多干了活凭什么更快如果预排序的代价和收益差不多那这个算法就没有意义。这一点留到实测部分用数据回答。核心机制分组、跳着走希尔排序的做法是把数据按间隔 gap 分成若干组组内做插入排序。假设gap 3那么下标 0、3、6、9…… 的元素是一组1、4、7…… 是第二组2、5、8…… 是第三组。分组是逻辑上的——不需要真的把这些元素搬到新数组里只靠循环的步长控制把它们看成一组。gap 3 时逻辑分组 组1: a[0] a[3] a[6] a[9] ... 组2: a[1] a[4] a[7] ... 组3: a[2] a[5] a[8] ...分好组之后对每一组分别做插入排序。注意这里的插入排序和上一篇几乎一样唯一的区别是前一个元素不是end - 1而是end - gap。所以整段逻辑可以这样描述把a[end gap]插进同组中它前面的那些元素里其他元素整体后移 gap 格。这样做的效果用一个逆序数组最直观一个本来在数组开头的大数以前每次只能往右挪一格要挪 n 次现在每次跳 gap 格几步就跳到后面去了。反过来对小元素同样成立它本来要一格一格往左蹭现在几步就跳到前面。所以预排序同时在做两件事——大的更快到后面小的更快到前面一举两得。而gap越大跳跃跨度越大调整得越猛。这是希尔排序最反直觉的一点单趟预排序并不追求排好它追求的是让数据整体形状变好。一趟预排序结束后数组通常并不是有序的只是比之前更接近有序大的数更靠后小的数更靠前逆序对数量大幅减少。然后缩小 gap 再来一趟再缩小再来一趟……直到gap 1。gap 1时“间隔为 1 的元素为一组”——所有元素都在同一组里这时的插入排序就是完整的直接插入排序。也就是说希尔排序的最后一趟并不是另外调一次 InsertSort而是循环自然走到的那一步。由此也能看出gap 1时的预排序代码和上一篇的直接插入排序是同一段代码。上一篇写的那个插入排序就是希尔排序在 gap 取 1 时的特例。整个算法用一个循环把预排序和最终排序统一了。代码演示第一步写出一组的插入排序先别管所有组把一组排好。和上一篇对比着看只有1变成了gap// 排一组gap 是该组的步长end 是组内有序区的末尾intendi;inttmpa[endgap];// 同组中的后一个元素while(end0){if(tmpa[end]){a[endgap]a[end];// 元素整体后移 gap 格end-gap;}else{break;}}a[endgap]tmp;// 位置定了落位结构完全没变先存 tmp、从后往前扫、循环外统一落位。变的只是步长。第二步三层循环——一组一组排有了排一组的逻辑最朴素的扩展是外面再套一层枚举每一组。// 一组一组排gap 固定为 3 的示意版本voidShellSort_ByGroup(int*a,intn){intgap3;for(intj0;jgap;j)// 第 j 组{for(size_tij;in-gap;igap)// 组内的有序区末尾{intendi;inttmpa[endgap];while(end0){if(tmpa[end]){a[endgap]a[end];end-gap;}else{break;}}a[endgap]tmp;}}}j的作用是告诉程序现在排第几组j 0排第一组、j 1排第二组……一组排完了再排下一组。这里i n - gap是必须的不能写成i n。理由和上一篇的越界陷阱是同一类但更容易踩这一趟要读的是a[end gap]如果i走到了n - gapend gap就等于n——越界。所以组内循环的末尾必须停在n - gap - 1也就是条件写i n - gap。第三步两层循环——多组并着走三层循环能跑通但可以合并成两层不把一组排完再排下一组而是几组轮流各推进一步。// 多组并着走 gap 逐趟缩小voidShellSort(int*a,intn){intgapn;while(gap1){// 1 保证最后一趟 gap 一定等于 1// gap 1 时是预排序gap 1 时就是直接插入排序gapgap/31;for(size_ti0;in-gap;i)// 注意这里是 i不是 gap{intendi;inttmpa[endgap];while(end0){if(tmpa[end]){a[endgap]a[end];end-gap;}else{break;}}a[endgap]tmp;}}}改动只有两处外层控制内层步进效果三层写法j gap枚举组号i gap一组排完再排下一组两层写法不需要i几组齐头并进交替推进i的语义是处理完a[i]这个位置下一个处理a[i 1]——它属于下一组。于是循环自动在几组之间轮转而循环边界i n - gap对每一组都成立。两种写法效率完全一样。三层循环跑的次数和两层循环一样多只是组织顺序不同。这一点很重要——它正面推翻了循环层数多就慢的直觉。gap gap / 3 1是 gap 的缩小策略。/ 3让跨度迅速收敛 1保证它最终一定会落到 1——如果没有这个1gap会停在 2、再变成 0永远等不到 gap 1 的那一趟最终排序数组就不会被真正排好。 背景补充size_t是无符号类型i n - gap中右边的int会转换成无符号再比较。这里n - gap恒非负gap 最大为 n所以是安全的但如果循环边界表达式可能为负无符号比较会把负数变成极大的正数导致循环失控——这是 C 语言里典型的隐性陷阱。复杂度O(N^1.3) 是怎么估出来的希尔排序的精确复杂度很难算多数教材也只给结论。但可以粗略估一遍理解为什么它比 O(N²) 好。先忽略1取gap ≈ n/3趟次gap组数每组元素个数单组最坏移动次数本趟总代价第 1 趟n/3n/3 组31 2 3(n/3) × 3 n第 2 趟n/9n/9 组912…8 36(n/9) × 36 4n………………最后一趟11 组n接近有序代价很小≈n单组代价怎么来的以第 2 趟为例gap 是 n/9 时每组有 9 个元素组内的插入排序最坏情况下第二个元素移动 1 次、第三个 2 次……第 9 个移动 8 次即12…8 36次。再乘以组数n/9得到 4n。于是每一趟的代价随趟次先增后减中间那几趟最贵比如 4n 这一趟两头第一趟和最后一趟都是大约 n 的量级。把这些趟加总结论落在O(N^1.3)附近。注意这里的关键差别直接插入排序在逆序时要累加到12…n ≈ n²/2而希尔排序把这份代价摊到了多趟里每趟都压到 O(n) 量级。至于为什么算不精确有两个原因后一趟的代价取决于前一趟的结果。第 2 趟还能按最坏情况算因为第 1 趟开始时数据是逆序的每一组也是逆序的但从第 3 趟起数据已经被前几趟改动过最坏情况这个前提就不成立了——必须引入概率分析。gap 序列的选择本身会影响复杂度。n/3、n/2、n/2.2等不同策略得出的结论不同1.3是常见取法下的经验值。所以这个数字记住结论即可不必试图手推。教材给的 O(N^1.3) 是一个经验结果不是从某一行代码直接推导出来的。实测它到底有没有白干活回到开头那个质疑预排序多花了力气值得吗看数据。同一组随机数据加入希尔排序与插入排序、堆排序同场比较数据规模直接插入排序希尔排序堆排序10 万条≈ 700 ms明显快于插入排序≈ 4 ms100 万条≈ 68 s与堆排序同量级重复数据多时可略快毫秒级结论有三条10 万条时希尔排序和插入排序已经不是一档。虽然它多了预排序的开销但预排序把数据变有序之后最后那趟插入排序的代价被压得很低总账反而划算。100 万条时希尔排序和堆排序处在同一量级。这验证了复杂度上的判断它已经跳出了 O(N²)不再是O(N²) 家族里比较优秀的那个而是和 O(N log N) 的算法同桌。希尔排序的一个隐藏优势是重复数据。上面的随机数据是用rand()生成的取值上限有限百万条数据里有大量重复值——重复度高时希尔排序表现更好甚至能略胜堆排序把重复度降下来堆排序会重新领先一点点。另外要说明一点数据量小的时候希尔排序没有优势。十来个元素时插入排序本来就快再用多趟分组去包装它多出来的循环开销纯属浪费。希尔排序的价值要到数据量上去之后才体现出来。常见误区把组内循环的边界写成i n。这是本篇最容易踩的坑和上一篇的i n - 1属于同一类错误但原因更绕要访问的是a[end gap]end本身没越界end gap却越界了。判断越界要看真正被访问的下标不是循环变量。数循环层数来估复杂度。三层写法和两层写法执行次数完全相同效率没有任何差别。循环层数只说明代码怎么组织不说明执行了多少次——这一点在上一篇已经埋过伏笔了。以为希尔排序是预排序 最后再调一次 InsertSort。实际上它只有一个循环gap缩小到 1 时那趟循环本身就是完整的插入排序。反过来也成立把gap固定为 1这段代码就是直接插入排序。认为预排序之后数组就应该有序了。预排序的目标是更接近有序不是有序。gap 取得巧时有可能恰好排好但那是偶然不是设计目标。附选择排序——一趟选两个数与它踩的那个坑同一节课还收掉了选择排序Selection Sort。它在分类上属于选择这一路和堆排序同一大类——都是选出最大/最小放到该在的位置。区别在于堆排序用堆来选O(log n) 找出极值选择排序用暴力遍历来选O(n) 找出极值。基础版本每趟遍历一遍、选出最小的放到最左边再遍历一遍选次小的如此往复。一个常见优化是一趟选出两个数同时维护最小值和最大值的下标最小的换到左端、最大的换到右端然后begin、end--两头往中间夹。voidSelectSort(int*a,intn){intbegin0,endn-1;while(beginend){intminibegin,maxibegin;// 存的是下标不是值for(intibegin1;iend;i){if(a[i]a[maxi]){maxii;}if(a[i]a[mini]){minii;}}Swap(a[begin],a[mini]);Swap(a[end],a[maxi]);begin;--end;}}这段代码有一个 bug而且平时测不出来。问题出在两次Swap的顺序上。如果maxi恰好等于begin——也就是最大值正好落在左端——那么第一次交换swap(a[begin], a[mini])会把最大值搬到mini的位置去。此时maxi这个下标还停在begin但那个位置上的值已经变了第二次Swap(a[end], a[maxi])交换的就不是最大值了。修复只需要在两处交换之间插一句Swap(a[begin],a[mini]);// 最大值原本在 begin 上第一次交换已经把它挪到了 mini 的位置if(maxibegin){maximini;}Swap(a[end],a[maxi]);这个 bug 的教训不在选择排序本身而在调试方法出问题时不要拿二十多个元素的数组去硬调应当把数组缩小到能画出图的程度逐趟标出begin、end、mini、maxi的位置让下标重叠的那一刻显形。用大数组调试等于把问题藏在噪声里。至于选择排序的整体评价最好情况也是 O(N²)。即使数组已经完全有序它也不知道仍然要一趟趟遍历过去把极值选出来。加了flag的冒泡在有序输入上是 O(N)选择排序没有这种优化空间。实测 5 万条随机数据插入排序在这个小规模组里表现最好选择排序垫底比冒泡还差一些。所以它的价值主要在教学逻辑直观适合理解选择这一类排序的思想在工程实践里几乎没有位置。 参考《数据结构知识库》第六节把冒泡/插入/选择排序统一列为 O(n²)最好情况也是 O(n²)这一点是选择排序区别于另外两者的地方第四节的堆一节给出了堆排序为什么能把这个选择过程加速到 O(n log n)。本节要点希尔排序的问题意识来自插入排序的死穴怕逆序。预排序的目标是让数组接近有序而不是排好。做法按间隔gap把数据逻辑分组不开新数组每组内部做插入排序然后缩小 gap 反复做。组内插入排序与直接插入排序只差一件事步长是gap而不是 1——a[end - gap]、a[end gap]。gap 越大跳得越快预排序同时把大的数往右推、小的数往左推。gap 1时这段代码就是上一篇的直接插入排序。所以希尔排序不是预排序 最后调一次 InsertSort而是一个循环自然走完。三层写法一组组排i gap与两层写法多组并着走i执行次数完全相同效率没有任何差别。循环层数不代表复杂度。组内循环边界是i n - gap而非i n被访问的下标是end gapend不越界不代表它不越界。gap gap / 3 1里的1不可省——它保证 gap 最终落到 1否则会停在 2 再变 0最后一趟最终排序永远不会发生。复杂度结论记O(N^1.3)即可。粗估思路gap ≈ n/3时每组 3 个 → 本趟约 ngap ≈ n/9时每组 9 个 →12…8 36×(n/9) ≈ 4n各趟代价先增后减累加落到 1.3 次方量级。精确值难算的原因后一趟的代价取决于前一趟的结果从第 3 趟起最坏情况前提失效需要概率分析且不同 gap 序列结论不同。数据量小时希尔排序没有优势它的价值在大规模数据上重复数据多时表现更好。选择排序优选版一趟选两个数bug 点在maxi begin第一次交换会把最大值挪走必须先修正maxi。调试应缩小数组并画图而不是硬看大数组。选择排序最好情况也是 O(N²)因为它无法感知已经有序这是它比冒泡还差的地方。
希尔排序：让插入排序不再怕逆序
希尔排序让插入排序不再怕逆序一个算法的短板通常是下一个算法的问题意识。为什么需要上一篇把直接插入排序的三种情况摊开了最好 O(N)、最坏 O(N²)、平均介于两者之间。它的表现取决于输入数据的逆序程度——数据越接近有序它就快得越像 O(N)。那么它的死穴也就很清楚了一旦数据是逆序的效率立刻掉下来。逆序时每个元素都要从当前位置一路挪到最前面挪动的步数分别是 n、n−1、n−2……累加就是 O(N²)。而且这些挪动全是一格一格走的——一个本该在数组末尾的大数要跟前面每个数比较一次、后移一次才能到位。于是问题变成了既然插入排序在有秩序的数据上快得惊人能不能先花点力气把数据变得接近有序再交给它收尾希尔排序Shell Sort就是这个思路。它是对直接插入排序的优化做法很简单先分组、每组内部插入排序让整个数组接近有序最后再走一趟完整的插入排序。一个自然的质疑是多干了活凭什么更快如果预排序的代价和收益差不多那这个算法就没有意义。这一点留到实测部分用数据回答。核心机制分组、跳着走希尔排序的做法是把数据按间隔 gap 分成若干组组内做插入排序。假设gap 3那么下标 0、3、6、9…… 的元素是一组1、4、7…… 是第二组2、5、8…… 是第三组。分组是逻辑上的——不需要真的把这些元素搬到新数组里只靠循环的步长控制把它们看成一组。gap 3 时逻辑分组 组1: a[0] a[3] a[6] a[9] ... 组2: a[1] a[4] a[7] ... 组3: a[2] a[5] a[8] ...分好组之后对每一组分别做插入排序。注意这里的插入排序和上一篇几乎一样唯一的区别是前一个元素不是end - 1而是end - gap。所以整段逻辑可以这样描述把a[end gap]插进同组中它前面的那些元素里其他元素整体后移 gap 格。这样做的效果用一个逆序数组最直观一个本来在数组开头的大数以前每次只能往右挪一格要挪 n 次现在每次跳 gap 格几步就跳到后面去了。反过来对小元素同样成立它本来要一格一格往左蹭现在几步就跳到前面。所以预排序同时在做两件事——大的更快到后面小的更快到前面一举两得。而gap越大跳跃跨度越大调整得越猛。这是希尔排序最反直觉的一点单趟预排序并不追求排好它追求的是让数据整体形状变好。一趟预排序结束后数组通常并不是有序的只是比之前更接近有序大的数更靠后小的数更靠前逆序对数量大幅减少。然后缩小 gap 再来一趟再缩小再来一趟……直到gap 1。gap 1时“间隔为 1 的元素为一组”——所有元素都在同一组里这时的插入排序就是完整的直接插入排序。也就是说希尔排序的最后一趟并不是另外调一次 InsertSort而是循环自然走到的那一步。由此也能看出gap 1时的预排序代码和上一篇的直接插入排序是同一段代码。上一篇写的那个插入排序就是希尔排序在 gap 取 1 时的特例。整个算法用一个循环把预排序和最终排序统一了。代码演示第一步写出一组的插入排序先别管所有组把一组排好。和上一篇对比着看只有1变成了gap// 排一组gap 是该组的步长end 是组内有序区的末尾intendi;inttmpa[endgap];// 同组中的后一个元素while(end0){if(tmpa[end]){a[endgap]a[end];// 元素整体后移 gap 格end-gap;}else{break;}}a[endgap]tmp;// 位置定了落位结构完全没变先存 tmp、从后往前扫、循环外统一落位。变的只是步长。第二步三层循环——一组一组排有了排一组的逻辑最朴素的扩展是外面再套一层枚举每一组。// 一组一组排gap 固定为 3 的示意版本voidShellSort_ByGroup(int*a,intn){intgap3;for(intj0;jgap;j)// 第 j 组{for(size_tij;in-gap;igap)// 组内的有序区末尾{intendi;inttmpa[endgap];while(end0){if(tmpa[end]){a[endgap]a[end];end-gap;}else{break;}}a[endgap]tmp;}}}j的作用是告诉程序现在排第几组j 0排第一组、j 1排第二组……一组排完了再排下一组。这里i n - gap是必须的不能写成i n。理由和上一篇的越界陷阱是同一类但更容易踩这一趟要读的是a[end gap]如果i走到了n - gapend gap就等于n——越界。所以组内循环的末尾必须停在n - gap - 1也就是条件写i n - gap。第三步两层循环——多组并着走三层循环能跑通但可以合并成两层不把一组排完再排下一组而是几组轮流各推进一步。// 多组并着走 gap 逐趟缩小voidShellSort(int*a,intn){intgapn;while(gap1){// 1 保证最后一趟 gap 一定等于 1// gap 1 时是预排序gap 1 时就是直接插入排序gapgap/31;for(size_ti0;in-gap;i)// 注意这里是 i不是 gap{intendi;inttmpa[endgap];while(end0){if(tmpa[end]){a[endgap]a[end];end-gap;}else{break;}}a[endgap]tmp;}}}改动只有两处外层控制内层步进效果三层写法j gap枚举组号i gap一组排完再排下一组两层写法不需要i几组齐头并进交替推进i的语义是处理完a[i]这个位置下一个处理a[i 1]——它属于下一组。于是循环自动在几组之间轮转而循环边界i n - gap对每一组都成立。两种写法效率完全一样。三层循环跑的次数和两层循环一样多只是组织顺序不同。这一点很重要——它正面推翻了循环层数多就慢的直觉。gap gap / 3 1是 gap 的缩小策略。/ 3让跨度迅速收敛 1保证它最终一定会落到 1——如果没有这个1gap会停在 2、再变成 0永远等不到 gap 1 的那一趟最终排序数组就不会被真正排好。 背景补充size_t是无符号类型i n - gap中右边的int会转换成无符号再比较。这里n - gap恒非负gap 最大为 n所以是安全的但如果循环边界表达式可能为负无符号比较会把负数变成极大的正数导致循环失控——这是 C 语言里典型的隐性陷阱。复杂度O(N^1.3) 是怎么估出来的希尔排序的精确复杂度很难算多数教材也只给结论。但可以粗略估一遍理解为什么它比 O(N²) 好。先忽略1取gap ≈ n/3趟次gap组数每组元素个数单组最坏移动次数本趟总代价第 1 趟n/3n/3 组31 2 3(n/3) × 3 n第 2 趟n/9n/9 组912…8 36(n/9) × 36 4n………………最后一趟11 组n接近有序代价很小≈n单组代价怎么来的以第 2 趟为例gap 是 n/9 时每组有 9 个元素组内的插入排序最坏情况下第二个元素移动 1 次、第三个 2 次……第 9 个移动 8 次即12…8 36次。再乘以组数n/9得到 4n。于是每一趟的代价随趟次先增后减中间那几趟最贵比如 4n 这一趟两头第一趟和最后一趟都是大约 n 的量级。把这些趟加总结论落在O(N^1.3)附近。注意这里的关键差别直接插入排序在逆序时要累加到12…n ≈ n²/2而希尔排序把这份代价摊到了多趟里每趟都压到 O(n) 量级。至于为什么算不精确有两个原因后一趟的代价取决于前一趟的结果。第 2 趟还能按最坏情况算因为第 1 趟开始时数据是逆序的每一组也是逆序的但从第 3 趟起数据已经被前几趟改动过最坏情况这个前提就不成立了——必须引入概率分析。gap 序列的选择本身会影响复杂度。n/3、n/2、n/2.2等不同策略得出的结论不同1.3是常见取法下的经验值。所以这个数字记住结论即可不必试图手推。教材给的 O(N^1.3) 是一个经验结果不是从某一行代码直接推导出来的。实测它到底有没有白干活回到开头那个质疑预排序多花了力气值得吗看数据。同一组随机数据加入希尔排序与插入排序、堆排序同场比较数据规模直接插入排序希尔排序堆排序10 万条≈ 700 ms明显快于插入排序≈ 4 ms100 万条≈ 68 s与堆排序同量级重复数据多时可略快毫秒级结论有三条10 万条时希尔排序和插入排序已经不是一档。虽然它多了预排序的开销但预排序把数据变有序之后最后那趟插入排序的代价被压得很低总账反而划算。100 万条时希尔排序和堆排序处在同一量级。这验证了复杂度上的判断它已经跳出了 O(N²)不再是O(N²) 家族里比较优秀的那个而是和 O(N log N) 的算法同桌。希尔排序的一个隐藏优势是重复数据。上面的随机数据是用rand()生成的取值上限有限百万条数据里有大量重复值——重复度高时希尔排序表现更好甚至能略胜堆排序把重复度降下来堆排序会重新领先一点点。另外要说明一点数据量小的时候希尔排序没有优势。十来个元素时插入排序本来就快再用多趟分组去包装它多出来的循环开销纯属浪费。希尔排序的价值要到数据量上去之后才体现出来。常见误区把组内循环的边界写成i n。这是本篇最容易踩的坑和上一篇的i n - 1属于同一类错误但原因更绕要访问的是a[end gap]end本身没越界end gap却越界了。判断越界要看真正被访问的下标不是循环变量。数循环层数来估复杂度。三层写法和两层写法执行次数完全相同效率没有任何差别。循环层数只说明代码怎么组织不说明执行了多少次——这一点在上一篇已经埋过伏笔了。以为希尔排序是预排序 最后再调一次 InsertSort。实际上它只有一个循环gap缩小到 1 时那趟循环本身就是完整的插入排序。反过来也成立把gap固定为 1这段代码就是直接插入排序。认为预排序之后数组就应该有序了。预排序的目标是更接近有序不是有序。gap 取得巧时有可能恰好排好但那是偶然不是设计目标。附选择排序——一趟选两个数与它踩的那个坑同一节课还收掉了选择排序Selection Sort。它在分类上属于选择这一路和堆排序同一大类——都是选出最大/最小放到该在的位置。区别在于堆排序用堆来选O(log n) 找出极值选择排序用暴力遍历来选O(n) 找出极值。基础版本每趟遍历一遍、选出最小的放到最左边再遍历一遍选次小的如此往复。一个常见优化是一趟选出两个数同时维护最小值和最大值的下标最小的换到左端、最大的换到右端然后begin、end--两头往中间夹。voidSelectSort(int*a,intn){intbegin0,endn-1;while(beginend){intminibegin,maxibegin;// 存的是下标不是值for(intibegin1;iend;i){if(a[i]a[maxi]){maxii;}if(a[i]a[mini]){minii;}}Swap(a[begin],a[mini]);Swap(a[end],a[maxi]);begin;--end;}}这段代码有一个 bug而且平时测不出来。问题出在两次Swap的顺序上。如果maxi恰好等于begin——也就是最大值正好落在左端——那么第一次交换swap(a[begin], a[mini])会把最大值搬到mini的位置去。此时maxi这个下标还停在begin但那个位置上的值已经变了第二次Swap(a[end], a[maxi])交换的就不是最大值了。修复只需要在两处交换之间插一句Swap(a[begin],a[mini]);// 最大值原本在 begin 上第一次交换已经把它挪到了 mini 的位置if(maxibegin){maximini;}Swap(a[end],a[maxi]);这个 bug 的教训不在选择排序本身而在调试方法出问题时不要拿二十多个元素的数组去硬调应当把数组缩小到能画出图的程度逐趟标出begin、end、mini、maxi的位置让下标重叠的那一刻显形。用大数组调试等于把问题藏在噪声里。至于选择排序的整体评价最好情况也是 O(N²)。即使数组已经完全有序它也不知道仍然要一趟趟遍历过去把极值选出来。加了flag的冒泡在有序输入上是 O(N)选择排序没有这种优化空间。实测 5 万条随机数据插入排序在这个小规模组里表现最好选择排序垫底比冒泡还差一些。所以它的价值主要在教学逻辑直观适合理解选择这一类排序的思想在工程实践里几乎没有位置。 参考《数据结构知识库》第六节把冒泡/插入/选择排序统一列为 O(n²)最好情况也是 O(n²)这一点是选择排序区别于另外两者的地方第四节的堆一节给出了堆排序为什么能把这个选择过程加速到 O(n log n)。本节要点希尔排序的问题意识来自插入排序的死穴怕逆序。预排序的目标是让数组接近有序而不是排好。做法按间隔gap把数据逻辑分组不开新数组每组内部做插入排序然后缩小 gap 反复做。组内插入排序与直接插入排序只差一件事步长是gap而不是 1——a[end - gap]、a[end gap]。gap 越大跳得越快预排序同时把大的数往右推、小的数往左推。gap 1时这段代码就是上一篇的直接插入排序。所以希尔排序不是预排序 最后调一次 InsertSort而是一个循环自然走完。三层写法一组组排i gap与两层写法多组并着走i执行次数完全相同效率没有任何差别。循环层数不代表复杂度。组内循环边界是i n - gap而非i n被访问的下标是end gapend不越界不代表它不越界。gap gap / 3 1里的1不可省——它保证 gap 最终落到 1否则会停在 2 再变 0最后一趟最终排序永远不会发生。复杂度结论记O(N^1.3)即可。粗估思路gap ≈ n/3时每组 3 个 → 本趟约 ngap ≈ n/9时每组 9 个 →12…8 36×(n/9) ≈ 4n各趟代价先增后减累加落到 1.3 次方量级。精确值难算的原因后一趟的代价取决于前一趟的结果从第 3 趟起最坏情况前提失效需要概率分析且不同 gap 序列结论不同。数据量小时希尔排序没有优势它的价值在大规模数据上重复数据多时表现更好。选择排序优选版一趟选两个数bug 点在maxi begin第一次交换会把最大值挪走必须先修正maxi。调试应缩小数组并画图而不是硬看大数组。选择排序最好情况也是 O(N²)因为它无法感知已经有序这是它比冒泡还差的地方。