PHP でクイックソート非再帰アルゴリズムを実装する方法

はじめに

クイック ソートは、配列を 2 つのサブ配列に連続的に分割することでソートを実装する効率的なソート アルゴリズムです。クイック ソート アルゴリズムでは、ピボット値が選択され、ピボット値より小さいすべての要素がその左側に配置され、ピボット値より大きいすべての要素が右側に配置されます。このプロセスは、配列全体がソートされるまで、左右の部分配列に再帰的に適用されます。

クイック ソートは、元の問題を 2 つの小さなサブ問題に分解し、これらのサブ問題を再帰的に解決することで元の問題を解決する必要があるため、再帰的関数です。このアプローチは状況によっては効果的に機能しますが、いくつかの制限があります。具体的には、大規模な配列を処理する場合、再帰的アルゴリズムによってコンピュータのスタック領域が使い果たされ、スタック オーバーフロー例外が発生する可能性があります。さらに、再帰的な関数呼び出しの追加のオーバーヘッドもアルゴリズムのパフォーマンス低下を引き起こす可能性があります。

したがって、場合によっては、非再帰的な実装メソッドを使用する方が適切な場合があります。この記事では、PHP を使用したクイックソートのための非再帰アルゴリズムを紹介します。

アルゴリズムの実装

最初に補助関数パーティションを定義します。これは、配列を 2 つのサブ配列に分割するために使用されます。1 つはベースライン値より小さいすべての要素を含み、もう 1 つはすべての要素を含みます。ベースライン値より大きい。

function partition(&$arr, $left, $right) {
    $pivot = $arr[$right]; // 选择最后一个元素作为基准值
    $i = $left - 1;
    for ($j = $left; $j < $right; $j++) {
        if ($arr[$j] < $pivot) {
            $i++;
            list($arr[$i], $arr[$j]) = array($arr[$j], $arr[$i]); // 交换i和j处的元素
        }
    }
    list($arr[$i + 1], $arr[$right]) = array($arr[$right], $arr[$i + 1]); // 将基准值放到正确的位置
    return $i + 1;
}

この関数は、配列の最後の要素をピボット値として選択し、配列要素を交換することによってピボット値より小さいすべての要素を配列の左側に配置します。このプロセスでは、変数 $i を使用して現在処理されている部分配列の添字を記録し、$j を使用して配列全体を走査します。ピボット値より小さい要素が見つかった場合は、$i を 1 つ右の位置に移動し、その要素を $i の位置に配置します。最後に、基本値を最終位置 $i 1 に配置します。

パーティション関数を使用すると、クイックソート アルゴリズムの非再帰バージョンを実装できるようになりました。このバージョンでは、スタックを使用して処理されるサブ配列を保存します。サブ配列を処理するときは、まずサブ配列の左右の境界をスタックに記録し、次にすべてのサブ配列がソートされるまでそれを 2 つの小さなサブ配列に分割し続けます。

function quick_sort(&$arr) {
    $stack = new SplStack(); // 使用SplStack实现栈
    $stack->push(count($arr) - 1); // 将整个数组的下标压入栈
    $stack->push(0);
    while (!$stack->isEmpty()) {
        $left = $stack->pop();
        $right = $stack->pop();
        $pivotIndex = partition($arr, $left, $right);
        if ($left < $pivotIndex - 1) {
            $stack->push($pivotIndex - 1);
            $stack->push($left);
        }
        if ($pivotIndex + 1 < $right) {
            $stack->push($right);
            $stack->push($pivotIndex + 1);
        }
    }
}

このバージョンのコードでは、SplStack クラスを使用してスタックを実装します。まず配列全体の左右の境界をスタックにプッシュし、次に継続的に左右の境界をスタックから削除し、部分配列を分割するパーティション関数に渡します。 left

このアルゴリズムの時間計算量は O(nlogn) です。すべての場合においてクイックソートの再帰バージョンほど高速ではありませんが、アルゴリズムのスペースの複雑さを大幅に軽減し、再帰関数呼び出しのオーバーヘッドを回避できます。 PHP で大規模な配列を迅速にソートする必要がある場合は、再帰バージョンのクイック ソートよりもこのアルゴリズムの方がニーズに適している可能性があります。

以上がPHP でクイックソート非再帰アルゴリズムを実装する方法の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。