PHPソートアルゴリズムシリーズの挿入ソートを詳しく解説-PHPチュートリアル-php.cn

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

jacklove

リリース： 2023-04-02 10:14:02

オリジナル

1522 人が閲覧しました

この記事は、主に 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 サイトをサポートしてくれることを願っています。