php快速排序三种方法

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冒泡排序与快速排序的例子