bubble sort的概念就是像泡泡一樣 ，越大的數字會漸漸的往右邊浮

比較相鄰的元素 ，兩兩比大小， 如果前面的數字大於後面的數字就交換順序，一路把最大值往後塞。

1. 跑完第1回合，該陣列的最後一個數字就會是最大的
2. 跑完第2回合，該陣列的倒數第2個數字就會是第2大的
3. 規律為執行完第n回合，第n大的數字就會出現在倒數第n個位置

函式內部實作為:

假設現在有一個陣列[29, 10, 14, 37, 14]要用氣泡排序法來排序的話

1. 29與10相比29較大，所以29與10交換，此時arr = [10, 29, 14, 37, 14]
   

2. 29與14相比29較大，所以29與14交換， 此時arr = [10, 14, 29, 37, 14]
   

3. 29與37相比29較小，所以29不跟37交換， 此時arr = [10, 14, 29, 37, 14]
   

4. 37與14相比37較大，所以37與14交換， 此時arr = [10, 14, 29,14, 37]
   

此時第一回合結束，可以發現最大的數字已經移動到最後面，依序執行n-1回合之後，就可以將全部的數字由小排到大了。

為甚麼是n-1回合?
假如今天有個陣列長度為5，當index1 ~ index4都是排序好的，那麼index0自然也會是最小的，就不需要再跑一次回合，所以只要跑 (n-1)，5–1=4回合即可。

連續的步驟會如下圖所示

圖檔來源:https://visualgo.net/zh/

用js實作氣泡排序法

const bubble = (arr) => {
    for (let i = 0; i < arr.length - 1; i++) {
        for (let j = 0; j < arr.length - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
            }
        }
    }
    return arr;
};
bubble([29, 10, 14, 37, 14])

第一個迴圈的長度為arr.length-1，因為經過一輪的排列，直到最後一回合，剩下的那個值必定為最小值，就不需要比較，可以扣掉一次，那第二個迴圈的長度為甚麼是arr.length-i-1 ?因為經過i回合後，倒數第i個數字都是經過排序的，那麼在跑迴圈的時候就可以排除掉，不需要檢查了。

時間複雜度

• 在最差的情況下，時間複雜度是O(n²)
• 在最佳的情況下，時間複雜度是O(n)
• 在平均情況下，時間複雜度為 O(n²)