Bubble Sort 泡泡排序法－Cedric's 學習備忘錄

泡泡排序法的原理是將一組數字中的第一位與後一位相比較，若後一位數字較大，則位置對調，再將第二位數與第三位數做比較，若後一數字較大，再對調位置

比如說：

4 3 2 5 1，五個數字比較的話，第一位與第二位比較，也就是4與3做比較，比較結果成為

3 4 2 5 1，再比較第二位跟第三位數，也就是4與2比較，比較結果為

3 2 4 5 1，再比較第三跟第四位數，也就是4與5比較，但是由於4比5小，所以比較結果不變

3 2 4 1 5，再比較第四跟第五位數，也就是5與1比較，比較結果為

以上為第一輪比較結果，由於並沒有完成排列順序，故接著第二輪的比較

3 2 4 1 5，重新比較第一與第二位數，3與2比較，比較結果為

2 3 4 1 5，再來第二位與第三位比較，3與4比較，3比4小，比較結果不變

2 3 4 1 5，再來第三位與第四位比較，4與1比較，比較結果為

2 3 1 4 5，再來4與5的比較結果也不變

以上為第二輪比較結果，一樣沒有完成比較順序，再比較第三輪

2 3 1 4 5，重新比較第一與第二位數，2與3比較，比較不變

2 3 1 4 5，再來第二位與第三位比較，3與1比較，比較結果為

2 1 3 4 5，由於第三位開始順序已排完成，所以比較結果皆不變

接下來繼續比較第四輪

2 1 3 4 5，重新比較第一與第二位數，2與1比較，比較結果為

1 2 3 4 5，雖然已經排序完成，但迴圈還是會繼續比較，但比較結果皆不變

1原本排列的位置是在最後一位，最後跑到第一位，就像泡泡從水底往上浮起，故稱之為泡泡排序 (什麼爛名字)

程式需要由兩個迴圈來控制，第一個迴圈控制要比較幾輪，第二個迴圈就控制要比較第幾位數

由小排列至大的語法大致如下：

public class TestBubbleSort {

    public static void main(String[] args) {
       int[] arr = {1, 3, 5, 7, 9, 2, 4, 6, 8};
       print(arr);
       bubbleSort(arr);
       print(arr);
    }


    public static void bubbleSort(int[] a) {
       int temp;
       for(int i=a.length-1; i>=1; i--){
           for(int j=0; j<=i-1; j++){
               if(a[j] > a[j+1]){
                   temp = a[j];
                   a[j] = a[j+1];
                   a[j+1] = temp;
               }
           }
       }
    }

    public static void print(int[] a) {
       for(int i=0; i<a.length; i++){
           System.out.print(a[i] + " ");
       }
       System.out.println();
    }
}