> 希尔排序（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]。 <br><br> ``` $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; } ```