[演算法(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次
- Best Case:Ο(n)
- 空間複雜度(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; } } } };