php实现快速排序的三种方法分享
发布:smiling 来源: PHP粉丝网 添加日期:2020-10-27 13:46:38 浏览: 评论:0
这篇文章主要介绍了php实现快速排序的三种方法,三种方法各有优缺点,需要的朋友可以参考下。
写了三种php快速排示例,第一种效率低但最简单最容易理解,第二个是算法导论上提供的单向一次遍历找中值方法,第三种是双向遍历找中值经典快排算法。三组算法实现和比较如下:
方法一:该方法比较直观,但损失了大量的空间为代价,使用了效率较低的merge函数,在三种方法中效率最低。最坏情况下算法退化为(O(n*n)),代码如下:
- function quick_sort($array) {
- if(count($array) <= 1) return $array;
- $key = $array[0];
- $rightArray = array();
- $leftArray = array();
- for($i = 1; $i < count($array); $i++) {
- if($array[$i] >= $key) {
- $rightArray[] = $array[$i];
- } else {
- $leftArray[] = $array[$i];
- }
- }
- $leftArray = quick_sort($leftArray);
- $rightArray = quick_sort($rightArray);
- return array_merge($leftArray, array($key), $rightArray);
- }
方法二:该算法来自算法导论,叫作Nico Lomuto方法(感兴趣goole上有详细说明)使用最经典的单方向一次遍历找到中值。
但这种算法在最坏情况下(例如值相同的数组,需要n-1次划分,每一次划分需要O(n) 时间去掉一个元素)最坏情况下为O(n*n),代码如下:
- function quick_sort(&$array, $start, $end) {
- if ($start >= $end) return;
- $mid = $start;
- for ($i = $start + 1; $i <= $end; $i++) {
- if ($array[$i] < $array[$mid]) {
- $mid++;
- $tmp = $array[$i];
- $array[$i] = $array[$mid];
- $array[$mid] = $tmp;
- }
- }
- $tmp = $array[$start];
- $array[$start] = $array[$mid];
- $array[$mid] = $tmp;
- quick_sort($array, $start, $mid - 1);
- quick_sort($array, $mid + 1, $end);
- }
方法三:该方法基本上是教科书式的常见写法,首先从左向右遍历小于中间元素的跳过,同时从右向左遍历遇到大的元素跳过,然后如果没有交叉着交换两边值,继续循环,直到找到中间点。注意该方法在处理相同元素的时候,仍旧交换,这样在最坏情况下也有O(nlogn)效率。但下面的函数中,如果将$array[$right] > $key 改成 $array[$right] >=$key 或将 $array[$left] < $key改成$array[$left] <= $key则最坏情况不但会堕落为O(n*n).而且除了每次比较的消耗外,还会产生n次交互的额外开销。该题还有另外两个考点,针对死记硬背的同学:
1:中间的两个while可否互换。当然不能互换,因为对于快盘需要一个额外的空间保存初始的左值,这样左右互换的时候,先用右边覆盖已经保存为中值的左值,否则会出现问题。见这句$array[$left] = $array[$right];
2:$array[$right] = $key; 该语句含义可否省略。该句不能省略,大家可以考虑一个极端情况比如两个值的排序(5,2),逐步看下就明白了,代码如下:
- function quick_sort_swap(&$array, $start, $end) {
- if($end <= $start) return;
- $key = $array[$start];
- $left = $start;
- $right = $end;
- while($left < $right) {
- while($left < $right && $array[$right] > $key)
- $right--;
- $array[$left] = $array[$right];
- while($left < $right && $array[$left] < $key)
- $left++;
- $array[$right] = $array[$left];
- }
- $array[$right] = $key;
- quick_sort_swap(&$array, $start, $right - 1);
- quick_sort_swap(&$array, $right+1, $end);
- }
Tags: php快速排序
相关文章
- ·PHP冒泡排序程序代码与源代码(2015-04-09)
- ·php冒泡排序、快速排序、快速查找、二维数组去重实例分享(2020-11-20)
- ·PHP两种快速排序算法实例(2021-05-14)
- ·php简单实现快速排序的方法(2021-05-21)
- ·php冒泡排序与快速排序实例详解(2021-06-28)
- ·PHP递归实现快速排序的方法示例(2021-08-23)
推荐文章
热门文章
最新评论文章
- 写给考虑创业的年轻程序员(10)
- PHP新手上路(一)(7)
- 惹恼程序员的十件事(5)
- PHP邮件发送例子,已测试成功(5)
- 致初学者:PHP比ASP优秀的七个理由(4)
- PHP会被淘汰吗?(4)
- PHP新手上路(四)(4)
- 如何去学习PHP?(2)
- 简单入门级php分页代码(2)
- php中邮箱email 电话等格式的验证(2)