挿入ソート Insertion Sort【可視化GIFでソートアルゴリズムを解説 その３】

3、挿入ソート（Insertion Sort）

挿入ソートとは、シンプルで直感的なソートアルゴリズムです。 順序付けられたシーケンスを作成することで機能します。ソートされていないデータの場合は、ソートされたシーケンスで後ろから前にスキャンし、対応する位置を見つけて挿入します。 挿入ソートは通常、インプレースソート（つまり、O（1）の余分なスペースのみを使用するソート）によって実装されます。したがって、後方から前方にスキャンするプロセスでは、ソートされた要素を段階的に後方に繰り返しシフトする必要があります。ステップ。、最新の要素の挿入スペースを提供します。

3.1 アルゴリズムの説明

一般的に、挿入ソートはインプレースを使用して配列に実装されます。 具体的なアルゴリズムは次のとおりです。

• 最初の要素から始めて、要素はソートされたと見なすことができます。
• 次の要素を取り出し、並べ替えられた要素のシーケンスで後ろから前にスキャンします。
• 要素（ソート済み）が新しい要素よりも大きい場合は、要素を次の位置に移動します。
• 並べ替えられた要素が新しい要素以下になる位置が見つかるまで、手順3を繰り返します。
• 新しい要素をこの位置に挿入した後。
• 手順2〜5を繰り返します。

3.2 可視化デモ

3.2 実装

    /**
     * Insertion Sort
     * @param array
     * @return
     */
    public static int[] insertionSort(int[] array) {
        if (array.length == 0)
            return array;
        int current;
        for (int i = 0; i < array.length - 1; i++) {
            current = array[i + 1];
            int preIndex = i;
            while (preIndex >= 0 && current < array[preIndex]) {
                array[preIndex + 1] = array[preIndex];
                preIndex--;
            }
            array[preIndex + 1] = current;
        }
        return array;
    }

3.4 性能評価

挿入ソートは通常、インプレースソート（つまり、O（1）の余分なスペースのみを使用するソート）によって実装されます。したがって、後方から前方にスキャンするプロセスでは、ソートされた要素を段階的に後方に繰り返しシフトする必要があります。ステップ。、最新の要素の挿入スペースを提供します。

• 最良時間計算量 ：T(n) = O(n)
• 最悪時間計算量 ：T(n) = O(n2)
• 平均時間計算量 ：T(n) = O(n2)

---