氣泡排序是一種簡單的排序演算法,但它的效率相對較低,最壞的情況下的時間複雜度為 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,所以我們保持它們不變。我們跳過了最後一個元素,因為根據我們的工作流程,它始終是最大的元素。