前言

今天要進入的是初等排序的最後一部分 - 氣泡排序法，一樣，我們先從觀念開始講起，講解完觀念再帶到演算法，談完演算法之後我們才會來談時間排序以及是否為 Stable

觀念

氣泡排序法可以分為兩種版本，從左邊往右實施、由右邊往左實施，我們先令 Array index 由 1 開始
在本章節，會選擇採用由左至右實施，我們先來進入氣泡排序法的最基本觀念

1. 判斷左值有沒有大於右值，有則交換，沒有則不換
2. 做 n-1 次，完全沒有 swap 發生即結束，每一回合便能把最大值放大最右邊
3. 由於每一回合都已經先將最大值放到右邊了，因此我們可以不要管 index n-i 之後的數 (即為藍色點)
   

演算法

BubbleSort(a[]){
    int n = a.length;
    for(int i=1;i<n-1;i++){ 
        boolean flag = false;      // 預設是沒有交換
        for(int j=1;j<n-i;j++){
            if(a[j]>a[j+1]){       // 若前面大於後面
                swap(a[j],a[j+1]); // 交換
                flag = true;       // 代表有交換過
            }
        }
        if(flag==false) break; //若沒有交換代表已排序好
    }
}

時間複雜度

Best Case : O(n)，假設全部都不用做SWAP
Worse Case : O(n^2)
Avg Case : O(n^2)

Stable or Unstable ?

讓我們看到 if(a[j]>a[j+1]) 這行，必須要真的大於，才會進行交換
當出現 2,2' 兩者值相同時，是不會進行交換的，因此為 Stable