PHP クイックソートアルゴリズム実装の原理とコードの紹介

この記事では、PHP クイック ソート アルゴリズム実装の原理とコードの紹介を紹介します。一定の参考価値があります。必要な友人は参照してください。お役に立てれば幸いです。

アルゴリズム原理

次のアニメーションは、5 分間学習アルゴリズムからのもので、クイック ソート アルゴリズムの原理と手順を示しています。

手順:

• 配列からベースライン値を選択します
• 配列を次より大きくしますベースライン値 ベンチマーク値より小さいものは同じ側に配置され、ベンチマーク値より小さいものは反対側に配置されます ベンチマーク値が中央に位置します
• 再帰ソート列の両側の配列

コード実装

function quickSort($arr)
{
    $len = count($arr);
    if ($len  $v) {
            $up[] = $arr[$i];
        } else {
            $low[] = $arr[$i];
        }
    }
    $low = quickSort($low);
    $up = quickSort($up);

    return array_merge($low, array($v), $up);
}

テスト コード:

$startTime = microtime(1);

$arr = range(1, 10);
shuffle($arr);

echo "before sort: ", implode(', ', $arr), "\n";
$sortArr = quickSort($arr);
echo "after sort: ", implode(', ', $sortArr), "\n";

echo "use time: ", microtime(1) - $startTime, "s\n";

テスト結果:

before sort: 1, 7, 10, 9, 6, 3, 2, 5, 4, 8
after sort: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
use time: 0.0009009838104248s

時間計算量

クイック ソートの時間計算量は最悪の場合 (N2) で O、平均時間計算量は O(N*lgN) です。

この文は理解しやすいです。並べ替えるシーケンスに N 個の数値があると仮定します。 1 回の走査の時間計算量は O(N) ですが、何回走査する必要があるでしょうか?少なくとも lg(N 1) 回、最大で N 回。

1) なぜ少なくとも lg(N 1) 倍なのでしょうか?クイックソートは、分割統治法を使用して走査します。これを二分木とみなします。走査する必要がある回数が二分木の深さです。完全な二分木の定義によると、その深さは二分木になります。少なくともlg(N 1)である。したがって、クイックソートの最小反復回数は lg(N 1) 回です。

2) なぜ最大でも N 回なのでしょうか?これは非常に単純であるはずです。クイック ソートを最大深さ N のバイナリ ツリーとして考えてください。したがって、高速読み取りソートの走査回数は最大でも N 回です。

[関連する推奨事項: PHP ビデオ チュートリアル ]

以上がPHP クイックソートアルゴリズム実装の原理とコードの紹介の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。