希尔排序，是插入排序的一种又称“缩小增量排序”，是直接插入排序算法的一种更高效的改进版本。算法的思想是将数组中的值，按照不同增量，分成若干个组，然后对各个组进行插入排序（对各个组进行插入排序的时候并不是先对一个组排序完成后再对另外一个组进行排序，而是轮流对每个组进行排序），然后再通过递减增量，实现排序功能。

算法步骤
1、减少增量；
2、从每组的第二个值开始遍历所有的值；
3、对每组进行插入排序。

动图演示

代码实现：

public function shellSort(array $arr)
{
    $length = count($arr);
    $gap = floor($length / 2);
    while ($gap > 0) { // 递减增量
        for ($i = $gap; $i < $length; $i ++) { // 循环所有的值
            $tmp = $arr[$i];
            $j = $i - $gap; // 每组的起始值
            while ($j >= 0 && $tmp < $arr[$j]) {
                $arr[$j + $gap] = $arr[$j]; // 被插入的数据比前面的数据小(大)，前面的数据就往后面移
                $j -= $gap;
            }
            $arr[$j + $gap] = $tmp;
        }
        $gap = floor($gap / 2);
    }
    
    return $arr;
}