第五章：PHP编程思想提升篇——希尔排序(插入排序升级版)

希尔排序(Shell Sort)是插入排序的一种。也称缩小增量排序，是直接插入排序算法的一种更高效的改进版本。如果连插入排序都没搞清楚，希尔排序就不要看了。

希尔排序是非稳定排序算法。该方法因DL．Shell于1959年提出而得名。

思路：

把一组数列分成几组进行插入排序，假如有10个数，按照floor(10/3)+1计算出得4，共4组。

备注：floor()函数可以求出小数的整数部分.

每一组分别进行插入排序，得到新的数列：

再按照floor(4/3)+1，计算得出2，共2组。

每一组分别进行插入排序，得到新的数列：

再按照floor(2/3)+1，计算得出1，共1组，对整个数列做插入排序，就可得出最后的结果。

基本思想：

先将整个待排元素序列分割成若干个子序列（由相隔某个“增量”的元素组成的）分别进行直接插入排序，然后依次缩减增量再进行排序，待整个序列中的元素基本有序（增量足够小）时，再对全体元素进行一次直接插入排序。因为直接插入排序在元素基本有序的情况下（接近最好情况），效率是很高的，因此希尔排序在时间效率上比前三种方法有较大提高。

希尔排序是按照不同步长对元素进行插入排序，当刚开始元素很无序的时候，步长最大，所以插入排序的元素个数很少，速度很快；当元素基本有序了，步长很小（最后的步长肯定为1），插入排序对于有序的序列效率很高。

关于步长的算法，步长的选取没有明确的规定，通过前人的研究我们用floor($step/3)+1这个公式。

看代码：

上面的代码，为了方便大家理解，总共用了4次循环，第一次循环（逐步减少步数），二次循环（几组数列切换），三次四次循环是（插入排序）。我们来做下改进，用三次循环：

由于多次插入排序，我们知道一次插入排序是稳定的，不会改变相同元素的相对顺序，但在不同的插入排序过程中，相同的元素可能在各自的插入排序中移动，最后其稳定性就会被打乱，所以shell排序是不稳定的。

楠神看到网上好多希尔排序步数都是floor($step/2)这个公式：

这两个公式哪个快呢？反复做了几次测试：

简单说下测试代码中的函数：

set_time_limit(0)作用延长脚本运行时间，PHP一般默认脚本运行时间是30秒，如果超过30秒还没有运行完程序，PHP就会自动超时。针对这块的内容，以后会做更详细的介绍。

rand(0,1000000)获得0——1000000之间的一个随机数

microtime(true)求当前的微妙时间戳，参数值“TRUE”一定不要忘记了。

当排序数字是200000时，公式floor($step/3)+1明显比公式floor($step/2)快那么一点点。

当排序数字是500000时，区别就没那么明显了。

整体上公式floor($step/3)+1是优于公式floor($step/2)的。在本节学习代码中大家可以自己测试下。

本节学习代码》》》