快速排序算法的原理:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。
虽说快速排序算法的原理是这样的,但是不同的思维方式,其理解也不一样,最终实现的方法也不一样。下面来看看PHP实现快速排序算法的3中方法。
1、该方法比较直观,但损失了大量的空间为代价,使用了效率较低的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 < $len=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); }
2、该算法来自算法导论,叫作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); }
3、该方法基本上是教科书式的常见写法,首先从左向右遍历小于中间元素的跳过,同时从右向左遍历遇到大的元素跳过,然后如果没有交叉着交换两边值,继续循环,直到找到中间点。注意该方法在处理相同元素的时候,仍旧交换,这样在最坏情况下也有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); }