ソートの挿入

ソートされた配列内のすべての要素の位置を検索して挿入し、ソートするアルゴリズムです.

ソート・プロシージャ

でソートされる資料は、2つの部分集合SおよびUと仮定される.

サブセットS:配列されたフロントエンド要素

サブセットU:残りのソートされていない要素

の並べ替えられていないサブセットUの要素を1つずつ取り出し、並べ替えられたサブセットSの最後の要素から比較し、位置を探して挿入する.

の挿入順序を繰り返すと、サブセットSの要素は1つずつ増加し、サブセットUの要素は1つずつ減少する.

部分集合Uが空の集合である場合、挿入ソートが完了する.

ソースコード

void InsertionSort() {	
	int[] nums = {1000, 400, 12, -59, 328, 121, -3};
		
        // loop 1
	for(int i = 1; i < nums.length; i++) {
    
    		//loop 2
		for(int j = i-1; j >= 0; j--) {
        
        		// conditional 1
			if(nums[j] > nums[j+1]) {
				int temp = nums[j+1];
				nums[j+1] = nums[j];
				nums[j] = temp;
			} 
		}
	}
	
	System.out.println(Arrays.toString(nums));
}

loop 1:2番目の要素から最後の要素までを表します.
loop 2:現在の要素の前の要素を表します.
conditional 1:2つの要素を比較し、大きな要素を後ろに押して位置を探します.

時間の複雑さ

最悪の場合、挿入ソートと同様にO(N^2)です.
すべての配列の最適な場合,一次元素のみを比較し,従ってO(N)である.また、要素を1つずつ挿入/削除すると、オーバーヘッドが非常に小さくなります.
配列サイズが小さいときはかなり効率的で、配列サイズが大きいときはO(nlogn)アルゴリズムを使って、挿入ソートを切り替えることもできます.

くうかんふくざつさ

1つのアレイでしか行われないのでO(n)である.

長所

は簡単です.

のほとんどの要素がソートされている場合に有効です.

は、他のメモリ領域を必要とせずにその場でソートされます.

安定ソート(安定ソート).

泡のソートは、選択したソートよりも比較的速い.

短所

平均

と最悪の時間複雑度はO(n^2)であるため効率は低下する.

泡配列、選択配列と同様に、配列の大きさが大きいほど効率が低下する.

の資料構造によれば、要素を押し出すのに長い時間がかかる.

[注意]

挿入