整列挿入

5009 ワード
アルゴリズム#アルゴリズム# テキストリンク

整列挿入


挿入ソートは、2番目のインデックスから始まり、インデックスの前のすべての数に比べて、インデックスの数より大きい場合は、前に挿入してソートする方法です.

まず、キー値は配列インデックス1から始まる.i以前の要素を比較する必要があります.インデックスが0の場合、比較可能な要素はありません.keyは8で、8より大きい値を右側に押します.8未満の要素が見つかった場合は、その要素の後ろに8を挿入する必要がありますが、その要素は存在しません.そのため、一番前に挿入します.

8を一番前に挿入した後、iを1つ増やして比較を続けます.keyは1になります.1より小さい要素はないので、一番前にあります.


その後iは1つ増加し,キーは3である.次の図は、3未満の要素に遭遇した場合に挿入する手順を示しています.



これでiが1つ増え、最後の要素2がキーになります.2未満の要素は1なので、1の後に2を挿入します.次の図は、このプロセスを示しています.




今ではすべての比較と交換が終わりました.昇順ソートが表示されます.

時間の複雑さ


繰り返し文→O(N 2)O(N^2)O(N 2)

インプリメンテーション

class Solution {
    public int[] insertionSort(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            for (int j = i; j > 0; j--) {
                if (nums[j] < nums[j-1]) {
                    int tmp = nums[j-1];
                    nums[j-1] = nums[j];
                    nums[j] = tmp;
                // 이미 if문 수들 앞은 정렬이 되어 있다    
                } else {
                    break;
                }
            }
        }
        return nums;
    }
}
[TIL] Spring Core 1.1-1.2
✔アルゴリズム/プログラマー/ハッシュレベル2/電話番号リスト(Python使用)