JIYIK CN >

Quick sort is a sorting algorithm developed by Tony Hall. On average, sorting n items requires O(n log n) comparisons. In the worst case, O(n2) comparisons are required, but this is uncommon. In fact, quick sort is often significantly faster than other O(n log n) algorithms because its inner loop can be implemented efficiently on most architectures.

Quick sort uses a divide and conquer strategy to divide a list into two sub-lists.

The above part is quoted from the Internet. I can never remember these definitions clearly.

Let's look at the implementation steps directly below

1. Pick an element from the sequence, called the "baseline" (there are many ways to find this base, here we use the first element as the base by default)

2. Rearrange the sequence, placing all elements smaller than the base value in front of the base value, and all elements larger than the base value in the back of the base value (the same number can be on either side). After this partition is exited, the base value is in the middle of the sequence. This is called a partition operation.

3. Divide the array into two parts based on the middle position of the benchmark obtained in the second step, and recursively sort the subsequence of elements less than the benchmark value and the subsequence of elements greater than the benchmark value.

4. Repeat the second step until the number of values ​​in the subsequence is 1

One of the sorting processes can be referred to the following figure

Above we have learned about the process of finding the reference position. Now we just need to recursively split the array according to the reference position and repeat the above process for each sub-array one by one.

Let’s look at the implementation process

function FindPv(&$arr,$s,$e){
    $p = $s; //基准起始位置
    $v = $arr[$p];  //将数组的第一个值作为基准值
    while($s<$e){
        while($arr[$e]>$v&&$e>$p){
            $e--;
        }
        $arr[$p] = $arr[$e];
        $p = $e;
        while($arr[$s]<$v&&$s<$p){
            $s++;
        }
        $arr[$p] = $arr[$s];
        $p = $s;
    }
    $arr[$p] = $v;
    return $p;
}
function PvSort(&$arr,$s,$e){
    if($s>=$e) return ;
    $nextP = FindPv($arr,$s,$e);  //找到下一个基准所在位置
    PvSort($arr,$s,$nextP-1);
    PvSort($arr,$nextP+1,$e);
}
$arr = array(10,6,8,23,4,1,17,56,32,50,11,9);
PvSort($arr);
print_r($arr);

The above is a quick sort implemented by recursion. Recursion is very convenient to use and allows us to grasp the overall architecture of the program. The system has already done the underlying details for us. In fact, the underlying recursion uses the stack mechanism. We can also use the stack mechanism to implement the quick sort algorithm without recursion. You can check the non-recursive implementation of quick sort . This will help us have a deeper understanding of the implementation mechanism of the algorithm.

I hope this article is helpful to you.