PHPでクイックソートを実装する方法

php メソッドによるクイック ソートの実装: 最初に PHP サンプル ファイルを作成し、次に Exchange 関数と main 関数を作成し、次に下位サブテーブルと上位サブテーブルを再帰的に並べ替え、最後に QuickSort アルゴリズムを呼び出します。

# 推奨: 「

PHP ビデオ チュートリアル」

基本的な考え方:

クイックソートはバブル ソートを改良したものです。彼の基本的なアイデアは、1 回のソートでソート対象のレコードを 2 つの独立した部分に分割することです。一方の部分のキーワードは、レコードのもう一方の部分のキーワードよりも小さいため、レコードの 2 つの部分をすばやく別々にソートできるようになります。全体 並べ替えプロセスは、シーケンス全体を順序付けるという目的を達成するために再帰的に実行できます。

基本的なアルゴリズムの手順:

例:

現在並べ替えるレコードが次の場合:

6   2   7   3   8   9

最初のステップ、変数 $low を作成してレコード内の最初のレコードを指し、$high で最後のレコードを指し、ピボット値として $pivot を作成して、並べ替えるレコードの最初の要素 (必ずしも最初の要素であるとは限りません)

$low = 0;
$high = 5;
$pivot = 6;

2 番目のステップは、$pivot より小さいすべての数値を $pivot の左側に移動することです。これにより、$high から始めて 6 より小さい数値を探し始めることができます。右から左に変数 $high の値を減分し続けると、添字 3 の最初のデータが 6 より小さいことがわかり、データ 3 を添字 0 の位置 ($low が指す位置) に移動します。添字 0 のデータ 6 を一番下に移動します。マーク 3、最初の比較を完了します:

3   2   7   6   8   9

//这时候,$high 减小为 3
$low = 0;
$high = 3;
$pivot = 6;

3 番目のステップ、2 番目の比較を開始します。今回は、より大きい比較を探す必要があります。 $pivot、前から後ろまで見なければなりません。変数 $low をインクリメントすると、添字 2 のデータが $pivot より大きい最初のデータであることがわかります。そのため、添字 2 ($low が指す位置) のデータ 7 と添字 3 ($low が指す位置) のデータ 7 を使用します。 6 個のデータが交換され、データの状態は次の表のようになります:

3   2   6   7   8   9

//这时候,$high 减小为 3
$low = 2;
$high = 3;
$pivot = 6;

2 番目と 3 番目のステップを完了することをサイクルの完了と呼びます。

4 番目のステップ (つまり、次のサイクルの開始) は、2 番目のステップのプロセス実行を模倣します。

5 番目のステップは、3 番目のステップのプロセスを模倣することです。

2 番目のループを実行した後のデータのステータスは次のとおりです:

3   2   6   7   8   9

//这时候,$high 减小为 3
$low = 2;
$high = 2;
$pivot = 6;

このステップでは、$low と $high が「一致」していることがわかります。両方とも添え字 2 を指しています。これで、最初の比較は終了です。結果は次のようになります。$pivot(=6) の左側の数値はすべてそれより小さく、$pivot の右側の数値はすべてそれより大きくなります。

次に、$pivot と {3, 8, 9} の両側のデータ {3, 2} と {7, 8, 9} をグループ化し、グループ化できなくなるまで上記のプロセスを個別に実行します。 。

注: クイック ソートの最初のパスでは最終結果が直接得られず、k より大きい数値と k より小さい数値を k の両側に分割するだけです。最終結果を得るには、添字 2 の両側の配列に対してこの手順を再度実行し、正しい結果を得るために配列が分解できなくなる (データが 1 つだけになる) まで配列を分解する必要があります。

アルゴリズム実装:

//交换函数
function swap(array &$arr,$a,$b){
    $temp = $arr[$a];
    $arr[$a] = $arr[$b];
    $arr[$b] = $temp;
}

//主函数：
function QuickSort(array &$arr){
    $low = 0;
    $high = count($arr) - 1;
    QSort($arr,$low,$high);
}

main 関数では、クイック ソートの最初のパスで配列全体がソートされるため、開始点は $low=0,$high=count($arr) になります。 - 1.

QSort() 関数は再帰呼び出しプロセスであるため、カプセル化されます。

