PHP ソート: PHP 挿入ソートのアルゴリズムのアイデアとアルゴリズムの実装

この記事の内容は、PHP ソートに関するものです。PHP 挿入ソートのアルゴリズムのアイデアとアルゴリズムの実装です。一定の参考価値があります。必要な友人は参考にしてください。お役に立てれば幸いです。

アルゴリズムの紹介:

ここでも「Dahua データ構造」の例を使用します:

ポーカーは、ほとんどすべての人がプレイしたことがあるゲームです。通常、開始時に 1 人がカードを配り、他の人がカードを引いて並べ替えます。最初に引いたカードが 5 で、2 番目のカードが 3 であれば、当然 3 を挿入します。カードは 4、3 と 5 の間で見つけます。4 番目のカードは 6、5 の後ろに置きます。5 番目のカードは 2、3 の前に置きます。最後に、すべてのカードを引き終わったら、手札のカードを小さいものから大きいもの（ポイント）に分類します。

#このシーケンスを見てみましょう：

# 5から5 5項、
3 4 5 6 // 2つの要素3 4 5、##の順序に6を挿入します# 3 4 5 6 2 // Insert 2 2 つの要素を入力します 3 4 5 5 6
2 の順序付きリストに 3 4 5 6

直接挿入ソートの基本的な考え方は次のとおりです。順序なしリストの最初の要素を毎回取り出して、順序付きリストの適切な位置に挿入するため、順序付きリストは順序付けされたままになります。

最初のパスでは最初の 2 つの数値を比較し、サイズに応じて 2 番目の数値を順序付きリストに挿入します。2 番目のパスでは 3 番目のデータと最初の 2 つの数値を後ろから前にスキャンし、3 番目の数値をスキャンします。サイズに応じて順序付きリストに挿入され、これが順番に継続され、ソート プロセス全体が (n-1) 回のスキャン後に完了します。

直接挿入ソートは、2 つのレベルのネストされたループで構成されます。外側のループは、比較する値を識別して決定します。内側のループは、比較される値の最終位置を決定します。直接挿入ソートでは、比較対象の値とその前の値が比較されるため、外側のループは 2 番目の値から始まります。現在の値が比較対象の値より大きい場合、比較対象の値より小さい値が見つかるまでループ比較が継続され、比較対象の値が次の位置に配置されてサイクルが終了します。

挿入ソートの基本的な方法は次のとおりです。各ステップで、すべてのレコードが挿入されるまで、キーのサイズに従って、ソート対象のレコードが以前にソートされたシーケンス内の適切な位置に挿入されます。

挿入ソート アルゴリズムの実装:

// 直接插入排序
function swap(&$arr,$a,$b)
{
$temp    = $arr[$a];
$arr[$a] = $arr[$b];
$arr[$b] = $temp;
}
function insertSort(&$arr)
{
$count = count($arr);
for ($i=1; $i = 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)
}

##関連する推奨事項:

php 配列のソート方法の共有 (バブル ソート、選択ソート)

## PHP の実装ヒープ ソート、PHP ヒープ ソート_PHP チュートリアル

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