/

JavaScript演算法：氣泡排序

JavaScript演算法：氣泡排序

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

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

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

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

以下是我們的實現：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
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
1 2 3

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

tags: [“JavaScript”, “Bubble Sort”, “Sorting Algorithm”, “Time Complexity”, “Array”]