PHPソートアルゴリズムシリーズの挿入ソートを詳しく解説

この記事は、主に PHP ソート アルゴリズム シリーズの挿入ソートに関する情報を詳しく皆さんに紹介します。一定の参考価値があります。興味のある方は、

insert sort を参照してください。

既に順序付けされたデータ列があります。この既に配置されたデータ列に数値を挿入する必要がありますが、挿入後もデータ列が順序付けされている必要があります。この場合、数値は必須です。新しいソート方式 - 挿入ソート方式 挿入ソートの基本動作は、すでにソート済みの順序付きデータにデータを挿入し、その数値に 1 を加えた新しい順序付きデータを取得することです。データ。データの並べ替えの時間計算量は O(n^2) です。安定した選別方法です。挿入アルゴリズムは、ソートされる配列を 2 つの部分に分割します。最初の部分には、最後の要素を除く配列のすべての要素が含まれます (配列に挿入位置を追加するためのスペースが 1 つ増えます)。2 番目の部分には、この要素のみが含まれます。 1 つの要素 (つまり、挿入される要素)。最初の部分がソートされた後、この最後の要素がソートされた最初の部分に挿入されます。

原則

直接挿入ソート (挿入ソート) の基本的な考え方は次のとおりです: ソート対象のレコードが、次に従って以前にソートされたレコードに挿入されるたびにキー サイズ すべてのレコードが挿入されるまで、順序付けされたサブシーケンス内の適切な位置。
配列が a[0...n-1] であるとします。

1. 最初、a[0] は順序付き領域を形成し、順序なし領域は a[1..n-1] です。 i=1 とする
2. a[i] を現在の順序領域 a[0...i-1] にマージして、a[0...i] の順序区間を形成します。
3.i を実行し、i==n-1 になるまで 2 番目のステップを繰り返します。並べ替えが完了しました。

PHP コードの実装

function insertSort($arr){
  //获取需要排序的长度
  $length=count($arr);
  //假定第一个为有序的，所以从$i开始比较
  for ($i=1; $i <$length ; $i++) {
    //存放待比较的值
    $tmp=$arr[$i];
    for($j=$i-1;$j>=0;$j--){
      //若插入值比较小，则将后面的元素后移一位，并将值插入
      if($tmp<$arr[$j]){
        $arr[$j+1]=$arr[$j];
        $arr[$j]=$tmp;
      }else{
        break;
      }
    }
  }
  return $arr;
}

アルゴリズムの時間計算量の計算

最良の場合 (要素は順序付けされています) : その場合、n-1 回ループするだけで済み、時間計算量は O(n) です。
最悪の場合 (要素の順序が逆): ループ調整の数: [ n * (n-1 ) ] / 2、時間計算量は O (n ^ 2)
平均時間計算量は次のとおりです: O (n ^ 2)

上記がこの記事の全内容です。皆さんの学習に役立ちます。 ヘルプ、そして皆さんが php 中国語 Web サイトをサポートしてくれることを願っています。

興味があるかもしれない記事:

PHP のバケット ソート アルゴリズムの説明

Laravel Service Provider で遅延読み込みを開発および設定するときに発生する問題の詳細な説明

PHP はソート ヒープ ソート アルゴリズムを実装します

以上がPHPソートアルゴリズムシリーズの挿入ソートを詳しく解説の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。