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;
}
}
}
}

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

敬請期待~

本文同時發布於鐵人賽