数据结构与算法之PHP排序算法(希尔排序)

一、基本思想
希尔排序算法是希尔排序,也称递减增量排序算法,是插入排序的一种更高效的改进版本。
该方法的基本思想是:先将整个待排元素序列分割成若干个子序列(由相隔某个“增量”的元素组成的)分别进行直接插入排序,然后依次缩减增量再进行排序,待整个序列中的元素基本有序(增量足够小)时,再对全体元素进行一次直接插入排序。
 
二、算法过程
1)取增量,一般取数组长度 / 2;
2)按增量取得子序列,对子序列进行插入排序;
3)将增量递减,重复1、2步骤;
4)直至增量均为0,数列已经排好序。
 
三、算法图解
数据结构与算法之PHP排序算法(希尔排序)
 
四、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 "</br>";
echo "排序后:";
$res = shellSort($arr);
print_r($res);
 
五、效率分析
1、时间复杂度:O(nlogn)
2、空间复杂度:O(1),是不稳定排序。
上一篇:ev3dev :利用ssh登录系统


下一篇:Python实现八大排序算法(转载)+ 桶排序(原创)