数据结构与算法之PHP排序算法（希尔排序）
一、基本思想
希尔排序算法是希尔排序，也称递减增量排序算法，是插入排序的一种更高效的改进版本。
该方法的基本思想是：先将整个待排元素序列分割成若干个子序列（由相隔某个“增量”的元素组成的）分别进行直接插入排序，然后依次缩减增量再进行排序，待整个序列中的元素基本有序（增量足够小）时，再对全体元素进行一次直接插入排序。
二、算法过程
1）取增量，一般取数组长度 / 2；
2）按增量取得子序列，对子序列进行插入排序；
3）将增量递减，重复1、2步骤；
4）直至增量均为0，数列已经排好序。
三、算法图解
四、PHP代码实现
<?php
function shellSort($arr) {
$len = count($arr);
for ($gap = floor($len / 2); $gap > 0; $gap = floor($gap / 2)) {
for($i = $gap; $i < $len; $i++) {
for($j = $i - $gap; $j >= 0; $j -= $gap) {
if ($arr[$j + $gap] < $arr[$j]) {
$temp = $arr[$j];
$arr[$j] = $arr[$j+$gap];
$arr[$j + $gap] = $temp;
}
}
}
}
return $arr;
}
// 测试
$arr = range(1, 10);
shuffle($arr);
echo "排序前：";
print_r($arr);
echo "";
echo "排序后：";
$res = shellSort($arr);
print_r($res);
五、效率分析
1、时间复杂度：O(nlogn)
2、空间复杂度：O(1)，是不稳定排序。