3）其实从两次分组排序之后就可以看出，这个数组已经基本有序了。这时最后就是以分组增量 1 再次进行简单插入排序。说白了，最后这一步就是一个普通的简单插入排序的过程了。
分步骤讲解之后是不是清楚很多了，再重复一篇，希尔排序其实就是按分组来一次大范围的插入排序，最后一步步缩小到只有 1 次增量的简单插入排序了。我们再来看看代码吧：
function ShellSort($arr) { $n = count($arr); $sedgewick = [5, 3, 1]; // 初始的增量值不能超过待排序列的长度 for ($si = 0; $sedgewick[$si] >= $n; $si++); // 开始分组循环，依次按照 5 、3 、 1 进行分组 for ($d = $sedgewick[$si]; $d > 0; $d = $sedgewick[++$si]) { // 获取当前的分组数量 for ($p = $d; $p < $n; $p++) { $tmp = $arr[$p]; // 插入排序开始，在当前组内 for ($i = $p; $i >= $d && $arr[$i - $d] > $tmp; $i -= $d) { $arr[$i] = $arr[$i - $d]; } $arr[$i] = $tmp; } } echo implode(\', \', $arr), PHP_EOL; } ShellSort($numbers);看着代码貌似有三层 for 循环呀，它哪里提升了效率了呢？其实希尔排序的效率提升确实是有限的，它其实是通过前几次的分组让数据先基本有序。而在分组的状态中，数据比较的数量并不会达到 n 的级别。当最后一次进行简单排序的时候，整个数据已经是基本有序了，在这种情况下交换的次数明显也会减少很多，所以它的时间复杂度在理想状态下可以减少到 O(log2n)2 的水平。
总结排序的入门餐怎么样？我们可不是直接就拿烂大街的冒泡和快排上手的吧。不出名不意味着不会用到，比如我面试的时候曾经有个公司就是在面试题上写明了不能使用冒泡和快排。这时候，我相信简单插入排序直观好理解的特性一定就能帮助我们度过这种面试难关了哦！
测试代码：
https://github.com/zhangyue0503/Data-structure-and-algorithm/blob/master/7.排序/source/7.1插入类排序：简单插入、希尔排序.php
参考文档：
本文示例选自 《数据结构》第二版，严蔚敏
《数据结构》第二版，陈越关注公众号：【硬核项目经理】获取最新文章
添加微信/QQ好友：【xiaoyuezigonggong/149844827】免费得PHP、项目管理学习资料
知乎、公众号、抖音、头条搜索【硬核项目经理】