PHP实现-希尔排序
2018-03-20 15:16 By
"Powerless"
3326
0
1
思路分析
希尔排序是指记录按下标的一定增量分组，对每一组使用 直接插入排序 ，随着增量逐渐减少，每组包含的关键字越来越多，当增量减少至 1 时，整个序列恰好被分成一组，算法便终止。
//希尔排序(对直接插入排序的改进)
function ShellSort(array &$arr)
{
$count = count($arr);
$inc = $count; //增量
do {
//计算增量
//$inc = floor($inc / 3) + 1;
$inc = ceil($inc / 2);
for ($i = $inc; $i < $count; $i++) {
$temp = $arr[$i]; //设置哨兵
//需将$temp插入有序增量子表
for ($j = $i - $inc; $j >= 0 && $arr[$j + $inc] < $arr[$j]; $j -= $inc) {
$arr[$j + $inc] = $arr[$j]; //记录后移
}
//插入
$arr[$j + $inc] = $temp;
}
//增量为1时停止循环
} while ($inc > 1);
}
//$arr = array(9,1,5,8,3,7,4,6,2);
$arr = array(49,38,65,97,76,13,27,49,55,04);
ShellSort($arr);
var_dump($arr);
小结：
时间复杂度：O(n log n)
空间复杂度：O(1)
通过以上代码的分析，相信大家已经有些明白，希尔排序的关键并不是随便分组后各自排序，而是将相隔某个“增量”的记录组成一个子序列，实现跳跃式的移动，使得排序的效率提高。
希尔排序属于不稳定排序
View in WeChat
Others Discussion
-
初识七层、五层、四层网络协议 Posted on 2021-04-09 16:52
-
投票通过，PHP 8 确认引入 Union Types 2.0 Posted on 2019-11-18 22:22
-
Linux工具 - NM目标文件格式分析 Posted on 2019-04-24 10:29
-
PHP扩展安装 Posted on 2019-06-24 11:28
-
Redis各种数据类型的使用场景举例分析【三】 Posted on 2018-11-22 17:00
-
ACID原则 Posted on 2020-12-17 16:36
-
PHP7不兼容性 Posted on 2018-03-07 15:59
-
MySQL分组 Posted on 2019-11-18 14:00
评 论