PHP実装挿入ソート

ガイド人
ソートのアルゴリズムについては,これで一段落する.バブルソート、クイックソート、選択ソート、本編の挿入ソートの4つのアルゴリズムは比較的簡単で、理解しやすい.もっと複雑なアルゴリズムは、人の子弟を誤らないように、恥をかかないようにします.
ソートの挿入
挿入ソート(英語:Insertion Sort)は、単純で直感的なソートアルゴリズムです.秩序化されたシーケンスを構築し、並べ替えられていないデータに対して、並べ替えられたシーケンスを後方から前方にスキャンし、対応する位置を見つけて挿入することが原理です.挿入ソートは実装上、通常はin-placeソート(すなわち、O(1)の余分な空間のソートにのみ使用される)を採用するため、後から前へスキャンする過程で、ソートされた要素を徐々に後ろにシフトし、最新の要素に挿入空間を提供する必要がある.
一般に,挿入ソートはin−placeを用いて配列上で実現される.具体的なアルゴリズムは以下の通りである.

は第1の要素から始まり、この要素は

に並べ替えられたと考えられる.

は次の要素を取り出し、並べ替えられた要素のシーケンスにおいて

を後方から前方に走査する.

新しい要素より大きい場合は、次の位置

に移動します.

は、順序付けされた要素が新しい要素より小さいまたは等しい位置

が見つかるまで、ステップ3を繰り返す.

この位置に新しい要素を挿入した後の

.

手順2~5

を繰り返す.
ウィキペディアからの紹介です.ポイントは手順2~5です.
動図デモ
≪インスタンス｜Instance｜emdw≫

= 0; $k--) {
            //     ，       ，          
            //    $temp > $arr[$k]
            if ($temp < $arr[$k]) {
                $arr[$k + 1] = $arr[$k];
                $arr[$k] = $temp;
            }
        }
    }
    return $arr;
}

print_r(insertSort($arr));
// Array ( [0] => 2 [1] => 3 [2] => 8 [3] => 16 [4] => 21 [5] => 23 [6] => 24 [7] => 32 [8] => 33 )

参考資料:挿入ソート、PHPソートアルゴリズムシリーズ:挿入ソート.