Sharing three ways to implement quick sorting in PHP_PHP tutorial

Written three PHP quick ranking examples. The first one is inefficient but the simplest and easiest to understand. The second one is the one-way one-time traversal method to find the median value provided in the introduction to the algorithm. The third one is two-way traversal to find the middle value. Value of the classic quicksort algorithm. The implementation and comparison of the three groups of algorithms are as follows:

Method 1: This method is more intuitive, but at the cost of losing a lot of space and using a less efficient merge function. The least efficient of the three methods. In the worst case, the algorithm degenerates to (O(n*n))

Copy code The code is as follows:

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 Google if you are interested). It uses the most classic one-way traversal to find the median.
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).

Copy code The code is as follows:

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 and skip elements smaller than the middle element. At the same time, traverse from right to left and skip elements that are larger than the middle element. Then

If there is no intersection and exchange of values ​​on both sides, continue looping until the middle point is found. Note that this method still exchanges when processing the same elements, so that in the worst case there is O(nlogn)

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

The situation will not only degrade to O(n*n). In addition to the consumption of each comparison, it will also generate the additional overhead of n interactions. There are two other test points for this question, for students who memorize by rote:

1: Whether the two whiles in the middle are interchangeable. Of course, it cannot be interchanged, because fast disk requires an extra space to save the initial left value. In this way, when swapping left and right, first use the right to overwrite the saved value

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.

Copy code The code is as follows:

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

http://www.bkjia.com/PHPjc/740664.htmlwww.bkjia.comtruehttp: //www.bkjia.com/PHPjc/740664.htmlTechArticleWritten three PHP quick sorting examples, the first is inefficient but the simplest and easiest to understand, the second It is a one-way traversal method to find the median provided in the introduction to the algorithm. The third method is a two-way traversal to find the median...