希尔排序
基本概念
希尔排序(Shell's Sort)是插入排序的一种又称“缩小增量排序”（Diminishing Increment Sort），是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法.
希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止.
人话(图解shell排序)
- 数据源[8,3,6,7,4,9,2,5]
-
初始增量gap=length/2=4
1.jpg
数组被分为四组[8,4], [3,9],[6,2],[7,5],组内比较排序结果为
[4,8], [3,9],[2,6],[5,7]结果集为[4,3,2,5,8,9,6,7]
-
缩小增量gap=gap/2=2
2.jpg
数组被分会两组[4,2,8,6],[3,5,9,7]组内排序
[2,4,6,8],[3,5,7,9]结果集为[2,3,4,5,6,7,8,9] (巧合已经有序,增量大于1,需要继续缩小增量)
-
重复第二步gap=gap/2=1
3.jpg
数组被分为一组[2,3,4,5,6,7,8,9],组内排序[2,3,4,5,6,7,8,9],由于增量已经到达1,停止缩小增量输出结果集[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++) { // 组内循环排序
$j = $i;
while ($j - $gap >= 0 && $arr[$j] < $arr[$j - $gap]) { //完成组内元素一次排序
swap($arr, $j, $j - $gap);
$j -= $gap;
}
}
echo implode(',', $arr) . PHP_EOL; // 完成一次增量输出一次结果
}
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;
}
shellSort([8,3,6,7,4,9,2,5]);
结论
希尔排序的时间复杂度取决于初始增量的选取,本文所选去的初始增量方式时间复杂度为O(nlog2n)
