Bubble Sort

給一個裡面都是整數的陣列，請由小到大排列，回傳新的陣列。

Bubble Sort 又稱氣泡排序法，最簡單的排序法，但並不是最有效率的。

後面兩篇我們會介紹其他排序方法，即討論其差別。

想法

一個一個遍歷，大的數字往右邊移動，遍歷完一次後少算一個，繼續遍歷直到結束。

實作

JavaScript 實作

function bubbleSort(ary) {
  for (let i = 0; i < ary.length; i++) {
    for (let j = 0; j < ary.length - i - 1; j++) {
      if (ary[j] > ary[j + 1]) {
        const smaller = ary[j + 1]
        ary[j + 1] = ary[j] // 大的往右邊移動一格
        ary[j] = smaller // 小的補上左邊
      }
    }
  }

  return ary
}

說明：

• 第二層迴圈 -1 是因為 index 從 0 開始，所以長度 -1 才會是最後一個數的 index。
• -i 是因為最大的數已經在最右邊了，所以可以少算 i 次。ex:第一圈 0，第二圈因為已經最大的數在最右邊了所以 -1 次。

Java 實作

一樣意思，沒有差很多。

static void bubbleSort(int[] arr) {
int n = arr.length;
int smaller = 0;

for(int i=0; i < n; i++){
  for(int j=1; j < (n-i); j++){
    if(arr[j-1] > arr[j]){
        smaller = arr[j-1];
        arr[j-1] = arr[j];
        arr[j] = smaller;
      }
    }
  }
}

本篇是我們介紹的第一種排序法，後面兩篇會介紹其他兩種

敬請期待~

本文同時發布於鐵人賽