PHP の 8 つの主要なソート アルゴリズム - 挿入ソート (-) 直接挿入ソート

PHP の 8 つの主要なソート アルゴリズム - 挿入ソート (-) 直接挿入ソート

直接挿入ソート:

挿入ソートは最も単純なソートの 1 つです。このアルゴリズムでは、N 要素を持つシーケンスの場合、挿入ソートは N-1 ソートで構成されます。その動作原理は、並べ替えられていないデータの場合、並べ替えられたシーケンスの後ろから前に向かってスキャンして、対応する位置を見つけて挿入することです。

挿入ソートアルゴリズムのステップ:

1. 最初のものを次のように変更します。 sorted シーケンスの最初の要素は順序付けられたシーケンスとみなされ、2 番目の要素から最後の要素まではソートされていないシーケンスとみなされます。

2. ソートされていないシーケンスを最初から最後までスキャンし、スキャンされた各要素を順序付けされたシーケンスの適切な位置に挿入します (ここで注意すべき問題があります。順序付けされたシーケンス内に挿入される要素と等しい要素が存在する場合、挿入される要素はその要素の後に見つかります。この方法で挿入ソートが要素の前に挿入される場合、その要素は安定します。この方法の挿入ソートは安定しています。 挿入ソートは不安定です

   上記の手順の挿入ソート アルゴリズムは次のように要約できます:

   並べ替えの L 回目のパスで、位置 L の要素を左に移動し、要素が前に来るまで移動します。 L+1 要素の正しい位置では、最初の L 要素は の順序になっています。

挿入ソートアルゴリズム分析:

ネストされたループのそれぞれは N 回の反復を必要とするため、挿入ソートの時間計算量は O(N^2);

上記で説明した挿入ソートは、挿入ソートのアルゴリズムにおける直接挿入ソートであり、順序付けされたシーケンス内の挿入位置を検索する際に、1つずつ検索するため、直接挿入ソートと呼ばれます。

引き続きフォローアップの並べ替えアルゴリズムにご注目ください。個人プロジェクトには以下が含まれます。 (www.ya-jing.cn)