Three methods of quick sorting in php

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);
}

Method 2: This algorithm comes from the Introduction to Algorithms and is called the Nico Lomuto method (details are available on goole if you are interested Description) Find the median value using the most classic one-way traversal. But this algorithm is O(n*n) in the worst case (for example, an array with the same value requires n-1 divisions, and each division requires O(n) time to remove an element). Code:

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);
 }

Method 3: This method is basically a common textbook writing method. First, traverse from left to right to skip elements smaller than the middle element, and at the same time, traverse from right to left to skip large elements. ,Then If there is no cross-exchange of values ​​on both sides, continue looping until the middle point is found. Note that this method still swaps when processing the same elements, so there is O(nlogn) in the worst case efficiency. But in the following function, if $array[$right] > $key is changed to $array[$right] >=$key ​​or $array[$left] < $key is changed to $array[$left] <= $key is the worst Not only will the situation degrade to O(n*n), but in addition to the consumption of each comparison, there will also be the additional overhead of n interactions. There are two other test points for this question, for students who memorize by rote: 1. Are the two whiles in the middle interchangeable? Of course, it cannot be interchanged, because fast disk requires an extra space to save the initial left value. In this way, when the left and right are interchanged, the right side is used to overwrite the saved value first. is the lvalue of the median, otherwise problems will occur. See this sentence $array[$left] = $array[$right]; 2. $array[$right] = $key; The meaning of this statement can be omitted. This sentence cannot be omitted. You can consider an extreme case such as the ordering of two values ​​​​(5,2), and you will understand it step by step. Code: < $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) ;
}

Articles you may be interested in:

• PHP practical quick sorting algorithm example code
• Sharing examples of php associative array sorting and quick sorting
• php function to implement quick sort
• php function to implement quick sort
• Examples of php bubble sort and quick sort