PHP で実装される一般的な並べ替えアルゴリズムの概要、PHP 並べ替えアルゴリズム_PHP チュートリアル

phpで実装される一般的な並べ替えアルゴリズム、php並べ替えアルゴリズムの概要

この記事は、一般的な PHP ソート アルゴリズムをまとめたもので、アルゴリズムを設計する際に参考になります。今度はそれをみんなで共有して参考にしてください。詳細は以下の通りです

1. 挿入ソート

単語を使って簡単に説明します。たとえば、 $arr = array(4,2,4,6,3,6,1,7,9); のように、数値のグループを順番に並べ替えます。 したがって、まず、配列の 2 番目の要素を最初の要素と比較します。最初の要素が 2 番目の要素より大きい場合は、次に、配列の 3 番目の要素を取得して、最初の要素と比較します。 2 番目の要素が比較され、3 番目の要素が小さい場合は交換されます。等々。これは挿入ソートであり、その時間頻度は 1+2+...+(n-1)=(n^2)/2 です。したがって、その時間計算量は O(n^2) になります。

phpの実装コードは次のとおりです:

リーリー

2. 選択の並べ替え

選択の並べ替えが言語で記述されている場合は、次のようになります: $arr = array(4,3,5,2,1);

まず、最初の配列とそれ以降のすべての配列を比較し、最小の数値を見つけて、それを最初の配列と交換します (もちろん、最初の配列が最小である場合は、交換する必要はありません) 、次にループします。つまり、2 番目の数値を次の数値と比較し、最小の数値を見つけて、それを 2 番目の数値と交換する、というように繰り返します。つまり、毎回最小の残りの値を見つけます。 取得できます：初回、時間頻度は n です（最初のものと次の n-1 を比較し、最小のものを見つけ、それが最初のものであるかどうかを確認し、そうでない場合は交換します）未来、その後にマイナス 1 が続きます。 時間計算量も O(n^2);

phpの実装コードは次のとおりです:

リーリー

3. バブルソート
実際には、バブル ソートと選択ソートの間に大きな違いはありません。一番小さいものを見つけて左端に置きます。問題を順番に解決してください。違いは、バブル ソートでは位置がより多く交換されるのに対し、選択ソートでは最小の要素の添字が検索され、最も左の要素と位置が直接交換されることです。

PHP の実装コードは次のとおりです:

リーリー

4. クイックソート

クイックソートは、言語で説明すると、配列から値 $a を選択し、それが $a より大きい場合は配列の右側に配置され、その逆も同様です。それは配列の左側に配置されます。次に、left と right をそれぞれ再帰的に呼び出します。つまり、left と right を細分化し、最後に配列をマージします。

php はクイックソートを実装します:

リーリー

5. 並べ替え

実際、マージソートは分割とマージのアイデアです。これは、クイックソートのアイデアと共通しており、左側に 1 つの山、右側に 1 つの山を配置してからマージします。並べ替えは再帰によって行われます。 違いは何ですか?それらの違いは、考え方の本質的な違いでもあります。クイックソートの分割では、サイズ比較のために特定の値が選択されるため、それらが左右に分割されます。つまり、小さい山は左側に配置され、大きい山は右側に配置されます。次に、小さな左が left1 と right1 に細分化されます。 。 。 。並べ替えは、同様の再帰を実行することによって行われます。つまり、細分化し続けた場合、再帰終了時の left1 が最小値になります。

マージソートとは、配列を幾何学的に左右から最小粒度2または1に再帰的に分割し、サイズの比較を開始してからマージすることです。ここでの比較サイズは次のとおりです。息子の左側の要素が息子の右側の要素と比較され、ソートされて父親の左側または右側にマージされます。ここで、最後の 2 つの配列がそれぞれソートおよびマージされるまで、最初の左と右はそれぞれの順序のみを確認でき、配列全体の順序は、最後の比較を通じてまだ確認できません。本当の意味での左と右の仕分け。

リーリー

6. ヒープソート

この例では、fixDown 関数は特定のノードの下方調整を実装します。ここでのデフォルトは開始ノードが 1 であり、親ノードと子ノード間の関係を計算するのに便利です。

注:

開始ノードを1とした親子関係：親ノードk、子ノードは2K、2k+1子ノードj、親ノードはfloor(j/2)floorは切り捨て

開始ノードを0とした親子関係：親ノードk、子ノードは2K+1、2k+2 子ノードj、親ノードはfloor((j-1)/2)

パラメータ$kは調整ポイントの位置、$lenthは配列の長さであり、1から最後のノードまでの座標です。

リーリー

