PHP ソート アルゴリズム シリーズ挿入ソート例の共有

この記事では、PHP ソート アルゴリズム シリーズの関連情報を主に詳しく紹介します。興味のある方は参考にしていただければ幸いです。

挿入ソート

既に整列したデータ列があり、この既に整列したデータ列に数値を挿入する必要がありますが、この際、挿入後もデータ列が整列している必要があります。数値を使用する 新しいソート方法 - 挿入ソート方法 挿入ソートの基本的な操作は、ソート済みの順序付きデータにデータを挿入し、数値に 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 実装バケットソートアルゴリズムの例共有

PHP ソートアルゴリズムヒープソート詳細説明

PHP 単純な選択ソートアルゴリズム学習共有

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