[演算法] 氣泡排序法(Bubble Sort)
YehYeh\'s Notepad yehyeh@gmail.com 

[演算法(Algorithm)] 氣泡排序法(Bubble Sort)

  • 將資料分成
    • 已排序:位置 < data.length - i - 1
    • 未排序:位置 ≥ data.length - i - 1
  • 氣泡排序作法:
    • 未排序中的第一筆開始,與第二筆資料比對
      • 第一筆 > 第二筆 交換位置(Swap)
      • 若還有未排序的資料,則用第二筆第三筆資料比對
      • 依此類推
    • 未排序的資料中,比對時都沒有進行交換位置 flag = false
      • 代表資料已排序好 提早結束排序
    • 執行時,未排序資料中的最大值會如同氣泡般往右跑
  • 時間複雜度(Time Complexity)
    • Best Case:Ο(n)
      • 當資料的順序恰好為由小到大時
      • 第一次執行後,未進行任何swap 提前結束
    • Worst Case:Ο(n2)
      • 當資料的順序恰好為由大到小時
      • 每回合分別執行:n-1、n-2、...、1次
      • (n-1) + (n-2) + ... + 1 = n(n-1)/2 Ο(n2)
    • Average Case:Ο(n2)
      • 第n筆資料,平均比較(n-1)/2次
  • 空間複雜度(Space Complexity):θ(1)
  • 穩定性(Stable/Unstable):穩定(Stable)
  • Demo:
  • 演算法
    var swap = function(data, i, j){ 
        var tmp = data[i];
        data[i] = data[j];
        data[j] = tmp;
    };
        
    var bubbleSort = function(data){
        var flag = true;
        for(var i = 0; i < data.length - 1 && flag; i++){
            flag = false;
            for(var j = 0; j < data.length - i - 1; j++){
                if(data[j+1] < data[j]){
                    swap(data, j+1, j);
                    flag = true;
                }
            }
        }
    };