引入

• 氣泡排序顧名思義，就是像冒泡一樣，泡泡在水裡慢慢升上來，由小變大。
• 雖然氣泡排序和冒泡並不完全一樣，但卻可以幫助我們理解氣泡排序。

思路

• 一組無序的陣列，要求我們從小到大排列
  1. 我們可以先將最大的元素放在陣列末尾
  2. 再將第二大的數放在陣列的倒數第二個位置
  3. 再將第三大的數放在陣列的倒數第三個位置
  4. 以此類推
• 那麼現在問題的關鍵就是如何將 第 n 大的數 放在 倒數第 n 個位置 ---> 交換

• 下面是氣泡排序的gif動畫，該圖來自於菜鳥教學

實現

提醒

• 現在我們假設無序陣列長度為 n 即下標 [ 0 , n-1 ]
• 當前元素下標為 i ，下一個元素的下標為 j

第一次遍歷 [ 0 , n - 1- 1 ] ---> [ 0 , n -2 ]

• 如果 當前元素 > 後一個元素 ，那麼就交換兩個元素 ， 再進行下次遍歷
• 如果 當前元素 > 後一個元素 , 直接進行下次遍歷
• 直到遍歷完成之後，最大的值就在一次一次的交換中被交換到了陣列末尾
• 思考：為什麼是從 0 開始遍歷 ，n-2 結束 ?
  1. 因為 j 為 i 的下一個元素下標 ，如果為 [ 0，n-1 ]的話 ，那麼當前元素下標就可以為 n - 1，那麼下一個元素的下標就為 n ，顯然陣列下標越界了
  2. 而且正因為是從 [ 0 , n -2] 範圍遍歷 ，剛好可以保證經過這一輪遍歷後 ，最大的數在陣列末尾 ( i = n - 2 【即為倒數第二個數】 ，j = i + 1【末尾數】)

第二次遍歷 [ 0 , n - 1- 2]----> [ 0 , n -3 ]

• 經過第一次遍歷，我們已經將最大的數移動到了陣列末尾，所以，我們不用在去對末尾以確定的數進行比較，我們可以減少次數，來提高效率
• 再次參照第一次遍歷的步驟

......
最後一次遍歷 [ 0 , n - 1 - (n-1) ] ---- > [ 0 , 0 ]

• 最後一次遍歷的情況就是還剩下兩個元素未進行排序的情況 ，即下標 0 和 下標 1 未進行排序
• 只需對這兩個元素進行排序後，就完成了這個陣列的排序

怎麼確定一共需要遍歷幾次及每次遍歷的陣列下標範圍

• 遍歷次數問題
  • 我們先來做一個假設
    • 如果一個陣列只有兩個元素，那麼應該遍歷幾次 ? 1 次
    • 如果一個陣列只有三個元素，那麼應該遍歷幾次 ? 2次
      • 第一次將最大的數放在最末尾 ，第二次將第二大的數放在倒數第二 ， 第三大的元素自然而然就在倒數第三了【即第一個】 ，不用遍歷
    • 如果一個陣列只有四個元素，那麼應該遍歷幾次 ? 3 次
      • 第一次將最大的數放在最末尾 ，第二次將第二大的數放在倒數第二 ， 第三次將第三大的元素放在在倒數第三 ，剩下一個元素，不用排
    • 顯而易見，如果有 n 個 元素 ，那麼就需要遍歷 n - 1 次
• 每次遍歷陣列下標
  • 按照上面的實現部分
    • 第一次遍歷我們需要陣列的下標為 [ 0 , n -2 ]
    • 第二次遍歷我們需要陣列的下標為 [ 0 , n -3 ]
    • 第三次遍歷我們需要陣列的下標為 [ 0 , n -4 ]
  • 那麼就有一個規律了 ，n - 2 ， n - 3 ， n - 4
    • 當我們正在進行第一次遍歷時，用一個變數儲存 m = 1 ， 那麼第一次遍歷下標可以為 [ 0 , n -1 - m ]
    • 當我們正在進行第二次遍歷時，用一個變數儲存 m = 2 ， 那麼第一次遍歷下標可以為 [ 0 , n -1 - m ]
    • 當我們正在進行第三次遍歷時，用一個變數儲存 m = 3 ， 那麼第一次遍歷下標可以為 [ 0 , n -1 - m ]
    • 當我們正在進行最後一次遍歷時，用一個變數儲存 m = n - 1， 那麼第一次遍歷下標可以為 [ 0 , n -1 - m ] ---> [ 0 , n - 1 - (n -1) ]

程式碼實現

// 氣泡排序演演算法
public static int[] bubble(int[] ints){
    // 注意我這裡使用的是 <  ， 而不是我思路中的  <= , 可以自行更改 ，如果沒想明白說明你還沒有理解
    // 用 i 來表示一共需要遍歷多少次
    for (int i = 0; i < ints.length-1; i++) {
        // 真正開始進行遍歷 ，根據 i 的值 不同 ，j 就不同 ，也就是說每次大遍歷中小遍歷的次數不同
        for (int j = 0; j < ints.length-1-i; j++) {
            // 如果前一個元素 >  後一個元素 ，則交換
            if (ints[j] > ints[j+1]){
                int temp = ints[j];
                ints[j] = ints[j+1];
                ints[j+1] = temp;
            }
            // 繼續下次遍歷
        }
    }
    return ints;
}