希尔排序

希尔排序(Shell's Sort)是插入排序的一种是直接插入排序算法的一种更高效的改进版本，又称“缩小增量排序”。希尔排序是非稳定排序算法。

1. 算法描述

• 先取一个小于待排序数列长度n的整数d1作为第一个增量，将所有距离为d1的倍数的记录放在同一个组中。（一般的初次取序列的一半为增量，以后每次减半，直到增量为1。）
• 在各组内进行插入排序；
• 然后，取第二个增量d2<d1重复上述的分组和排序，直至增量为1，即所有记录放在同一组中进行插入排序。

希尔排序比插入排序高效是因为：希尔排序是比较相隔较远距离（增量）的数，使得数移动时能跨过多个元素，则进行一次比较就可能消除多个元素交换。

2. 动图演示

image

3. 代码实现

function shell_sort2($arr) {
    if(!is_array($arr)) return;
    $len = count($arr);
    /**
     * $gap为增量，用向右移1位的方式，得到初次增量为序列的一半
     * 并且增量每次减半，直到增量为1
     */
    for ($gap = $len >> 1; $gap > 0; $gap = $gap >> 1) {
        /**
         * $i为增量数，同时也是分组数，遍历分组，对每个组中的记录数进行插入排序
         */
        for($i = $gap; $i < $len; $i++) {
            /**
             * 遍历每个组中的记录，比较间隔为增量的两个数，如果后者大于前者则交换两者位置
             * 下面的插入排序可类比后面的插入排序算法
             */
            for($j = $i - $gap; $j >= 0 && $arr[$j + $gap] < $arr[$j]; $j -= $gap) {
                $temp = $arr[$j];
                $arr[$j] = $arr[$j + $gap];
                $arr[$j + $gap] = $temp;
            }

            /*
            $preIndex = $i - $gap;
            $current = $arr[$i];
            while ($preIndex >= 0 && $current < $arr[$preIndex]) {
                $temp = $arr[$preIndex];
                $arr[$preIndex] = $arr[$preIndex + $gap];
                $arr[$preIndex + $gap] = $temp;
                $preIndex -= $gap;
            }
            */
        }
    }
    return $arr;
}