クイックソートのためのPHPコード例

この記事の内容は、PHP でのクイックソートのコード例に関するものですが、一定の参考価値がありますので、困っている方は参考にしていただければ幸いです。

クイック ソート

クイック ソート (英語: Quicksort)、パーティション交換ソート (partition-exchange sort) とも呼ばれ、クイック ソートの略です。 Tony Hall によって最初に提案されたソート アルゴリズム。平均して、n 個の項目を並べ替えるには、O(n log n) 個の比較が必要です。最悪の場合、O(n2) 回の比較が必要になりますが、これは一般的ではありません。実際、クイックソート O(n log n) は、ほとんどのアーキテクチャで内部ループを効率的に実現できるため、他のアルゴリズムよりも大幅に高速であることがよくあります。

手順は次のとおりです。

シーケンスから「ピボット」と呼ばれる要素を選択します。

シーケンスをすべての比率で並べ替えます。小さい基底値は基底の前に配置され、大きい基底値を持つすべての要素は基底の後に配置されます (同じ数値がどちらの側にも配置できます)。この分割の後、データはシーケンスの途中にあります。これをパーティション操作と呼びます。

基本値より小さい要素の部分配列と基本値より大きい要素の部分配列を再帰的に並べ替えます。

再帰が最後に到達すると、配列のサイズは 0 または 1 になります。これは、配列がソートされたことを意味します。各反復で少なくとも 1 つの要素が最終位置に移動するため、このアルゴリズムは必ず終了します。

ウィキペディアでの紹介。中心となるアイデアは、recursion を使用することです。以下のアニメーションは非常に鮮やかです。

アニメーション デモンストレーション

<?php $arr = [33, 24, 8, 21, 2, 23, 3, 32, 16];

function quickSort($arr)
{
    $count = count($arr);

    if ($count < 2) {
        return $arr;
    }

    $leftArray = $rightArray = array();
    $middle = $arr[0];// 基准值

    for ($i = 1; $i < $count; $i++) {
        // 小于基准值，存入左边；大于基准值，存入右边
        if ($arr[$i] < $middle) {
            $leftArray[] = $arr[$i];
        } else {
            $rightArray[] = $arr[$i];
        }
    }

    $leftArray = quickSort($leftArray);
    $rightArray = quickSort($rightArray);

    return array_merge($leftArray, array($middle), $rightArray);
    // 倒序
    // return array_merge($rightArray, array($middle), $leftArray);
}

print_r(quickSort($arr));
// Array ( [0] => 2 [1] => 3 [2] => 8 [3] => 16 [4] => 21 [5] => 23 [6] => 24 [7] => 32 [8] => 33

ログイン後にコピー

以上がクイックソートのためのPHPコード例の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。