バブルソート-java実装


バブルソートは一般的なソートアルゴリズムであり,そのコア部分は二重ネストサイクルであるため,バブルソートの時間的複雑さはO(N 2)である.その基本思想は、隣接する2つの要素を比較するたびに、彼らの順序が間違っている場合は交換することです(ここで、順序は私たちが予め設定した大きいものから小さいものまで、または小さいものから大きいものまで).
たとえば、グループの数を大きいものから小さいものまでソートする必要があります.大きいものから小さいものまで並べ替えている以上、小さいものほど後ろに寄っています.隣接する2つの数を比較するたびに、後ろの数が前の数より大きい場合は、この2つの数の位置を交換します.最後の2つの数が比較されるまで比較した後、最小の数は最後の1つで、このように私たちは最小の数の位置を確定して、“1回”が完成したことを説明して、1回ごとに1つの数の位置しか確定できません.プロセス全体が気泡に似ているため、一歩一歩上に「出る」ので、「泡ソート」アルゴリズムと呼ばれます.
まとめて拡張すると,n個の数がソートされている場合,n−1個の数の位置,すなわちn−1回の操作を行うだけである.「1回ごとに」は、1位から隣接する2つの数の比較を行い、小さい数を後ろに置き、比較が終わったら1つ後ろに移動し、次の2つの隣接数の大きさを比較し続け、最後の未確定位置の数まで繰り返す必要があります.バブルソートの利点は、ソートを行うたびに比較が少なくなることが明らかである.ソートを行うたびに小さな値が見つかり、次のソートでもその数と比較する必要がないからである.
次にjavaコードでバブルソートを実現します.
package test;

public class test5 {
	public static void main(String[] args) {
		int a[] = {12,23,24,11,66,43,98,70,1,2};
		System.out.println("sort before:");
		printArray(a);
		System.out.println("after bubbleSort:");
		bubbleSort(a);
		printArray(a);
	}
	
	public static void bubbleSort(int[] a) {
		int temp = 0;
		int n = a.length;
		//          ,n    ,    n-1 
		for(int i = 0; i < n-1; i++) {
			//              ,  1                 
			for(int j = 0; j < n-i-1; j++) {
				//       
				if (a[j] < a[j+1]) {
					temp = a[j];
					a[j] = a[j+1];
					a[j+1] = temp;
				}
			}
		}
	}
	
	public static void printArray(int[] numbers) {
        for (int i = 0 ; i < numbers.length ; i ++ ) {
        	System.out.print(numbers[i] + ",");
        }
        System.out.println("");
    }
}
    :
sort before:
12,23,24,11,66,43,98,70,1,2,
after bubbleSort:
98,70,66,43,24,23,12,11,2,1,