-
-
function quick_sort($array) {
- if(count($array) $key = $array[0];
- $rightArray = array();
- $leftArray = array();
- for($i = 1; $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 if ($array[$i] $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]
-
-
function quick_sort_swap(&$array, $start, $end) {
- if($end $key = $array[$start];
- $left = $start;
- $right = $end;
- while($left while($left $key)
- $right--;
- $array[$left] = $array[$right];
- while($left $left++;
- $array[$right] = $array[$left];
- }
- $array[$right] = $key;
- quick_sort_swap(&$array, $start, $right - 1);
- quick_sort_swap(&$array, $right+1, $end);
- }
-
您可能感兴趣的文章：
- php实用快速排序算法的实例代码
- php关联数组排序、快速排序的实例分享
- php实现快速排序(quick sort)的函数
- php实现快速排序的函数
- php冒泡排序与快速排序的例子
| 
