希爾排序
基本概念
希爾排序(Shell's Sort)是插入排序的一種又稱“縮小增量排序”（Diminishing Increment Sort）涌矢，是直接插入排序算法的一種更高效的改進版本熄云。希爾排序是非穩(wěn)定排序算法.
希爾排序是把記錄按下標的一定增量分組刁愿，對每組使用直接插入排序算法排序；隨著增量逐漸減少咱枉，每組包含的關(guān)鍵詞越來越多玛臂，當增量減至1時，整個文件恰被分成一組辕近，算法便終止.
人話(圖解shell排序)
- 數(shù)據(jù)源[8,3,6,7,4,9,2,5]
-
初始增量gap=length/2=4
1.jpg
數(shù)組被分為四組[8,4], [3,9],[6,2],[7,5],組內(nèi)比較排序結(jié)果為
[4,8], [3,9],[2,6],[5,7]結(jié)果集為[4,3,2,5,8,9,6,7]
-
縮小增量gap=gap/2=2
2.jpg
數(shù)組被分會兩組[4,2,8,6],[3,5,9,7]組內(nèi)排序
[2,4,6,8],[3,5,7,9]結(jié)果集為[2,3,4,5,6,7,8,9] (巧合已經(jīng)有序,增量大于1,需要繼續(xù)縮小增量)
-
重復(fù)第二步gap=gap/2=1
3.jpg
數(shù)組被分為一組[2,3,4,5,6,7,8,9],組內(nèi)排序[2,3,4,5,6,7,8,9],由于增量已經(jīng)到達1,停止縮小增量輸出結(jié)果集[2,3,4,5,6,7,8,9]
代碼示例
Talk is cheap, show you my code!
<?php
/**
* 希爾排序
* @param array $arr
* @return array
*/
function shellSort(array $arr)
{
for ($gap = floor(count($arr) / 2); $gap > 0; $gap = floor($gap / 2)) { // 縮小增量
for ($i = $gap; $i < count($arr); $i++) { // 組內(nèi)循環(huán)排序
$j = $i;
while ($j - $gap >= 0 && $arr[$j] < $arr[$j - $gap]) { //完成組內(nèi)元素一次排序
swap($arr, $j, $j - $gap);
$j -= $gap;
}
}
echo implode(',', $arr) . PHP_EOL; // 完成一次增量輸出一次結(jié)果
}
return $arr;
}
/**
* 交換函數(shù)
* @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;
}
shellSort([8,3,6,7,4,9,2,5]);
結(jié)論
希爾排序的時間復(fù)雜度取決于初始增量的選取,本文所選去的初始增量方式時間復(fù)雜度為O(nlog2n)
