さまざまな PHP 配列ソート アルゴリズムの複雑さの分析

PHP 配列ソート アルゴリズムの複雑さ: バブル ソート: O(n^2) クイック ソート: O(n log n) (平均) マージ ソート: O(n log n)

PHP 配列ソート アルゴリズムの複雑さの分析

PHP には、配列内の要素をソートするために使用できるさまざまなソート アルゴリズムがあります。各アルゴリズムの効率は、配列のサイズとデータの分布に応じて異なります。

バブル ソート

バブル ソートは単純な並べ替えアルゴリズムですが、効率は低くなります。これは、隣接する要素を繰り返し比較し、大きい方の要素を配列の最後に交換することで機能します。

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

時間計算量: O(n^2)

クイック ソート

クイック ソートは一種の分割であり、征服アルゴリズム。一般に最も効率的な並べ替えアルゴリズムであると考えられています。再帰を使用して配列を小さなサブ配列に分割し、各サブ配列を並べ替えます。

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

時間計算量: O(n log n) (平均)

マージ ソート

マージ ソートです。分割統治アルゴリズムでもあります。これは、配列をより小さいサブ配列に再帰的に分割し、サブ配列をソートし、ソートされたサブ配列をマージすることによって機能します。

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

時間計算量: O(n log n)

実用的なケース

10,000 個の配列を含むデータベースがあると仮定します。整数の。上記のアルゴリズムを使用してこの配列を並べ替え、PHP の microtime() 関数を使用して並べ替えにかかる時間を測定できます。

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

10,000 個の整数を含む配列の結果は次のとおりです。

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

結果は、クイック ソートとマージ ソートがバブル ソートよりも大幅に効率的であることを示しています。

以上がさまざまな PHP 配列ソート アルゴリズムの複雑さの分析の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。