05.md

Bubble Sort

Definition

比較比鄰的兩個數，如果順序不對則交換元素

Performance

• Worst Case: O(n^2)
• Best Case: O(n)
• Average Case: O(n^2)

Code:

function bubbleSort(arr) {
  for (let i = 0; i <= arr.length - 2; i++) { // 最後一個不用排序，必為最大
    let swapping = false;
    for (let j = arr.length - 1; j >= i + 1; j--) {
      if (arr[j] < arr[j - 1]) {
        let temp = arr[j];
        arr[j] = arr[j - 1];
        arr[j - 1] = temp;
        swapping = true;
      }
    }
    if (!swapping) { // 優化，如果沒有任何元素在交換就暫停
      break;
    }
  }
  return arr;
}