---
tags: DSA in JavaScript
---
# Ch.11-2 Bubble Sort
Bubble sort 翻譯為氣泡排序法，在排序演算法系列中，氣泡排序法的演算過程算是最容易理解的一種。

function bubbleSort (arr) {
    // 1. i 代表排序的範圍，因此會從最後一個元素開始縮減
    for (let i = arr.length - 1; n >= 0; n--) {
    // EX: 進一步優化：設置一個旗標，代表這個陣列沒有被改動過
        let noSwap = true
    // 2. 由 j 這個迴圈開始排序
        for (let j = 0; j < i; j++) {
        // 3.如果 arr[j] 比下一個元素還要大，它就會與下一個元素互換位置
        // EX: 互換位置後，因為陣列被改動了，所以更改旗標的狀態
            if (arr[j] > arr[j + 1]) {
                const temp = arr[j + 1]
                arr[j + 1] = arr[j]
                arr[j] = temp
                noSwap = false
            }
        }
    // EX: 如果 j 迴圈結束後沒有被更動的話，直接結束 i 迴圈
        if (noSwap) break
    }
    return arr
}

氣泡排序法基本上就是倆倆互換位置的過程，雖然容易理解，但是因為使用了兩個迴圈，因此時間複雜度為 O(n^2^)，只要陣列大小達到一定規模，就會大幅增加演算時間。