Introduction to the principle and code of PHP quick sort algorithm implementation

The content of this article is about the principle and code introduction of the PHP quick sort algorithm implementation. It has certain reference value. Friends in need can refer to it. I hope it will be helpful to you.

Algorithm Principle

The following animations are from the Five Minute Learning Algorithm, demonstrating the principles and steps of the quick sort algorithm.

Steps:

• Select a baseline value from the array
• Make the array greater than the baseline value Those that are smaller than the benchmark value are placed on the same side, and those that are smaller than the benchmark value are placed on the other side. The benchmark value is in the middle position
• Recursively sort the arrays on both sides of the column

Code implementation

function quickSort($arr)
{
    $len = count($arr);
    if ($len  $v) {
            $up[] = $arr[$i];
        } else {
            $low[] = $arr[$i];
        }
    }
    $low = quickSort($low);
    $up = quickSort($up);

    return array_merge($low, array($v), $up);
}

Test code:

$startTime = microtime(1);

$arr = range(1, 10);
shuffle($arr);

echo "before sort: ", implode(', ', $arr), "\n";
$sortArr = quickSort($arr);
echo "after sort: ", implode(', ', $sortArr), "\n";

echo "use time: ", microtime(1) - $startTime, "s\n";

Test result:

before sort: 1, 7, 10, 9, 6, 3, 2, 5, 4, 8
after sort: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
use time: 0.0009009838104248s

Time complexity

The time complexity of quick sort is O in the worst case (N2), the average time complexity is O(N*lgN).

This sentence is easy to understand: Suppose there are N numbers in the sequence to be sorted. The time complexity of one traversal is O(N). How many times do we need to traverse it? At least lg(N 1) times and at most N times.

1) Why is it at least lg(N 1) times? Quick sort uses the divide-and-conquer method to traverse. We regard it as a binary tree. The number of times it needs to be traversed is the depth of the binary tree. According to the definition of a complete binary tree, its depth is at least lg(N 1). Therefore, the minimum number of iterations of quick sort is lg(N 1) times.

2) Why is it at most N times? This should be very simple. Think of quick sort as a binary tree with a maximum depth of N. Therefore, the number of traversals for fast read sorting is at most N times.

[Related recommendations: PHP video tutorial]

The above is the detailed content of Introduction to the principle and code of PHP quick sort algorithm implementation. For more information, please follow other related articles on the PHP Chinese website!