バブルソート

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

隣接する2つの要素を比較、交換、ソートするアルゴリズム

ソート・プロシージャ

  • 最初の要素と2番目の要素、2番目と3番目の要素、...(最後-1)条件に従って位置を交換する最初の要素と最後の要素を比較します.
  • のソートを1回行うと、最大の要素が最後の位置に移動します.2回転後、2番目の大きな要素は(最後の-1)位置に移動します.つまり、回転するたびに要素がソートから除外されます.

    • ソースコード

    void BubbleSort() {
	int[] nums = {1000, 400, 12, -59, 328, 121, -3};
	
        // loop 1
	for(int i = 0; i < nums.length; i++) {
    
    		// loop2
		for(int j = 0; j < nums.length-(i+1); j++) {
			if(nums[j] > nums[j+1]) {
				int temp = nums[j];
				nums[j] = nums[j+1];
				nums[j+1] = temp;
			}
		}
	}
		
	System.out.println(Arrays.toString(nums));
}
    loop 1:ソートから除外する要素の数を示します.
    loop 2:jの2番目の要素をj+1の要素と比較した後、シフトします.iの値を増やすたびに、巡回する要素の数が1つ減少します.

    時間の複雑さ



    回転毎の比較回数を合わせると上記のように、全ての場合O(N^2)となります.

    くうかんふくざつさ


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

    長所

  • の実装は非常に簡単で、コードは直感的です.
  • は、他のメモリ領域を必要とせずにその場でソートされます.
  • 安定ソート(安定ソート).

    • 短所

  • 時間複雑度は全ての場合O(N^2)であるため非常に非効率である.
  • 要素は、ビット探索中によく交換演算を発生する.
    • [注意]
  • バブルソート
    • リングのパーセントロード
    Programmers多段歯ブラシ販売