Analisis kerumitan pelbagai algoritma pengisihan tatasusunan PHP-tutorial php-php.cn

Analisis kerumitan pelbagai algoritma pengisihan tatasusunan PHP

王林

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

asal

812 orang telah melayarinya

Kerumitan algoritma pengisihan tatasusunan PHP: Isih buih: O(n^2) Isih pantas: O(n log n) (purata) Isih gabung: O(n log n)

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

Algoritma isihan tatasusunan PHP Analisis Kerumitan

Dalam PHP, terdapat pelbagai algoritma pengisihan yang boleh digunakan untuk mengisih elemen dalam tatasusunan. Kecekapan setiap algoritma berbeza-beza, bergantung pada saiz tatasusunan dan pengedaran data.

Isih buih

Isih buih ialah algoritma pengisihan yang mudah, tetapi ia kurang cekap. Ia berfungsi dengan berulang kali membandingkan elemen bersebelahan dan menukar elemen yang lebih besar ke penghujung tatasusunan.

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

Salin selepas log masuk

Kerumitan masa: O(n^2)

Isih cepat

Isih cepat ialah algoritma bahagi-dan-takluk dan secara amnya dianggap sebagai algoritma isihan yang paling berkesan. Ia menggunakan rekursi untuk membahagikan tatasusunan kepada subarray yang lebih kecil dan mengisih setiap 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));
}

Salin selepas log masuk

Kerumitan masa: O(n log n) (secara purata)

Isih gabung

Isih gabung juga merupakan algoritma bahagi dan takluk. Ia berfungsi dengan membahagikan tatasusunan secara rekursif kepada subarray yang lebih kecil, mengisih subarray, dan kemudian menggabungkan subarray yang diisih.

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

Salin selepas log masuk

Kerumitan masa: O(n log n)

Kes praktikal

Andaikan anda mempunyai tatasusunan yang mengandungi 10000 integer. Anda boleh mengisih tatasusunan ini menggunakan algoritma di atas dan mengukur tempoh masa yang diperlukan untuk mengisih menggunakan fungsi microtime() PHP.

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

Salin selepas log masuk

Untuk tatasusunan 10,000 integer, keputusannya adalah seperti berikut:

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

Salin selepas log masuk

Hasilnya menunjukkan bahawa isihan cepat dan isihan gabungan adalah lebih cekap daripada isihan gelembung.

Atas ialah kandungan terperinci Analisis kerumitan pelbagai algoritma pengisihan tatasusunan PHP. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!