直接挿入ソート
ソートを直接挿入するというアイデアは理解しやすいです、それは次のようになります：
1.ソートされたアレイを分類するアレイを分割します：ソートされていないものと未解決のもの。最初は、最初の要素はソートされていると見なされます。
2。2番目の要素から始めて、ソートされたサブアレイの要素の適切な位置を見つけて挿入します。
3.最後の要素が順序付けられたサブアレイに挿入されるまで、上記のプロセスを繰り返します。
4.並べ替えが完了しました。
例：
アイデアはシンプルですが、コードはバブルソートほど簡単に記述するのは簡単ではありません。まず第一に、正しい位置を決定する方法は？左よりも大きい、または右以下？いいえ、多くの境界条件を考慮する必要があり、判断が多すぎます。第二に、要素を配列に挿入するには、必然的に多数の要素を移動する必要があります。彼らの動きを制御する方法は？
実際、これはアルゴリズム自体の問題ではなく、プログラミング言語と関係があります。アルゴリズム自体がすでに非常に成熟している場合があり、特定のプログラミング言語に関しては、わずかに変更する必要があります。ここで話しているのはJavaアルゴリズムですので、Javaについて話しましょう。
上記の問題を解決するために、2番目のステップを少し改良しました。サブアレイの開始位置からの比較を開始するのではなく、サブアレイの尾から逆比較を開始します。挿入する必要がある数よりも大きい限り、後方に移動します。数値が数値より大きくなるまで、挿入する数はこの空の位置に配置されます。したがって、次のコードを書くことができます。
IntersArray.java
public class insertArray {//配列private long [] arr; //配列のプライベートインテルの有効なデータのサイズ。 //デフォルトのコンストラクターpublic InsertArray（）{arr = new long [50]; } public InsertArray（int max）{arr = new long [max]; } // insert data public void insert（long value）{arr [elems] = value; Elems ++; } //データpublic void display（）{for（int i = 0; i <elems; i ++）{system.out.print（arr [i]+""）; } system.out.println（）; } // [sort public void insertsort（）{long select = 0l; for（int i = 1; i <elems; i ++）{select = arr [i]; int j = 0; for（j = i; j> 0 && arr [j -1]> = select; j-）{arr [j] = arr [j -1]; } arr [j] = select; }}}テストクラス：
testinsertarray.java
public class testinsertarray {public static void main（string [] args）{insertArray iarr = new InsertArray（）; iarr.insert（85）; iarr.insert（7856）; iarr.insert（12）; iarr.insert（8）; iarr.insert（5）; iarr.insert（56）; iarr.display（）; iarr.insertsort（）; iarr.display（）; }}印刷結果：
アルゴリズムのパフォーマンス/複雑さ
次に、直接挿入アルゴリズムの時間の複雑さについて説明しましょう。入力に関係なく、アルゴリズムは常にn-1ラウンドのソートを実行します。ただし、各要素の挿入点は不確実であり、入力データの影響を大きく受けているため、その複雑さは確信がありません。最高、最悪の状況、平均的な状況について説明できます。
1.最良のケース：アルゴリズムの特性から、配列自体が正の順序である場合がわかります（配列が順序付けられ、注文は必要な順序と同じであり、議論の前提に基づいて昇順です）。その理由は、この場合、各要素を1回だけ比較する必要があり、移動する必要がないためです。アルゴリズムの時間の複雑さはo（n）です。
2。最悪の場合：明らかに、配置される配列が逆の順序である場合、それは最悪の場合です。この場合、ラウンドあたりの比較数はI-1であり、割り当ての数はiです。合計回数は、シリーズ2N-1の最初のn項、つまりn^2の合計です。アルゴリズムの時間の複雑さはo（n^2）です。
3.平均状況：上記の分析から、平均状況下でのアルゴリズムの操作の数は約（n^2）/2であることを取得できます（注：ここでの計算は割り当てと比較に基づいています。移動と比較に基づいている場合、それは約n^2/4です）。明らかに、時間の複雑さはまだo（n^2）です。
アルゴリズムの空間的複雑さに関しては、すべての動きがデータ内で実行されます。唯一のオーバーヘッドは、一時的な変数を導入したことです（一部のデータ構造は本に「センチネル」と呼ばれます）ので、その空間的な複雑さ（余分なスペース）はO（1）です。
アルゴリズムの安定性
現在の数値よりも大きくなく、交換する必要がない位置を見つける必要があるため、ソートを直接挿入することは安定したソート方法です。
アルゴリズムバリアント
手配すべきデータがたくさんある場合、後ろから正面へ見るたびに多くのオーバーヘッドを引き起こします。検索速度を改善するために、バイナリ検索を使用してパフォーマンスの最適化を行うことができます。バイナリ検索の効率は非常に高いため、O（n）の複雑さが確保され、データが増えたり、入力データが最悪の状態になると検索効率が大幅に向上します。いくつかの本では、この方法は折りたたみと呼ばれ、ハーフインサートソートと呼ばれます。そのコードの実装は非常に複雑であり、将来の時間がある場合は投稿できます。
さらに、2方向の挿入ソートがあり、テーブルインサートソートがあります。 2方向の挿入ソートは、折りたたみ式と半分の挿入ソートに基づいてさらに改善され、その動きの数は約N^2/8です。ただし、動きの数を回避せず、複雑さレベルを下げることもありません。テーブル挿入のソートは、ストレージ構造を完全に変更し、レコードを移動しませんが、リンクされたリストを維持する必要があり、リンクリストのポインターはレコードを移動する代わりに変更されます。したがって、その複雑さはまだo（n^2）です。
2ウェイの挿入ソートとテーブル挿入ソートについては、Yan WeiminとWu Weiminが編集した本「データ構造」を参照できます。
アルゴリズム適用シナリオ
O（n^2）の複雑さのために配列が大きい場合、挿入並べ替えは適用できません。ただし、データが比較的少ない場合、それは良い選択であり、一般的に迅速な並べ替えのための拡張として使用されます。たとえば、STLのソートアルゴリズムとSTDLIBのQSORTアルゴリズムでは、挿入並べ替えがクイックソートのサプリメントとして使用され、少数の要素を並べ替えるために使用されます。たとえば、JDK 7 java.util.arraysで使用されるソートメソッドの実装では、ソートする配列の長さが47未満の場合、挿入並べ替えが使用されます。