希尔排序

将待排序数组按照步长gap进行分组，然后将每组的元素利用直接插入排序的方法进行排序；每次将gap折半减小，循环上述操作；当gap=1时，利用直接插入，完成排序。

java

public static void shellSort(int[] array) {
    int n = array.length;
    int h;
    for (h = n / 2; h > 0; h /= 2) {
        for (int i = h; i < n; i++) {
            for (int j = i - h; j >= 0; j -= h) {
                if (array[j] > array[j + h]) {
                    int temp = array[j];
                    array[j] = array[j + h];
                    array[j + h] = temp;
                }
            }
        }
    }
}

php

希尔排序

function shellSort($arr) {
    $length = count($arr);
    $gap = intval($length / 2);
    while ($gap > 0) {
        for ($i = $gap; $i < $length; $i++) {
            for ($j = $i - $gap; $j >= 0; $j -= $gap) {
                if ($arr[$j] > $arr[$j + $gap]) {
                    $temp = $arr[$j];
                    $arr[$j] = $arr[$j + $gap];
                    $arr[$j + $gap] = $temp;
                }
            }
        }
        $gap = intval($gap / 2);

    }
}