终于进入我们对排序相关算法的学习了。相信系统学过算法或者没有系统学过算法的朋友，都会听说过很多非常有名的排序算法。当然，我们今天入门的内容并不是直接从最常见的算法中得出，而是根据一定的规则。规则一一介绍。首先，我们要介绍的排序算法是插入式排序算法。顾名思义，插入排序就是将一条或几条无序的记录“插入”到一个有序的序列中。典型的例子是简单的插入排序和希尔排序。简单插入排序简单插入排序也可以称为直接插入排序。或者先看代码，再解释下一步。函数InsertSort($arr){$n=count($arr);for($i=1;$i<$n;$i++){//开始循环，从第二个元素开始，下标为1$tmp=$arr[$i];//取出未排序序列的第一个元素for($j=$i;$j>0&&$arr[$j-1]>$tmp;$j--){//从当前下标判断为向前判断，如果前一个大于当前元素$arr[$j]=$arr[$j-1];//依次移动元素}//将元素放在合适的位置Position$arr[$j]=$tmp;}echoimplode(',',$arr),PHP_EOL;}InsertSort($numbers);//49,38,65,97,76,13,27,49//13,27,38,49,49,65、76、97代码不多，但其实非常容易理解。下面就拿测试数据的前两个数字来简单说明一下。首先，第一次循环从1开始，即第一个取出的未排序序列元素是tmp=arr[1]，也就是当前tmp=38。然后开始循环，当前循环是判断是否是j-1元素大于当前tmp元素，如果是则进入循环体，arr[1]=arr[0]。到目前为止，arr[0]和arr[1]现在都是49。整个序列是49,49,65,...最后令arr[0]=$tmp，等于38。（循环时j--）。整个序列是38,49,65,...通过下图，我们可以更清楚的看到整个序列完成排序的过程。从上面的步骤可以看出，简单的插入排序是从一侧开始，让前面的数据逐渐有序的过程。从代码中可以看出，它在内部循环中不断递减j，与之前的有序序列进行比较，找到合适的位置后，将数据放到这个位置。从代码和我们的分析来看，简单插入排序的时间复杂度是O(n2)。同时，它是一个稳定的排序。什么是稳定排序？细心的同学应该已经发现，在我们的测试代码中，有两个相同的数据，就是49。稳定是指同一数据在排序前后位置不会发生变化，前面的49还在后面的49前面，这就是排序的稳定性。另外，简单插入排序更适用于初始记录基本有序的情况。当初始记录乱序且n较大时，该算法的时间复杂度会比较高，不适合使用。希尔排序简单插入排序很好理解，希尔排序是什么鬼？别担心，我们从名字上看不出什么，因为这种名字是以它的发现者命名的。实际上，希尔排序是一种插入排序算法。上面说了简单插入排序适用于基本有序的情况，而希尔排序则是为了提高简单插入排序的效率。它的主要目的是减少排序n的大小，让经过多次排序的数据形成基本有序的格式。对于这个算法，我们先不能上传代码，先看图吧。你明白吗？我们实际上是在对数据进行分组，每一次分组都是按照一定的增量进行的。比如我们的示意图中，第一次以5为增量排序，第二次以3为增量排序。这样，第三次排序时，增量为1，就变成了一个普通的简单插入排序。过一段时间就会体现在我们的代码中。下面我们对这三种排序按照增量为迭代顺序进行具体分析：1）在第一次迭代中，我们将分组增量设置为5，然后就有了三组数据，分别是49和13、38和27、65、49，然后对这三组数据进行简单插入排序，之后数组的结果为13、27、49、97、76、49、38、65。2）在第二次迭代中，分组增量为3，此时分为两组，每组三个数据，一组为13、97、38，一组为27、76、65。对这两组数据进行简单插入排序后，更新数组的结果为13、27、49、38、65、49、97、76。3）其实从两次分组排序就可以看出该数组基本上是有序的。此时，最后一步就是再次进行简单插入排序，分组增量为1。说白了，最后一步就是一个普通的简单插入排序过程。一步步解释之后，是不是更清楚了？让我们再重复一遍这篇文章。希尔排序实际上是按组进行大规模的插入排序，最后逐步缩小到只有1个增量的简单插入排序。我们再看一下代码：functionShellSort($arr){$n=count($arr);$sedgewick=[5,3,1];//初始增量值不能超过要排序的列的长度($si=0;$sedgewick[$si]>=$n;$si++);//开始分组循环，依次对5、3、1进行分组for($d=$sedgewick[$si];$d>0;$d=$sedgewick[++$si]){//得到当前的组数($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;}}echoimplode(',',$arr),PHP_EOL;}ShellSort($numbers);看代码好像是三层for循环，怎么提高效率？事实上，希尔排序的效率提升确实有限。其实就是通过前面的分组，让数据基本有序。在分组状态下，数据比较的次数没有达到n的水平。当最后进行简单排序时，整个数据就基本有序了。这样的话，交换的次数显然会减少很多，所以它的时间复杂度可以降低到理想状态下的O(log2n)2。级。总结一下这种情况的开胃菜怎么样？我们不只是从BadStreet的冒泡和快速队列开始。不出名不代表不会用。比如我在面试的时候，曾经有一家公司表示，面试题中不能使用冒泡和快速排序。这个时候相信简单插入排序直观易懂的特点一定能帮我们攻克这次面试难关！测试代码：https://github.com/zhangyue0503/Data-structure-and-algorithm/blob/master/7。sorting/source/7.1插入类排序：简单插入，希尔sorting.php参考文档：本文精选示例来自《数据结构》第二版，严伟民《数据结构》第二版，陈越各自媒体平台均可被搜【硬核项目经理】