function QSort(array &$arr,$low,$high){
    //当 $low >= $high 时表示不能再进行分组，已经能够得出正确结果了
    if($low < $high){
        $pivot = Partition($arr,$low,$high);  //将$arr[$low...$high]一分为二，算出枢轴值
        QSort($arr,$low,$pivot - 1);	//对低子表（$pivot左边的记录）进行递归排序
        QSort($arr,$pivot + 1,$high);	//对高子表（$pivot右边的记录）进行递归排序
    }
}

上記の QSort() 関数から、Partition() 関数が全体のコアであることがわかります。 code 。この関数の機能は、最初のキーワードを選択するなど、キーワードの 1 つを選択することであるためです。次に、左側の値がそれより小さく、右側の値がそれより大きくなるように、特定の位置に配置するように最善を尽くします。このようなキーワードをピボットと呼びます。

コードに直接移動します:

//选取数组当中的一个关键字，使得它处于数组某个位置时，左边的值比它小，右边的值比它大，该关键字叫做枢轴
//使枢轴记录到位，并返回其所在位置
function Partition(array &$arr,$low,$high){
    $pivot = $arr[$low];   //选取子数组第一个元素作为枢轴
    while($low < $high){  //从数组的两端交替向中间扫描（当 $low 和 $high 碰头时结束循环）
        while($low < $high && $arr[$high] >= $pivot){
            $high --;
        }
        swap($arr,$low,$high);	//终于遇到一个比$pivot小的数，将其放到数组低端

        while($low < $high && $arr[$low] <= $pivot){
            $low ++;
        }
        swap($arr,$low,$high);	//终于遇到一个比$pivot大的数，将其放到数组高端
    }
    return $low;   //返回high也行，毕竟最后low和high都是停留在pivot下标处
}

結合されたコード全体は次のとおりです:

function swap(array &$arr,$a,$b){
    $temp = $arr[$a];
    $arr[$a] = $arr[$b];
    $arr[$b] = $temp;
}

function Partition(array &$arr,$low,$high){
    $pivot = $arr[$low];   //选取子数组第一个元素作为枢轴
    while($low < $high){  //从数组的两端交替向中间扫描
        while($low < $high && $arr[$high] >= $pivot){
            $high --;
        }
        swap($arr,$low,$high);	//终于遇到一个比$pivot小的数，将其放到数组低端
        while($low < $high && $arr[$low] <= $pivot){
            $low ++;
        }
        swap($arr,$low,$high);	//终于遇到一个比$pivot大的数，将其放到数组高端
    }
    return $low;   //返回high也行，毕竟最后low和high都是停留在pivot下标处
}

function QSort(array &$arr,$low,$high){
    if($low < $high){
        $pivot = Partition($arr,$low,$high);  //将$arr[$low...$high]一分为二，算出枢轴值
        QSort($arr,$low,$pivot - 1);   //对低子表进行递归排序
        QSort($arr,$pivot + 1,$high);  //对高子表进行递归排序
    }
}

function QuickSort(array &$arr){
    $low = 0;
    $high = count($arr) - 1;
    QSort($arr,$low,$high);
}

アルゴリズムを呼び出します:

$arr = array(9,1,5,8,3,7,4,6,2);
QuickSort($arr);
var_dump($arr);

複雑性分析:

最適な状況では、つまり、数値軸が配列全体の中央の値になるように選択された場合、配列は毎回 2 つの半分に分割されます。したがって、最適な場合の時間計算量は O(nlogn) です (ヒープ ソートおよびマージ ソートと同じ)。

最悪の場合、並べ替えるシーケンスが順方向または逆順の場合、ピボットを選択するときにエッジ データのみを選択できます。各分割では、前の分割よりもレコードが 1 つ少なくなります。 1 つのパーティションが空の場合、このケースの最終的な時間計算量は O(n^2) です。

最良のケースと最悪のケースに基づくと、平均時間計算量は O(nlogn) です。

クイックソートは不安定なソート方法です。

クイック ソートは比較的高度なソートであるため、20 世紀のトップ 10 アルゴリズムの 1 つとしてリストされています。 。 。 。これほど素晴らしいアルゴリズムがあるのに、そこから学ばないのはなぜでしょうか?

このアルゴリズムはすでに非常に優れていますが、上記のアルゴリズム プログラムにはまだ改善の余地があります。

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