排序算法之希尔排序

来源:www.onmpw.com

希尔排序是按照该算法的设计者的名字希尔命名的，其产生是希尔在插入排序的基础上改进的，可以说是一种特殊的插入排序。
下面先介绍一下插入排序的性质：
首先，插入排序算法对于已经有序的数据进行操作的时候，效率很高，可以达到线性排序的效率。
其次，插入排序进行排序的时候，每一趟排序只能移动一个数据。所以说这样的排序方法相对来说效率又比较低。
基于此性质，希尔排序的设计者发明了希尔排序算法，其基本思想是：
先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，分割子序列的方法就是设定一个增量，待当下的每个子序列有序的时候，将增量减一半（除以2，取整），再次进行子序列的排序。
依次进行，待整个序列中的记录基本上有序的时候，再对全体记录进行依次直接插入排序，此时增量减为1，因为直接插入排序在元素基本有序的情况下（根据上述第一点，接近最好的情况），效率是很高的。

因此，对于希尔排序，总结一句话，就是一种分组插入方法。因为设定了一个增量，并且依次将增量减1，所以希尔排序又称为递减增量排序算法。
对于希尔排序的算法步骤，可以用下图来表示

在这里需要说一下，希尔排序是稳定排序，我们可以设定一组数据按照上述方式进行排序，可以发现其为稳定排序。
希尔排序在按照增量分组以后，其组内的排序可以使用插入排序，当然也可以使用冒泡排序、选择排序等等下面奉上希尔排序的PHP实现代码

$arr = array(10, 6, 20, 50, 30, 7, 23, 35, 40, 1, 17);
/\*
\* 首先初始化 增量  数组长度/2 取整 floor() 函数向下取整  对于增量每次循环都由 当前增量/2
*/
for ($dl = floor(count($arr) / 2); $dl >= 1; $dl = floor($dl / 2)) {
    /\*
\* 每次从 增量的位置开始，直到数组递增变量达到数组的长度
*/
    for ($j = $dl; $j < count($arr); $j++) {
        for ($i = $j - $dl; $i >= 0; $i -= $dl) {
            if ($arr[$i + $dl] < $arr[$i]) {
                $temp = $arr[$i + $dl];
                $arr[$i + $dl] = $arr[$i];
                $arr[$i] = $temp;
            }
        }
    }
}

以上代码只是其中的一种实现方式，其代码实现有很多种，仅仅针对组内的排序方式就有很多，如果大家有什么好的方法，欢迎从下面留言，大家共同讨论，共同提高。