php快速排序三种方法

2. function quick_sort($array) {
3. if(count($array) $key = $array[0];
4. $rightArray = array();
5. $leftArray = array();
6. for($i = 1; $i if($array[$i] >= $key) {
7. $rightArray[] = $array[$i];
8. } else {
9. $leftArray[] = $array[$i];
10. }
11. }
12. $leftArray = quick_sort($leftArray);
13. $rightArray = quick_sort($rightArray);
14. return array_merge($leftArray, array($key), $rightArray);
15. }

复制代码

方法二：该算法来自算法导论，叫作Nico Lomuto方法（感兴趣goole上有详细说明）使用最经典的单方向一次遍历找到中值。 但这种算法在最坏情况下（例如值相同的数组，需要n-1次划分，每一次划分需要O(n) 时间去掉一个元素）最坏情况下为O(n*n)。 代码：

2. function quick_sort(&$array, $start, $end) {
3. if ($start >= $end) return;
4. $mid = $start;
5. for ($i = $start + 1; $i if ($array[$i] $mid++;
6. $tmp = $array[$i];
7. $array[$i] = $array[$mid];
8. $array[$mid] = $tmp;
9. }
10. }
11. $tmp = $array[$start];
12. $array[$start] = $array[$mid];
13. $array[$mid] = $tmp;
14. quick_sort($array, $start, $mid - 1);
15. quick_sort($array, $mid + 1, $end);
16. }

复制代码

方法三：该方法基本上是教科书式的常见写法，首先从左向右遍历小于中间元素的跳过，同时从右向左遍历遇到大的元素跳过，然后 如果没有交叉着交换两边值，继续循环，直到找到中间点。注意该方法在处理相同元素的时候，仍旧交换，这样在最坏情况下也有O(nlogn) 效率。但下面的函数中，如果将$array[$right] > $key 改成 $array[$right] >=$key 或将 $array[$left]

2. function quick_sort_swap(&$array, $start, $end) {
3. if($end $key = $array[$start];
4. $left = $start;
5. $right = $end;
6. while($left while($left $key)
7. $right--;
8. $array[$left] = $array[$right];
9. while($left $left++;
10. $array[$right] = $array[$left];
11. }
12. $array[$right] = $key;
13. quick_sort_swap(&$array, $start, $right - 1);
14. quick_sort_swap(&$array, $right+1, $end);
15. }

复制代码

您可能感兴趣的文章：

• php实用快速排序算法的实例代码
• php关联数组排序、快速排序的实例分享
• php实现快速排序(quick sort)的函数
• php实现快速排序的函数
• php冒泡排序与快速排序的例子