Detailed explanation of PHP quick sort algorithm, detailed explanation of sorting algorithm

Detailed explanation of PHP quick sort algorithm, detailed explanation of sorting algorithm_PHP tutorial

WBOY

Release： 2016-07-13 10:14:27

Original

1008 people have browsed it

Detailed explanation of PHP quick sort algorithm, detailed explanation of sorting algorithm

Concept

Here is a picture borrowed from Baidu Encyclopedia, which is very vivid:

The quick sort algorithm is an optimization of the bubble algorithm. His idea is to split the array first, put the large element values into a temporary array, and put the small element values into another temporary array (the dividing point can be any element value in the array, generally Use the first element, i.e. $array[0]), then continue to repeat the above splitting of these two temporary arrays, and finally merge the small array elements and the large array elements. The idea of recursion is used here.

PHP implementation

Copy code The code is as follows:

/*
Quick sort
*/

function quickSort($array)
{
If(!isset($array[1]))
return $array;
$mid = $array[0]; //Get a keyword for splitting, usually the first element
$leftArray = array();
$rightArray = array();

foreach($array as $v)
{
            if($v > $mid)
               $rightArray[] = $v; //Put numbers larger than $mid into an array
           if($v < $mid)
              $leftArray[] = $v; //Put the number smaller than $mid into another array
}

$leftArray = quickSort($leftArray); //Split the smaller array again
$leftArray[] = $mid; //Add the divided elements to the end of the small array, don’t forget it

$rightArray = quickSort($rightArray); //Split the larger array again
Return array_merge($leftArray,$rightArray); //Combine two results
}

Comparison with bubble algorithm

Here I compare the sorting implemented by the bubble algorithm I wrote before. It can be seen that this algorithm is much more efficient than the bubble algorithm.

Copy code The code is as follows:

$a = array_rand(range(1,3000), 1500); //Even when the bubble algorithm exceeds 1600 elements, a message of insufficient memory will appear, but here in order to measure the difference between the two, just set It becomes 1500, which ensures that the bubble algorithm can be completed.
shuffle($a); //Get the array that has been shuffled
$t1 = microtime(true);
quickSort($a); //Quick sort
$t2 = microtime(true);
echo (($t2-$t1)*1000).'ms
';

require('./maopao.php'); //What is quoted here is the bubble algorithm sorting I wrote before
$t1 = microtime(true);
maoPao($a); //Bubble
$t2 = microtime(true);
echo (($t2-$t1)*1000).'ms';

Run result:

Copy code The code is as follows:

12.10880279541ms
772.64094352722ms