> 希尔排序（Shell's Sort）是直接插入排序算法的一种更高效的改进版本，又称“缩小增量排序”（Diminishing Increment Sort）。 > 希尔排序是将要排序的数组按下标的一定增量进行分组，每组分别进行直接插入排序，随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个数组都被分成一组，算法结束。 图示： ~~~ 1、初始数组：$arr = [3,9,2,5,7,6,8,1] 2、初始增量：$gap = count($arr) / 2; // 4 ~~~  数组被分成了四组：\[3,7\]，\[9,6\]，\[2,8\]，\[5,1\]。对每组分别进行排序后，结果为：\[3,7\]，\[6,9\]，\[2,8\]，\[1,5\]。因此结果集为：\[3,6,2,1,7,9,8,5\]。 ~~~ 3、缩小增量：$gap = $gap / 2; // 2 ~~~  数组被分为两组\[3,2,7,8\]，\[6,1,9,5\]，分别进行排序，结果为：\[2,3,7,8\]，\[1,5,6,9\]，结果集为：\[2,1,3,5,7,6,8,9\]; ~~~ 4、增量大于1,需要继续缩小增量，重复第三步：$gap = $gap / 2; // 1 ~~~  数组会被分为一组\[2,1,3,5,7,6,8,9\]，进行组内排序，由于增量已经等于1，算法结束，输出结果：\[1,2,3,5,6,7,8,9\]。 ~~~ $arr = [3,9,2,5,7,6,8,1]; $result = $this->shellSort($arr); // [1,2,3,5,6,7,8,9] /** * 希尔排序 * @param array $arr * @return array|string */ function shellSort(array $arr) { for ($gap = intval(count($arr) / 2); $gap > 0; $gap = intval($gap / 2)) { // 缩小增量 for ($i = $gap; $i < count($arr); $i++) { // 组内循环排序 $j = $i; while ($j - $gap >= 0 && $arr[$j] < $arr[$j - $gap]) { //完成组内元素一次排序 $this->swap($arr, $j, $j - $gap); $j -= $gap; } } } return $arr; } /** * 交换函数 * @param array $arr * @param int $a * @param int $b */ function swap(array &$arr, int $a, int $b) { $temp = $arr[$a]; $arr[$a] = $arr[$b]; $arr[$b] = $temp; } ~~~