首页 > 学院 > 逻辑算法 > 正文

PHP希尔(Shell)排序算法的实现(代码详解)

2020-03-22 18:56:46
字体:
来源:转载
供稿:网友
希尔(Shell)排序或Shell的方法,是一种就地比较排序。它可以被看作是冒泡排序或插入排序的推广。该方法首先对彼此相距很远的元素对进行排序,然后逐步缩小要比较的元素之间的差距。从相距很远的元素开始,可以比近邻交换更快地移动一些位置不合适的元素。

Shell排序示例如下:

95dc4344a48b3bedf361af3b44efc0d.png

第一次遍历是“5排序”,对不同的子数组(a1, a6, a11)、(a2, a7, a12)、(a3, a8)、(a4, a9)、(a5, a10)执行插入排序。例如,它将子数组(a1, a6, a11)从(62,17,25)更改为(17,25,62)。

然后是“3排序”,对子数组(a1、a4、a7、a10)、(a2、a5、a8、a11)、(a3、a6、a9、a12)执行插入排序。

最后一次是“1排序”,它是整个数组(a1,…,a12)。如示例所示,Shell sort操作的子数组最初很短;后来它们变长了,但基本都是有序的。在这两种情况下,插入排序都是有效的。希尔(Shell)排序是不稳定的:它可能会改变具有相等值的元素的相对顺序。它是一种自适应排序算法,在输入部分排序时执行得会更快。

希尔(Shell)排序图形示意如下:

Sorting_shellsort_anim.gif

PHP实现希尔(Shell)排序算法的代码示例:

<?phpfunction shell_Sort($my_array){    $x = round(count($my_array)/2);    while($x > 0)    {        for($i = $x; $i < count($my_array);$i++){            $temp = $my_array[$i];            $j = $i;            while($j >= $x && $my_array[$j-$x] > $temp)            {                $my_array[$j] = $my_array[$j - $x];                $j -= $x;            }            $my_array[$j] = $temp;        }        $x = round($x/2.2);    }    return $my_array;}$test_array = array(3, 0, 2, 5, -1, 4, 1);echo "原始数组 :/n";echo implode(', ',$test_array );echo "/n排序后数组/n:";echo implode(', ',shell_Sort($test_array)). PHP_EOL;

输出:

原始数组 : 3, 0, 2, 5, -1, 4, 1 排序后数组 :-1, 0, 1, 2, 3, 4, 5

本篇文章就是关于PHP希尔(Shell)排序算法的介绍,简单易懂,希望对需要的朋友有所帮助!

以上就是PHP希尔(Shell)排序算法的实现(代码详解)的详细内容,更多请关注 其它相关文章!

郑重声明:本文版权归原作者所有,转载文章仅为传播更多信息之目的,如作者信息标记有误,请第一时间联系我们修改或删除,多谢。

发表评论 共有条评论
用户名: 密码:
验证码: 匿名发表