Complexity analysis of various PHP array sorting algorithms-PHP Tutorial-php.cn

Complexity analysis of various PHP array sorting algorithms

王林

Release： 2024-04-27 09:03:02

Original

807 people have browsed it

PHP array sorting algorithm complexity: bubble sort: O(n^2) quick sort: O(n log n) (average) merge sort: O(n log n)

各种 PHP 数组排序算法的复杂度分析

Complexity analysis of PHP array sorting algorithm

In PHP, there are a variety of sorting algorithms that can be used to sort elements in an array. The efficiency of each algorithm varies, depending on the size of the array and the distribution of the data.

Bubble sort

Bubble sort is a simple sorting algorithm, but it is less efficient. It works by repeatedly comparing adjacent elements and exchanging the larger element to the end of the array.

function bubbleSort($arr) {
    for ($i = 0; $i < count($arr); $i++) {
        for ($j = 0; $j < count($arr) - $i - 1; $j++) {
            if ($arr[$j] > $arr[$j + 1]) {
                $temp = $arr[$j];
                $arr[$j] = $arr[$j + 1];
                $arr[$j + 1] = $temp;
            }
        }
    }
    return $arr;
}

Copy after login

Time complexity: O(n^2)

Quick sort

Quick sort is a kind of divide and conquer algorithm, generally considered to be the most efficient sorting algorithm. It uses recursion to divide the array into smaller subarrays and sort each subarray.

function quickSort($arr) {
    if (count($arr) <= 1) {
        return $arr;
    }
    $pivot = $arr[count($arr) - 1];
    $left = [];
    $right = [];
    for ($i = 0; $i < count($arr) - 1; $i++) {
        if ($arr[$i] < $pivot) {
            $left[] = $arr[$i];
        } else {
            $right[] = $arr[$i];
        }
    }
    return array_merge(quickSort($left), [$pivot], quickSort($right));
}

Copy after login

Time complexity: O(n log n) (on average)

Merge sort

Merge sort It is also a divide and conquer algorithm. It works by recursively dividing the array into smaller subarrays, sorting the subarrays, and then merging the sorted subarrays.

function mergeSort($arr) {
    if (count($arr) <= 1) {
        return $arr;
    }
    $mid = count($arr) / 2;
    $left = mergeSort(array_slice($arr, 0, $mid));
    $right = mergeSort(array_slice($arr, $mid));
    return merge($left, $right);
}
function merge($left, $right) {
    $merged = [];
    $i = $j = 0;
    while ($i < count($left) && $j < count($right)) {
        if ($left[$i] <= $right[$j]) {
            $merged[] = $left[$i];
            $i++;
        } else {
            $merged[] = $right[$j];
            $j++;
        }
    }
    return array_merge($merged, array_slice($left, $i), array_slice($right, $j));
}

Copy after login

Time complexity: O(n log n)

Practical case

Suppose you have a database containing 10,000 Array of integers. You can sort this array using the algorithm above and measure how long it takes to sort using PHP's microtime() function.

$arr = range(1, 10000);
shuffle($arr); // 打乱数组以获得更现实的结果

$timeStart = microtime(true);
bubbleSort($arr);
$timeEnd = microtime(true);
echo "Bubble Sort: " . ($timeEnd - $timeStart) . " 秒\n";

$timeStart = microtime(true);
quickSort($arr);
$timeEnd = microtime(true);
echo "Quick Sort: " . ($timeEnd - $timeStart) . " 秒\n";

$timeStart = microtime(true);
mergeSort($arr);
$timeEnd = microtime(true);
echo "Merge Sort: " . ($timeEnd - $timeStart) . " 秒\n";

Copy after login

For an array containing 10,000 integers, the results are as follows:

Bubble Sort: 1.0129920272827 秒
Quick Sort: 0.001443982124329 秒
Merge Sort: 0.001151084899902 秒

Copy after login

The results show that quick sort and merge sort are significantly more efficient than bubble sort.

The above is the detailed content of Complexity analysis of various PHP array sorting algorithms. For more information, please follow other related articles on the PHP Chinese website!