PHP でよく使用されるソート アルゴリズムとバイナリ検索、PHP アルゴリズム バイナリ メソッド_PHP チュートリアル

PHPでよく使われるソートアルゴリズムと二分探索、PHPアルゴリズムバイナリメソッド

1: マージソート

2 つの順序付けられたシーケンスを 1 つの順序付けられたシーケンスにマージします。これを「マージ」と呼びます。
マージソートは、マージのアイデアを使用してシーケンスをソートすることです。特定の実装に応じて、マージソートには「上から下へ」と「下から上へ」という 2 つの方法が含まれます。

1. 下から上へのソートのマージ: ソートするシーケンスを長さ 1 の複数のサブシーケンスに分割し、これらのシーケンスをペアとしてマージして、長さ 2 の順序付けされたシーケンスをいくつか取得します。これらのシーケンスをペアでマージし、長さ 4 の順序付けられたシーケンスをいくつか取得し、それらが 1 つのシーケンスに直接マージされるまでペアでマージします。このようにして、希望する並べ替え結果が得られます

2. トップダウンのマージソート: 「ボトムアップ」からのソートの逆方向です。これには基本的に 3 つのステップが含まれます:
① 分解 - 現在の区間を 2 つに分割します。つまり、分割点 Mid = (low + high)/2 を見つけます。
② 解決策 - 2 つのサブ区間 a[low ...mid] と a[mid+1...high] がマージされ、ソートされます。再帰の最終条件は、部分区間の長さが 1 であることです。
③ マージ -- 並べ替えられた 2 つのサブ間隔 a[low...mid] と a[mid+1...high] を、順序付けられた間隔 a[low...high] にマージします。

2: クイックソート

1 回の並べ替えパスで、並べ替えるデータを 2 つの独立した部分に分割します。次に、この方法を使用して、データの 2 つの部分を別々に並べ替えます。全体の並べ替えプロセス データ全体が順序付けされたシーケンスになるように再帰的に実行できます。クイックソートアルゴリズムの主な演算時間は約O(log2n)、サブ領域関数の演算時間は約O(n)であるため、合計時間計算量はO(nlog2n)となり、バブルソートよりも明らかに優れています。 O(n2) ただし、アルゴリズムの利点は絶対的なものではありません。試行分析によると、元のファイルのキーワードが整っていれば、クイック ソートの時間計算量は O(n2) になります。この場合、クイック ソートは高速ではありません。この場合、バブル ソートは O(n) であり、非常に高速です。元のファイル レコードのキーワードの順序が崩れている場合のさまざまなソート方法の中で、クイック ソートが最適なソート方法と考えられます。

3: バブルソート

ペアごとにソートするデータ要素のサイズを比較し、2 つのデータ要素の順序が逆転していることが判明した場合は、逆転したデータ要素がなくなるまでそれらを入れ替えます。このアルゴリズムの時間計算量は O(n²) です。ただし、元のキーワード シーケンスが整っていれば、比較は 1 回だけ実行され、時間計算量は O(n) になります。

4: 挿入ソート

並べ替えるデータ要素を毎回、以前に並べ替えた配列に挿入します。これにより、並べ替えられるすべてのデータ要素が挿入されるまで配列が正しい順序のままになります。 n 個の要素のシーケンスを昇順でソートすることが目的の場合、挿入ソートを使用する最良のケースと最悪のケースがあります。最良の場合は、シーケンスがすでに昇順になっている場合です。この場合、実行する必要がある比較演算は (n-1) 回のみ必要です。最悪のシナリオは、シーケンスが降順に配置されているため、この時点で合計 n(n-1)/2 の比較を実行する必要があることです。挿入ソートの代入演算は、比較演算の回数 + (n-1) 回です。平均すると、挿入ソート アルゴリズムの時間計算量は O(n^2) です。したがって、挿入ソートは、比較的大量のデータを扱うアプリケーションのソートには適していません。ただし、ソートする必要があるデータの量が少ない場合 (たとえば、大きさが 1,000 未満である場合)、挿入ソートは依然として良い選択です

5: 選択ソート

各パスでは、並べ替えられるデータ要素から最小 (または最大) の要素が選択され、並べ替えられるすべてのデータ要素が並べ替えられるまで、並べ替えられたシーケンスの最後に順序が配置されます。時間計算量は o(n2)、不安定なソート、小規模に適しています

6: 二分探索