PHP实现希尔排序（Shell Sort）

希尔排序

        基本思想: 希尔排序也是一种插入排序，它是简单插入排序经过改进之后的一个更高效的版本，也称为缩小增量排序，同时该算法是冲破O(n2）的第一批算法之一。它与插入排序的不同之处在于，它会优先比较距离较远的元素。

算法描述

      选择一个增量序列t1，t2，…，tk，其中ti>tj，tk=1；

按增量序列个数k，对序列进行k 趟排序；

每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m 的子序列，分别对各子表进行直接插入排序。仅增量因子为1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。

图片描述

代码实现(php）

<?php
    $arr = [9, 43, 12, 0, 87, 1];
function shell_sort(&$arr){
    $gap = count($arr) -1;
    $max = count($arr) -1;
    do{
        $gap = $gap/2;
        for($i = 0; $i <= $max - $gap; $i++){
            for($j = $i; $j <= $max - $gap; $j += $gap){
                if($arr[$j] < $arr[$j + $gap]){
                    swap($arr, $j, $j + $gap);
                }
            }
        }
    }while($gap > 1);
}
shell_sort($arr);
var_export($arr);