PHP code example for quick sorting

The content of this article is about the code example of quick sorting in PHP. It has certain reference value. Friends in need can refer to it. I hope it will be helpful to you.

Quick sort

Quick sort (English: Quicksort), also known as partition-exchange sort (partition-exchange sort), short for quick sort, a sort Algorithm, first proposed 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, quicksort O(n log n) is often significantly faster than other algorithms because its inner loop can be achieved efficiently on most architectures.

The steps are:

Pick out an element from the sequence, called "pivot",

Reorder the sequence, all ratios Elements with a smaller base value are placed in front of the base, and all elements with a larger base value are placed after the base (the same number can go to either side). After this partition, the datum is in the middle of the sequence. This is called a partition operation.

Recursively sort the subarray of elements smaller than the base value and the subarray of elements greater than the base value.

When the recursion reaches the bottom, the size of the array is zero or one, which means it has been sorted. This algorithm will definitely end, because in each iteration, it will move at least one element to its final position.

Introduction in Wikipedia. The core idea is to use recursion. The animation below is very vivid.

Animation demonstration

<?php $arr = [33, 24, 8, 21, 2, 23, 3, 32, 16];

function quickSort($arr)
{
    $count = count($arr);

    if ($count < 2) {
        return $arr;
    }

    $leftArray = $rightArray = array();
    $middle = $arr[0];// 基准值

    for ($i = 1; $i < $count; $i++) {
        // 小于基准值，存入左边；大于基准值，存入右边
        if ($arr[$i] < $middle) {
            $leftArray[] = $arr[$i];
        } else {
            $rightArray[] = $arr[$i];
        }
    }

    $leftArray = quickSort($leftArray);
    $rightArray = quickSort($rightArray);

    return array_merge($leftArray, array($middle), $rightArray);
    // 倒序
    // return array_merge($rightArray, array($middle), $leftArray);
}

print_r(quickSort($arr));
// Array ( [0] => 2 [1] => 3 [2] => 8 [3] => 16 [4] => 21 [5] => 23 [6] => 24 [7] => 32 [8] => 33

Copy after login

The above is the detailed content of PHP code example for quick sorting. For more information, please follow other related articles on the PHP Chinese website!