希尔排序

---

希尔排序(Shell Sort)

1959年Shell发明，第一个突破O(n的平方)的排序算法，是简单插入排序的改进版。 它与插入排序的不同之处在于，它会优先比较距离较远的元素。 希尔排序又叫缩小增量排序。

算法描述

先将整个等排序的记录序列分割成为若干子序列分别进行直接插入排序，具体算法描述：

• 选择一个增量序列t1,t2,...,tk,其中ti>tj, tk=1;
• 按增量序列个数k, 对序列进行k趟排序；
• 每趟排序，根据对应的增量ti，将等排序列分割成若干长度为m的子序列，分别对各子表进行直接插入排序。 仅增量因子为1时，整个序列作为一个表来处理，表长度即为整个序列的长度。

动图演示

代码实现

$numbers = [20, 40, 60, 80, 30, 70, 90, 10, 50, 0, 5];
/**
 * @param $numbers
 * @return mixed
 * 希尔排序
 */
function shellSort($numbers)
{
    $length = count($numbers);
    for ($gap = floor($length / 2); $gap > 0; $gap = floor($gap / 2)) {
        var_dump($gap);
        for ($i = $gap; $i < $length; $i++) {
            $tmp = $numbers[$i];
            for ($j = $i - $gap; $j >= 0 && $numbers[$j] > $tmp; $j -= $gap) {
                $numbers[$j + $gap] = $numbers[$j];
            }
            $numbers[$j + $gap] = $tmp;
        }
    }
    return $numbers;
}
$numbers = shellSort($numbers);
var_dump($numbers);