PHP ソート アルゴリズム シリーズ挿入ソート例の共有
- 小云云オリジナル
- 2018-01-08 10:14:311540ブラウズ
この記事では、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 中国語 Web サイトの他の関連記事を参照してください。