この記事では、PHP ソート アルゴリズムのストレート挿入ソートを主に紹介し、サンプルの形式でストレート挿入ソート アルゴリズムの実装テクニックを詳細に分析します。 PHP ソート アルゴリズムのストレート挿入ソートについて説明します。参考のために皆さんと共有してください。詳細は次のとおりです:
アルゴリズムの紹介: ここでも「Dahua データ構造」の例を使用します:
ポーカーは、ほとんどの人が持っているものです。ゲームをしました。通常、開始時に 1 人がカードを配り、他の人がカードを引いて並べ替えます。最初に引いたカードが 5 で、2 番目のカードが 3 であれば、当然、3 番目のカードを挿入します。カードが 4 の場合は 3 と 5 の間で見つけ、4 番目のカードは 6 の場合は 5 の後ろに置き、5 番目のカードは 2 の場合は 3 の前に挿入します。最後に、すべてのカードを引き終えたら、手札のカードを小さいものから大きいもの(ポイント)に分類します。このシーケンスを見てみましょう:5 3 3 5 // 要素が 1 つだけある順序付きリストに 3 を挿入します 5
3 5 4 4 // 要素が 2 つある順序付きリストに 4 を挿入します 3 5 3 4 5 // 2 つの要素を持つ順序付きリストに 6 を挿入します 3 4 5
3 4 5 6 2 / / 2 つの要素を持つ順序付きリストに 2 を挿入します 3 4 5 6
2 3 4 5 6
基本的な考え方: 直接挿入ソートの基本的な考え方は、順序なしリストから毎回最初の要素を取り出し、順序付きリストの適切な位置に挿入することで、順序付きリストに順序が残るようにすることです。
最初のパスは最初の 2 つの数値を比較し、サイズに従って 2 番目の数値を順序付きリストに挿入します。2 番目のパスは 3 番目のデータと最初の 2 つの数値を後ろから前にスキャンし、3 番目の数値を順序付きリストに挿入します。サイズに従って順序付きリストに挿入し、順番に処理を進め、(n-1) 回のスキャン後にソート処理全体が完了します。
直接挿入ソートは 2 レベルのネストされたループで構成されます。外側のループは、比較する値を識別して決定します。内側のループは、比較される値の最終位置を決定します。直接挿入ソートでは、比較対象の値とその前の値が比較されるため、外側のループは 2 番目の値から始まります。現在の値が比較対象の値より大きい場合、比較対象の値より小さい値が見つかるまでループ比較が継続され、比較対象の値が次の位置に配置されてサイクルが終了します。
挿入ソートの基本的な方法は次のとおりです。各ステップで、すべてのレコードが挿入されるまで、キーのサイズに従って、ソート対象のレコードが以前にソートされたシーケンス内の適切な位置に挿入されます。
アルゴリズムの実装:
<?php //直接插入排序 function swap(array &$arr,$a,$b){ $temp = $arr[$a]; $arr[$a] = $arr[$b]; $arr[$b] = $temp; } function InsertSort(array &$arr){ $count = count($arr); //数组中第一个元素作为一个已经存在的有序表 for($i = 1;$i < $count;$i ++){ $temp = $arr[$i]; //设置哨兵 for($j = $i - 1;$j >= 0 && $arr[$j] > $temp;$j --){ $arr[$j + 1] = $arr[$j]; //记录后移 } $arr[$j + 1] = $temp; //插入到正确的位置 } } $arr = array(9,1,5,8,3,7,4,6,2); InsertSort($arr); var_dump($arr);
実行結果:
array(9) { [0]=> int(1) [1]=> int(2) [2]=> int(3) [3]=> int(4) [4]=> int(5) [5]=> int(6) [6]=> int(7) [7]=> int(8) [8]=> int(9) }
直接挿入ソートアルゴリズムの時間計算量は
O(n^2)です。 直接挿入ソートは安定したソートです。
この記事は「Dahua データ構造」から参照されています。将来の参考のためにここに記録されているだけです。批判しないでください。
関連する推奨事項:
以上がPHP ソート アルゴリズム ストレート挿入ソートの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。