PHP の通常のソート アルゴリズムと二分探索
- WBOYオリジナル
- 2016-06-13 12:29:13813ブラウズ
PHP で一般的に使用されるソート アルゴリズムと二分探索
1: マージ ソート
2 つの順序付けされたシーケンスを 1 つの順序付けされたシーケンスにマージします。これを「Merge」と呼びます。
マージソートは、マージのアイデアを使用してシーケンスをソートすることです。特定の実装に応じて、マージソートには「トップダウン」と「ボトムアップ」の 2 つの方法が含まれます。
1. 下から上へのマージソート: ソートするシーケンスを長さ 1 の複数のサブシーケンスに分割し、これらのシーケンスをペアでマージします。いくつかの長さ 2 の順序付きシーケンスを取得し、これらのシーケンスをペアでマージし、長さ 4 の順序付きシーケンスをいくつか取得し、それらを 1 つのシーケンスに直接マージします。このようにして、希望するソート結果が得られます
2. トップダウンマージソート: 「ボトムアップ」からのソートの逆方向です。基本的には 3 つのステップで構成されます:
① 分解 - 現在の区間を 2 つに分割します。つまり、分割点 Mid = (低 高)/2 を見つけます。
② 解く - 2 つの部分区間 a[ low ...mid] と a[mid 1...high] マージソート用。再帰の最終条件は、部分区間の長さが 1 であることです。
③ マージ -- ソートされた 2 つのサブ間隔 a[low...mid] と a[mid 1...high] を順序付き間隔 a[low...high] にマージします。
<span style="color: #008000;"> /*</span><span style="color: #008000;">* * 归并排序实现过程 * @param Array $arr 待排序的区间数组 * @param Int $start 第一个区间数组的起始位置 * @param Int $mid 第一个区间数组的结束位置，第二个区间数组的起始位置 * @param Int $end 第二个区间数组的结束位置 * @return void </span><span style="color: #008000;">*/</span> <span style="color: #0000ff;">function</span> merge(<span style="color: #0000ff;">Array</span> &<span style="color: #800080;">$arr</span>,<span style="color: #800080;">$start</span>,<span style="color: #800080;">$mid</span>,<span style="color: #800080;">$end</span><span style="color: #000000;">) { </span><span style="color: #800080;">$i</span> = <span style="color: #800080;">$start</span><span style="color: #000000;">; </span><span style="color: #800080;">$j</span> = <span style="color: #800080;">$mid</span> + 1<span style="color: #000000;">; </span><span style="color: #800080;">$k</span> = 0<span style="color: #000000;">; </span><span style="color: #0000ff;">while</span>(<span style="color: #800080;">$i</span> <= <span style="color: #800080;">$mid</span> && <span style="color: #800080;">$j</span> <= <span style="color: #800080;">$end</span><span style="color: #000000;">) { </span><span style="color: #0000ff;">if</span> (<span style="color: #800080;">$arr</span>[<span style="color: #800080;">$i</span>] <= <span style="color: #800080;">$arr</span>[<span style="color: #800080;">$j</span>]) <span style="color: #008000;">//</span><span style="color: #008000;">判断两个区间数组各自数据的大小，并归类</span> <span style="color: #800080;">$tmp</span>[<span style="color: #800080;">$k</span>++] = <span style="color: #800080;">$arr</span>[<span style="color: #800080;">$i</span>++<span style="color: #000000;">]; </span><span style="color: #0000ff;">else</span> <span style="color: #800080;">$tmp</span>[<span style="color: #800080;">$k</span>++] = <span style="color: #800080;">$arr</span>[<span style="color: #800080;">$j</span>++<span style="color: #000000;">]; } </span><span style="color: #0000ff;">while</span>(<span style="color: #800080;">$i</span> <= <span style="color: #800080;">$mid</span>) <span style="color: #008000;">//</span><span style="color: #008000;">防止第一个区间有一个数据没有归类</span> <span style="color: #800080;">$tmp</span>[<span style="color: #800080;">$k</span>++] = <span style="color: #800080;">$arr</span>[<span style="color: #800080;">$i</span>++<span style="color: #000000;">]; </span><span style="color: #0000ff;">while</span>(<span style="color: #800080;">$j</span> <= <span style="color: #800080;">$end</span>) <span style="color: #008000;">//</span><span style="color: #008000;">防止第二个区间有一个数据没有归类</span> <span style="color: #800080;">$tmp</span>[<span style="color: #800080;">$k</span>++] = <span style="color: #800080;">$arr</span>[<span style="color: #800080;">$j</span>++<span style="color: #000000;">]; </span><span style="color: #008000;">//</span><span style="color: #008000;"> 将排序后的元素，全部都整合到数组arr中。</span> <span style="color: #0000ff;">for</span> (<span style="color: #800080;">$i</span> = 0; <span style="color: #800080;">$i</span> < <span style="color: #800080;">$k</span>; ++<span style="color: #800080;">$i</span><span style="color: #000000;">) </span><span style="color: #800080;">$arr</span>[<span style="color: #800080;">$start</span> + <span style="color: #800080;">$i</span>] = <span style="color: #800080;">$tmp</span>[<span style="color: #800080;">$i</span><span style="color: #000000;">]; } </span><span style="color: #008000;">/*</span><span style="color: #008000;">* * 归并排序(从上往下) * @param Array $arr 待排序的数组 * @param Int $start 数组起始位置 * @param Int end 数组结束位置 * @return void </span><span style="color: #008000;">*/</span> <span style="color: #0000ff;">function</span> merge_sort(<span style="color: #0000ff;">Array</span> &<span style="color: #800080;">$arr</span>,<span style="color: #800080;">$start</span>=0,<span style="color: #800080;">$end</span>=0<span style="color: #000000;">) { </span><span style="color: #800080;">$len</span> = <span style="color: #008080;">count</span>(<span style="color: #800080;">$arr</span><span style="color: #000000;">); </span><span style="color: #0000ff;">if</span>(<span style="color: #800080;">$len</span> <= 1 || <span style="color: #800080;">$start</span> >= <span style="color: #800080;">$end</span><span style="color: #000000;">) </span><span style="color: #0000ff;">return</span> <span style="color: #800080;">$arr</span><span style="color: #000000;">; </span><span style="color: #800080;">$mid</span> = <span style="color: #008080;">intval</span>((<span style="color: #800080;">$start</span> + <span style="color: #800080;">$end</span>) / 2); <span style="color: #008000;">//</span><span style="color: #008000;">分区间</span><span style="color: #000000;"> merge_sort(</span><span style="color: #800080;">$arr</span>,<span style="color: #800080;">$start</span>,<span style="color: #800080;">$mid</span><span style="color: #000000;">); merge_sort(</span><span style="color: #800080;">$arr</span>,<span style="color: #800080;">$mid</span>+1,<span style="color: #800080;">$end</span><span style="color: #000000;">); merge(</span><span style="color: #800080;">$arr</span>,<span style="color: #800080;">$start</span>,<span style="color: #800080;">$mid</span>,<span style="color: #800080;">$end</span><span style="color: #000000;">); }<br><br> //从下往上与此刚好相反</span>
2: クイックソート
1 回のソートパスでソート対象のデータを 2 つの独立した部分に分割します。すべてのデータが 1 つの部分にある方が優れています。すべてのデータは小さい必要があり、この方法に従ってデータの 2 つの部分がすばやく並べ替えられるため、並べ替えプロセス全体が再帰的に実行され、データ全体が順序付けされたシーケンスになります。クイックソートアルゴリズムの主な演算時間は約O(log2n)、サブ領域関数の演算時間は約O(n)であるため、合計時間計算量はO(nlog2n)となり、バブルソートよりも明らかに優れています。 O(n2) ただし、アルゴリズムの利点は絶対的なものではありません。試行分析によると、元のファイルのキーワードが整っていれば、クイック ソートの時間計算量は O(n2) になります。この場合、クイック ソートは高速ではありません。この場合、バブル ソートは O(n) であり、非常に高速です。元のファイル レコードのキーワードの順序が崩れている場合のさまざまなソート方法の中で、クイック ソートが最適なソート方法と考えられます。
<span style="color: #008000;"> /*</span><span style="color: #008000;">* * 快速排序 * @param Array $arr 待排序的数组 * @return Array 排序后的数组 </span><span style="color: #008000;">*/</span> <span style="color: #0000ff;">function</span> quick_sort(<span style="color: #0000ff;">Array</span> <span style="color: #800080;">$arr</span><span style="color: #000000;">) { </span><span style="color: #800080;">$len</span> = <span style="color: #008080;">count</span>(<span style="color: #800080;">$arr</span><span style="color: #000000;">); </span><span style="color: #0000ff;">if</span>(<span style="color: #800080;">$len</span> <= 1<span style="color: #000000;">) </span><span style="color: #0000ff;">return</span> <span style="color: #800080;">$arr</span><span style="color: #000000;">; </span><span style="color: #800080;">$tmp</span> = <span style="color: #800080;">$arr</span>[0<span style="color: #000000;">]; </span><span style="color: #800080;">$left_arr</span> =<span style="color: #000000;"> []; </span><span style="color: #800080;">$right_arr</span> =<span style="color: #000000;"> []; </span><span style="color: #0000ff;">for</span>(<span style="color: #800080;">$i</span> = 1; <span style="color: #800080;">$i</span> < <span style="color: #800080;">$len</span>; ++<span style="color: #800080;">$i</span><span style="color: #000000;">) { </span><span style="color: #0000ff;">if</span>(<span style="color: #800080;">$arr</span>[<span style="color: #800080;">$i</span>] <= <span style="color: #800080;">$tmp</span><span style="color: #000000;">) </span><span style="color: #800080;">$left_arr</span>[] = <span style="color: #800080;">$arr</span>[<span style="color: #800080;">$i</span><span style="color: #000000;">]; </span><span style="color: #0000ff;">else</span> <span style="color: #800080;">$right_arr</span>[] = <span style="color: #800080;">$arr</span>[<span style="color: #800080;">$i</span><span style="color: #000000;">]; } </span><span style="color: #008000;">//</span><span style="color: #008000;">递归分类</span> <span style="color: #800080;">$left_arr</span> = quick_sort(<span style="color: #800080;">$left_arr</span><span style="color: #000000;">); </span><span style="color: #800080;">$right_arr</span> = quick_sort(<span style="color: #800080;">$right_arr</span><span style="color: #000000;">); </span><span style="color: #0000ff;">return</span> <span style="color: #008080;">array_merge</span>(<span style="color: #800080;">$left_arr</span>,<span style="color: #0000ff;">array</span>(<span style="color: #800080;">$tmp</span>),<span style="color: #800080;">$right_arr</span><span style="color: #000000;">); } </span>3: バブルソート
2 つのデータ要素の順序がペアごとにソートされるデータ要素のサイズを比較します。逆の場合、逆の順序のデータ要素がなくなるまで交換されます。このアルゴリズムの時間計算量は O(n2) です。ただし、元のキーワード シーケンスが整っていれば、比較は 1 回だけ実行され、時間計算量は O(n) になります。
<span style="color: #008000;"> /*</span><span style="color: #008000;">* * 冒泡排序 * @param Array $arr 待排序的数组 * @return Array 排序后的数组 </span><span style="color: #008000;">*/</span> <span style="color: #0000ff;">function</span> bubble_sort(<span style="color: #0000ff;">Array</span> <span style="color: #800080;">$arr</span><span style="color: #000000;">) { </span><span style="color: #800080;">$len</span> = <span style="color: #008080;">count</span>(<span style="color: #800080;">$arr</span><span style="color: #000000;">); </span><span style="color: #0000ff;">for</span>(<span style="color: #800080;">$i</span> = 0; <span style="color: #800080;">$i</span> < <span style="color: #800080;">$len</span>; ++<span style="color: #800080;">$i</span><span style="color: #000000;">) { </span><span style="color: #0000ff;">for</span>(<span style="color: #800080;">$j</span> = <span style="color: #800080;">$len</span> - 1; <span style="color: #800080;">$j</span> > <span style="color: #800080;">$i</span>; --<span style="color: #800080;">$j</span><span style="color: #000000;">) { </span><span style="color: #0000ff;">if</span>(<span style="color: #800080;">$arr</span>[<span style="color: #800080;">$j</span>] < <span style="color: #800080;">$arr</span>[<span style="color: #800080;">$j</span>-1<span style="color: #000000;">]) { </span><span style="color: #800080;">$tmp</span> = <span style="color: #800080;">$arr</span>[<span style="color: #800080;">$j</span><span style="color: #000000;">]; </span><span style="color: #800080;">$arr</span>[<span style="color: #800080;">$j</span>] = <span style="color: #800080;">$arr</span>[<span style="color: #800080;">$j</span>-1<span style="color: #000000;">]; </span><span style="color: #800080;">$arr</span>[<span style="color: #800080;">$j</span>-1] = <span style="color: #800080;">$tmp</span><span style="color: #000000;">; } } } </span><span style="color: #0000ff;">return</span> <span style="color: #800080;">$arr</span><span style="color: #000000;">; }</span>4: 挿入ソート
毎回、以前にソートされた配列にソート対象のデータ要素を挿入します。こうすることで、配列は常に順序どおりになります。ソートされるすべてのデータ要素が挿入されます。 n 個の要素のシーケンスを昇順にソートすることが目的の場合、挿入ソートを使用する最良のケースと最悪のケースがあります。最良の場合は、シーケンスがすでに昇順になっている場合です。この場合、実行する必要がある比較演算は (n-1) 回のみ必要です。最悪のシナリオは、シーケンスが降順に配置されているため、この時点で合計 n(n-1)/2 の比較を実行する必要があることです。挿入ソートの代入演算は、比較演算の回数 + (n-1) 回です。平均すると、挿入ソート アルゴリズムの時間計算量は O(n^2) です。したがって、挿入ソートは、比較的大量のデータを扱うアプリケーションのソートには適していません。ただし、並べ替える必要があるデータの量が少ない場合 (たとえば、大きさが 1,000 未満である場合)、挿入並べ替えが依然として適切な選択です
<span style="color: #008000;"> /*</span><span style="color: #008000;">* * 插入排序 * @param Array $arr 待排序的数组 * @return Array 排序后的数组 </span><span style="color: #008000;">*/</span> <span style="color: #0000ff;">function</span> insert_sort(<span style="color: #0000ff;">Array</span> <span style="color: #800080;">$arr</span><span style="color: #000000;">) { </span><span style="color: #800080;">$len</span> = <span style="color: #008080;">count</span>(<span style="color: #800080;">$arr</span><span style="color: #000000;">); </span><span style="color: #0000ff;">for</span>(<span style="color: #800080;">$i</span> = 1; <span style="color: #800080;">$i</span> < <span style="color: #800080;">$len</span>; ++<span style="color: #800080;">$i</span><span style="color: #000000;">) { </span><span style="color: #800080;">$tmp</span> = <span style="color: #800080;">$arr</span>[<span style="color: #800080;">$i</span><span style="color: #000000;">]; </span><span style="color: #800080;">$j</span> = <span style="color: #800080;">$i</span> - 1<span style="color: #000000;">; </span><span style="color: #008000;">//</span><span style="color: #008000;">把数据插入到合适的位置(交换位置)</span> <span style="color: #0000ff;">while</span>(<span style="color: #800080;">$j</span> >= 0 && <span style="color: #800080;">$arr</span>[<span style="color: #800080;">$j</span>] > <span style="color: #800080;">$tmp</span><span style="color: #000000;">) { </span><span style="color: #800080;">$arr</span>[<span style="color: #800080;">$j</span>+1] = <span style="color: #800080;">$arr</span>[<span style="color: #800080;">$j</span><span style="color: #000000;">]; </span><span style="color: #800080;">$arr</span>[<span style="color: #800080;">$j</span>] = <span style="color: #800080;">$tmp</span><span style="color: #000000;">; </span>--<span style="color: #800080;">$j</span><span style="color: #000000;">; } } </span><span style="color: #0000ff;">return</span> <span style="color: #800080;">$arr</span><span style="color: #000000;">; }</span>
5 : 選択ソート
各パスは、ソートされるデータ要素から最小 (または最大) の要素を選択し、ソートされるすべてのデータ要素が配置されるまで、それをソートされたシーケンスの最後に配置します。時間計算量は o(n2)、不安定なソート、小規模に適しています
<span style="color: #008000;"> /*</span><span style="color: #008000;">* * 选择排序 * @param Array $arr 待排序的数组 * @return Array 排序后的数组 </span><span style="color: #008000;">*/</span> <span style="color: #0000ff;">function</span> select_sort(<span style="color: #0000ff;">Array</span> <span style="color: #800080;">$arr</span><span style="color: #000000;">) { </span><span style="color: #800080;">$len</span> = <span style="color: #008080;">count</span>(<span style="color: #800080;">$arr</span><span style="color: #000000;">); </span><span style="color: #0000ff;">for</span>(<span style="color: #800080;">$i</span> = 0; <span style="color: #800080;">$i</span> < <span style="color: #800080;">$len</span>; ++<span style="color: #800080;">$i</span><span style="color: #000000;">) { </span><span style="color: #800080;">$k</span> = <span style="color: #800080;">$i</span>; <span style="color: #008000;">//</span><span style="color: #008000;">标记当前索引</span> <span style="color: #0000ff;">for</span>(<span style="color: #800080;">$j</span> = <span style="color: #800080;">$i</span> + 1; <span style="color: #800080;">$j</span> < <span style="color: #800080;">$len</span>; ++<span style="color: #800080;">$j</span><span style="color: #000000;">) { </span><span style="color: #0000ff;">if</span>(<span style="color: #800080;">$arr</span>[<span style="color: #800080;">$j</span>] < <span style="color: #800080;">$arr</span>[<span style="color: #800080;">$k</span><span style="color: #000000;">]) </span><span style="color: #800080;">$k</span> = <span style="color: #800080;">$j</span>; <span style="color: #008000;">//</span><span style="color: #008000;">获取当前最小值索引</span> <span style="color: #0000ff;">if</span>(<span style="color: #800080;">$k</span> != <span style="color: #800080;">$i</span>) <span style="color: #008000;">//</span><span style="color: #008000;">如果最小值得索引发生变化</span><span style="color: #000000;"> { </span><span style="color: #800080;">$tmp</span> = <span style="color: #800080;">$arr</span>[<span style="color: #800080;">$i</span><span style="color: #000000;">]; </span><span style="color: #800080;">$arr</span>[<span style="color: #800080;">$i</span>] = <span style="color: #800080;">$arr</span>[<span style="color: #800080;">$k</span><span style="color: #000000;">]; </span><span style="color: #800080;">$arr</span>[<span style="color: #800080;">$k</span>] = <span style="color: #800080;">$tmp</span><span style="color: #000000;">; } } } </span><span style="color: #0000ff;">return</span> <span style="color: #800080;">$arr</span><span style="color: #000000;">; }</span>6: 二分探索
<span style="color: #008000;"> /*</span><span style="color: #008000;">* * 二分查找 * @param Array $arr 待查找的数组 * @param Int $key 要查找的关键字 * @return Int </span><span style="color: #008000;">*/</span> <span style="color: #0000ff;">function</span> bin_search(<span style="color: #0000ff;">Array</span> <span style="color: #800080;">$arr</span>,<span style="color: #800080;">$key</span><span style="color: #000000;">) { </span><span style="color: #800080;">$high</span> = <span style="color: #008080;">count</span>(<span style="color: #800080;">$arr</span><span style="color: #000000;">); </span><span style="color: #0000ff;">if</span>(<span style="color: #800080;">$high</span> <= 0<span style="color: #000000;">) </span><span style="color: #0000ff;">return</span> 0<span style="color: #000000;">; </span><span style="color: #800080;">$low</span> = 0<span style="color: #000000;">; </span><span style="color: #0000ff;">while</span>(<span style="color: #800080;">$low</span> <= <span style="color: #800080;">$high</span><span style="color: #000000;">) { </span><span style="color: #008000;">//</span><span style="color: #008000;">当前查找区间arr[low..high]非空</span> <span style="color: #800080;">$mid</span>=<span style="color: #008080;">intval</span>((<span style="color: #800080;">$low</span> + <span style="color: #800080;">$high</span>) / 2<span style="color: #000000;">); </span><span style="color: #0000ff;">if</span>(<span style="color: #800080;">$arr</span>[<span style="color: #800080;">$mid</span>] == <span style="color: #800080;">$key</span><span style="color: #000000;">) </span><span style="color: #0000ff;">return</span> <span style="color: #800080;">$mid</span>; <span style="color: #008000;">//</span><span style="color: #008000;">查找成功返回</span> <span style="color: #0000ff;">if</span>(<span style="color: #800080;">$arr</span>[<span style="color: #800080;">$mid</span>] > <span style="color: #800080;">$key</span><span style="color: #000000;">) </span><span style="color: #800080;">$high</span> = <span style="color: #800080;">$mid</span> - 1; <span style="color: #008000;">//</span><span style="color: #008000;">继续在arr[low..mid-1]中查找</span> <span style="color: #0000ff;">else</span> <span style="color: #800080;">$low</span> = <span style="color: #800080;">$mid</span> + 1; <span style="color: #008000;">//</span><span style="color: #008000;">继续在arr[mid+1..high]中查找</span><span style="color: #000000;"> } </span><span style="color: #0000ff;">return</span> 0; <span style="color: #008000;">//</span><span style="color: #008000;">当low>high时表示查找区间为空，查找失败</span><span style="color: #000000;"> } </span><span style="color: #800080;">$arr</span> = <span style="color: #0000ff;">array</span>(1,2,4,6,10,40,50,80,100,110<span style="color: #000000;">); </span><span style="color: #0000ff;">echo</span> bin_search(<span style="color: #800080;">$arr</span>,80);
声明：
この記事の内容はネチズンが自主的に寄稿したものであり、著作権は原著者に帰属します。このサイトは、それに相当する法的責任を負いません。盗作または侵害の疑いのあるコンテンツを見つけた場合は、admin@php.cn までご連絡ください。