氣泡排序是一種簡單的排序演算法,但它的效率相對較低,最壞的情況下的時間複雜度為 O(n^2)

儘管如此,學習它是值得的。

我們遍歷一個數組,將每個元素與其旁邊的元素進行比較。

如果右邊的元素比較小,我們就交換它們的位置。

以下是我們的實現:

const bubbleSort = (originalArray) => {
 let swapped = false

 const a = [...originalArray]

 for (let i = 1; i < a.length - 1; i++) {
 swapped = false

 for (let j = 0; j < a.length - i; j++) {
 if (a[j + 1] < a[j]) {
 ;[a[j], a[j + 1]] = [a[j + 1], a[j]]
 swapped = true
 }
 }

 if (!swapped) {
 return a
 }
 }

 return a
}

你可以看到,O(n^2) 是因為我們對數組進行了兩次循環,以檢查是否需要將項目與右邊的項目交換位置。

我們從第一個元素開始,將其與第二個元素進行比較。如果第一個元素較大,我們就交換它們。否則,我們將其保持不變,然後切換到數組的第二個元素。我們再次進行比較,直到該元素在數組中找到其位置。

以下是一個示例:

假設我們執行 bubbleSort([2, 1, 3])

首先,我們將2與1進行比較。2 > 1,所以我們將它們交換位置:

1 2 3

然後,我們將2與3進行比較。2 < 3,所以我們保持它們不變。我們跳過了最後一個元素,因為根據我們的工作流程,它始終是最大的元素。