PHP ソート アルゴリズム ストレート挿入ソート

この記事では、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 ソート アルゴリズム ストレート挿入ソートの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。