php实现希尔排序算法的方法分析
发布:smiling 来源: PHP粉丝网 添加日期:2021-08-22 13:38:40 浏览: 评论:0
这篇文章主要介绍了php实现希尔排序算法的方法,简单说明了希尔排序的原理,并结合实例形式分析了php实现希尔排序的具体操作技巧,需要的朋友可以参考下。
本文实例讲述了php实现希尔排序算法的方法,分享给大家供大家参考,具体如下:
虽然现在各种程序语言都有其各自强大的排序库函数,但是这些底层实现也都是利用这些基础或高级的排序算法。
理解这些复杂的排序算法还是很有意思的,体会这些排序算法的精妙~
希尔排序(shell sort):希尔排序是基于插入排序的,区别在于插入排序是相邻的一个个比较(类似于希尔中h=1的情形),而希尔排序是距离h的比较和替换。
希尔排序中一个常数因子n,原数组被分成各个小组,每个小组由h个元素组成,很可能会有多余的元素。当然每次循环的时候,h也是递减的(h=h/n)。第一次循环就是从下标为h开始。希尔排序的一个思想就是,分成小组去排序。
理解这些算法,最好是有个图示。就先来代码吧。
- <?php
- /**
- * 希尔排序
- */
- function shell_sort(array $arr){
- // 将$arr按升序排列
- $len = count($arr);
- $f = 3;// 定义因子
- $h = 1;// 最小为1
- while ($h < $len/$f){
- $h = $f*$h + 1; // 1, 4, 13, 40, 121, 364, 1093, ...
- }
- while ($h >= 1){ // 将数组变为h有序
- for ($i = $h; $i < $len; $i++){ // 将a[i]插入到a[i-h], a[i-2*h], a[i-3*h]... 之中 (算法的关键
- for ($j = $i; $j >= $h; $j -= $h){
- if ($arr[$j] < $arr[$j-$h]){
- $temp = $arr[$j];
- $arr[$j] = $arr[$j-$h];
- $arr[$j-$h] = $temp;
- }
- //print_r($arr);echo '<br/>'; // 打开这行注释,可以看到每一步被替换的情形
- }
- }
- $h = intval($h/$f);
- }
- return $arr;
- }
- $arr = array(14, 9, 1, 4, 6, -3, 2, 99, 13, 20, 17, 15, 3);
- $shell = shell_sort($arr);
- echo '<pre>';
- print_r($shell);
- /**
- *
- Array
- (
- [0] => -3
- [1] => 1
- [2] => 2
- [3] => 3
- [4] => 4
- [5] => 6
- [6] => 9
- [7] => 13
- [8] => 14
- [9] => 15
- [10] => 17
- [11] => 20
- [12] => 99
- )
- )
- *
- */
Tags: php希尔排序算法
推荐文章
热门文章
最新评论文章
- 写给考虑创业的年轻程序员(10)
- PHP新手上路(一)(7)
- 惹恼程序员的十件事(5)
- PHP邮件发送例子,已测试成功(5)
- 致初学者:PHP比ASP优秀的七个理由(4)
- PHP会被淘汰吗?(4)
- PHP新手上路(四)(4)
- 如何去学习PHP?(2)
- 简单入门级php分页代码(2)
- php中邮箱email 电话等格式的验证(2)