> 希爾排序（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; } ```