日日操夜夜添-日日操影院-日日草夜夜操-日日干干-精品一区二区三区波多野结衣-精品一区二区三区高清免费不卡

php 數(shù)組排序算法復(fù)雜度：冒泡排序： o(n^2)快速排序： o(n log n) (平均)歸并排序： o(n log n)

PHP 數(shù)組排序算法的復(fù)雜度分析

在 PHP 中，有多種排序算法可用于對數(shù)組中的元素進(jìn)行排序。每種算法的效率各不相同，這取決于數(shù)組的大小和數(shù)據(jù)分布。

冒泡排序

冒泡排序是一種簡單的排序算法，但效率較低。它通過反復(fù)比較相鄰元素并交換較大的元素到數(shù)組末尾來工作。

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;
}

登錄后復(fù)制

時(shí)間復(fù)雜度：O(n^2)

快速排序

快速排序是一種分治算法，通常被認(rèn)為是效率最高的排序算法。它使用遞歸來將數(shù)組劃分為較小的子數(shù)組，并對每個(gè)子數(shù)組進(jìn)行排序。

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));
}

登錄后復(fù)制

時(shí)間復(fù)雜度：O(n log n) (平均情況下)

歸并排序

歸并排序也是一種分治算法。它通過遞歸將數(shù)組劃分為較小的子數(shù)組，對子數(shù)組進(jìn)行排序，然后合并排序的子數(shù)組來工作。

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));
}

登錄后復(fù)制

時(shí)間復(fù)雜度：O(n log n)

實(shí)戰(zhàn)案例

假設(shè)您有一個(gè)包含 10000 個(gè)整數(shù)的數(shù)組。您可以使用上述算法對該數(shù)組進(jìn)行排序，并使用 PHP 的 microtime() 函數(shù)測量排序所需的時(shí)間。

$arr = range(1, 10000);
shuffle($arr); // 打亂數(shù)組以獲得更現(xiàn)實(shí)的結(jié)果

$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";

登錄后復(fù)制

對于包含 10000 個(gè)整數(shù)的數(shù)組，結(jié)果如下：

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

登錄后復(fù)制

結(jié)果表明，快速排序和歸并排序明顯比冒泡排序更有效。