ソートの挿入

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

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

ソート・プロシージャ

  • でソートされる資料は、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)であるため効率は低下する.
  • 泡配列、選択配列と同様に、配列の大きさが大きいほど効率が低下する.
  • の資料構造によれば、要素を押し出すのに長い時間がかかる.
    • [注意]
  • 挿入
    • Schemaでの要素の非空チェック
    Frescoソース分析(二)Fresco.initializeDrawee()分析続き