总算进入我们的排序相关算法的学习了。相信不管是系统学习过的还是没有系统学习过算法的朋友都会听说过许多非常出名的排序算法，当然，我们今天入门的内容并不是直接先从最常见的那个算法说起，而是按照一定的规则一个一个的介绍。
首先，我们要介绍的排序算法是插入类型的排序算法。顾名思义，插入排序就是将无序的一个或几个记录“插入”到有序的序列中，比较典型的例子就是简单插入排序和希尔排序。
简单插入排序简单插入排序，也可以叫做直接插入排序。还是先看代码，再来进行下一步的解释。
function 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]; // 依次移动元素 } // 将元素放到合适的位置 $arr[$j] = $tmp; } echo implode(\', \', $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 。