挿入ソート、バブルソート、選択ソート、シェルソート、クイックソート、マージソート、ヒープソート、SortUtilなどを含む、Java言語で実装されたさまざまなソート。
挿入ソート: package org.rut.util.algorithm.support;
import org.rut.util.algorithm.SortUtil;/*** @author Treeroot
* @since 2006-2-2
* @version 1.0*/ public class InsertSort は SortUtil.Sort{
/* (非 Javadoc)
* @org.rut.util.algorithm.SortUtil.Sort#sort(int[])*/public void sort(int[] data) を参照してください。 int temp;for(int i=1;ifor(int j=i;(j0)&&(data[j]SortUtil.swap(data,j,j-1);}}}}バブルソート: package org.rut.util.algorithm.support;
import org.rut.util.algorithm.SortUtil;/*** @著者 Treeroot
* @since 2006-2-2
* @version 1.0*/public class BubbleSort は SortUtil.Sort{
/* (非 Javadoc)
* を実装します @see org.rut.util.algorithm.SortUtil.Sort # sort(int[])*/public void sort(int[] data) {int temp;for(int i=0;ifor(int j=data.length-1; ji ;j--){

ソートアルゴリズム いわゆるソートは、レコードの文字列を、その中の 1 つまたはいくつかのキーワードのサイズに応じて昇順または降順に並べる操作です。
分類
コンピューター サイエンスで使用される並べ替えアルゴリズムは通常、次のように分類されます。
リスト (n) のサイズに応じて、計算複雑さ (最低、平均、最高のパフォーマンス)。一般的に、良いパフォーマンスは O です。 (n log n)、悪い動作は Ω(n2) です。ソートの理想的なパフォーマンスは O(n) です。抽象キー比較を 1 つだけ使用する並べ替えアルゴリズムでは、常に平均で少なくとも Ω(n log n) が必要です。
メモリ使用量 (および他のコンピューター リソースの使用量)
安定性: 安定した並べ替えアルゴリズムにより、等しいキー (つまり値) に従ってレコードの相対的な順序が維持されます。つまり、ソート アルゴリズムは安定しています。つまり、キーが等しい 2 つのレコード R と S があり、元のシーケンスで R が S の前に出現する場合、ソートされたシーケンスでも R が S の前になります。
一般的なメソッド: 挿入、交換、選択、マージなど。交換ソートにはバブル ソートとクイックソートが含まれます。選択ソートには、シェーカー ソートとヒープ ソートが含まれます。
整数など、等しい要素が区別できない場合、安定性は問題になりません。ただし、次の数値のペアが最初の桁でソートされると仮定します。
(4, 1) (3, 1) (3, 7) (5, 6)
この場合、2 つの異なる結果を生成することが可能です。1 つは、等しいキー値に従って相対順序を維持することです。もう 1 つは、等しいキー値に従って相対順序を維持することです。1 つはそうではありません:
(3, 1) (3, 7) (4, 1) (5, 6) (順序を維持)
(3, 7) (3) , 1) (4, 1) (5, 6) (順序変更)
不安定な並べ替えアルゴリズムでは、等しいキー値内のレコードの相対的な順序が変更される可能性がありますが、安定した並べ替えアルゴリズムではこれが行われません。不安定な並べ替えアルゴリズムは特に安定していると見なすことができます。これを行う 1 つの方法は、キー比較を人為的に拡張して、他の点では同一のキーを持つ 2 つのオブジェクト間の比較が決定され、元のデータ順序のエントリをタイブレーカーとして使用することです。ただし、この順序には通常、追加のスペース オーバーヘッドが含まれることに注意してください。
並べ替えアルゴリズムのリスト
この表では、n は並べ替えられるレコードの数、k は異なるキー値の数です。
安定
バブルソート (バブルソート) — O(n2)
カクテルソート (双方向バブルソート) — O(n2)
挿入ソート (挿入ソート) — O(n2)
バケットソート (バケットソート) — O(n ); O(k) の追加メモリが必要
ソートのカウント — O(n+k); 追加のメモリが必要です
マージ ソート — O(n) の追加メモリが必要です
配置マージ ソート — O(n2)
バイナリ ツリー ソート (バイナリ ツリー ソート) — O(n) の追加メモリが必要
ピジョンホール ソート — O(n+k) の追加メモリが必要
基数ソート — O(n·k); には O(n) の追加メモリが必要です
Gnome ソート — O(n2)
ライブラリのソート — O(n log n) には、高い確率で (1+ε)n の追加メモリが必要です
不安定
選択ソート — O(n2)
シェルソート ) — O(n log n) 現在の最良のバージョンを使用する場合
コムソート — O(n log n)
ヒープソート (heapsort) — O(n log n)
...本文>>