How to implement quick sorting in php

php method to implement quick sort: first create a PHP sample file; then create the exchange function and main function; then recursively sort the low sub-table and high sub-table; finally call the QuickSort algorithm.

# Recommended: "

PHP Video Tutorial》

Basic idea:

Quicksort is an improvement on bubble sort. His basic idea is to divide the records to be sorted into two independent parts through one sorting. The keywords of one part are smaller than the keywords of the other part of the record. Then the two parts of the records can be quickly sorted separately. The entire The sorting process can be performed recursively to achieve the purpose of ordering the entire sequence.

Basic algorithm steps:

As an example:

If the record to be sorted now is:

6   2   7   3   8   9

The first step, Create the variable $low to point to the first record in the record, $high to point to the last record, and $pivot as the pivot value to be the first element of the record to be sorted (not necessarily the first one), here:

$low = 0;
$high = 5;
$pivot = 6;

The second step is to move all numbers smaller than $pivot to the left of $pivot, so we can start looking for numbers smaller than 6, starting from $high, looking from right to left, and continue Decrementing the value of the variable $high, we find that the first data with subscript 3 is smaller than 6, so we move data 3 to the position of subscript 0 (the position pointed to by $low), and move the data 6 with subscript 0 to the next position. Mark 3, complete the first comparison:

3   2   7   6   8   9

//这时候,$high 减小为 3
$low = 0;
$high = 3;
$pivot = 6;

The third step, we start the second comparison, this time we have to look for one larger than $pivot, and we have to look from front to back. . Increment the variable $low and find that the data at subscript 2 is the first one larger than $pivot, so we use the data 7 at subscript 2 (the position pointed by $low) and the data 7 at subscript 3 (the position pointed at by $high). 6 of the data are exchanged, and the data status becomes the following table:

3   2   6   7   8   9

//这时候,$high 减小为 3
$low = 2;
$high = 3;
$pivot = 6;

Completing the second and third steps is called completing a cycle.

The fourth step (that is, starting the next cycle), imitates the process execution of the second step.

The fifth step is to imitate the process of the third step.

After executing the second loop, the data status is as follows:

3   2   6   7   8   9

//这时候,$high 减小为 3
$low = 2;
$high = 2;
$pivot = 6;

At this step, we find that $low and $high "meet": they both point to subscript 2. Thus, the first comparison is over. The result is as follows: all numbers on the left of $pivot(=6) are smaller than it, and all numbers on the right of $pivot are larger than it.

Then, group the data {3, 2} and {7, 8, 9} on both sides of $pivot and {3, 8, 9} and perform the above process separately until no more grouping is possible.

Note: The first pass of quick sort will not directly obtain the final result. It will only divide the numbers larger than k and smaller than k to both sides of k. In order to get the final result, you need to perform this step again on the arrays on both sides of subscript 2, and then decompose the array until the array can no longer be decomposed (only one data) to get the correct result.

Algorithm implementation:

//交换函数
function swap(array &$arr,$a,$b){
    $temp = $arr[$a];
    $arr[$a] = $arr[$b];
    $arr[$b] = $temp;
}

//主函数：
function QuickSort(array &$arr){
    $low = 0;
    $high = count($arr) - 1;
    QSort($arr,$low,$high);
}

In the main function, since the first pass of quick sort sorts the entire array, the starting point is $low=0,$high=count($arr)- 1.

Then the QSort() function is a recursive calling process, so it is encapsulated:

function QSort(array &$arr,$low,$high){
    //当 $low >= $high 时表示不能再进行分组，已经能够得出正确结果了
    if($low < $high){
        $pivot = Partition($arr,$low,$high);  //将$arr[$low...$high]一分为二，算出枢轴值
        QSort($arr,$low,$pivot - 1);	//对低子表（$pivot左边的记录）进行递归排序
        QSort($arr,$pivot + 1,$high);	//对高子表（$pivot右边的记录）进行递归排序
    }
}

From the QSort() function above, we can see that the Partition() function is the core of the entire code , because the function of this function is to select one of the keywords, such as selecting the first keyword. Then we try our best to put it in a certain position so that the values ​​on the left are smaller than it and the values ​​on the right are larger than it. We call such a keyword a pivot.

Go directly to the code:

//选取数组当中的一个关键字，使得它处于数组某个位置时，左边的值比它小，右边的值比它大，该关键字叫做枢轴
//使枢轴记录到位，并返回其所在位置
function Partition(array &$arr,$low,$high){
    $pivot = $arr[$low];   //选取子数组第一个元素作为枢轴
    while($low < $high){  //从数组的两端交替向中间扫描（当 $low 和 $high 碰头时结束循环）
        while($low < $high && $arr[$high] >= $pivot){
            $high --;
        }
        swap($arr,$low,$high);	//终于遇到一个比$pivot小的数，将其放到数组低端

        while($low < $high && $arr[$low] <= $pivot){
            $low ++;
        }
        swap($arr,$low,$high);	//终于遇到一个比$pivot大的数，将其放到数组高端
    }
    return $low;   //返回high也行，毕竟最后low和high都是停留在pivot下标处
}

The entire combined code is as follows:

function swap(array &$arr,$a,$b){
    $temp = $arr[$a];
    $arr[$a] = $arr[$b];
    $arr[$b] = $temp;
}

function Partition(array &$arr,$low,$high){
    $pivot = $arr[$low];   //选取子数组第一个元素作为枢轴
    while($low < $high){  //从数组的两端交替向中间扫描
        while($low < $high && $arr[$high] >= $pivot){
            $high --;
        }
        swap($arr,$low,$high);	//终于遇到一个比$pivot小的数，将其放到数组低端
        while($low < $high && $arr[$low] <= $pivot){
            $low ++;
        }
        swap($arr,$low,$high);	//终于遇到一个比$pivot大的数，将其放到数组高端
    }
    return $low;   //返回high也行，毕竟最后low和high都是停留在pivot下标处
}

function QSort(array &$arr,$low,$high){
    if($low < $high){
        $pivot = Partition($arr,$low,$high);  //将$arr[$low...$high]一分为二，算出枢轴值
        QSort($arr,$low,$pivot - 1);   //对低子表进行递归排序
        QSort($arr,$pivot + 1,$high);  //对高子表进行递归排序
    }
}

function QuickSort(array &$arr){
    $low = 0;
    $high = count($arr) - 1;
    QSort($arr,$low,$high);
}

We call the algorithm:

$arr = array(9,1,5,8,3,7,4,6,2);
QuickSort($arr);
var_dump($arr);

Complexity analysis:

In the optimal situation, that is, if the number axis is chosen to be at the middle value of the entire array, the array will be divided into two halves every time. Therefore, the time complexity in the optimal case is O(nlogn) (same as heap sort and merge sort).

In the worst case, if the sequence to be sorted is in forward or reverse order, then only edge data can be selected when selecting the pivot. Each division will result in one record less than the previous division. If one partition is empty, the final time complexity of this case is O(n^2).

Based on the best and worst cases, the average time complexity is O(nlogn).

Quick sort is an unstable sorting method.

Because quick sort is a relatively advanced sort, it is listed as one of the top ten algorithms in the 20th century. . . . With such an awesome algorithm, why shouldn’t we learn from it?

Although this algorithm is already very good, there are still areas for improvement in the above algorithm program.

The above is the detailed content of How to implement quick sorting in php. For more information, please follow other related articles on the PHP Chinese website!