JavaScript 中的計算機科學：冒泡排序
排序算法是計算機科學教育的基石之一。目的不是教你幾十種不同的數據排序方法，因為你永遠不需要在職業生涯中手動實現它們。相反，它們被用作教授算法理論的工具，向您展示解決單個問題的多種方法。所以我開始用 JavaScript 和冒泡排序做同樣的事情。
冒泡排序通常是第一個教授的排序算法，因為它是效率最低但在概念上最容易理解的排序算法之一。基本思想是一次比較兩個項目，並確保它們的順序正確，然後再轉到其他項目。在每次傳遞結束時，一個值“冒泡”到正確的位置，最終只留下其他項目進行排序。基本算法如下：
- 比較第一項和第二項。
- 如果第一項應該在第二項之後，請交換它們。
- 比較第二項和第三項。
- 如果第二項應該在第三項之後，請交換它們。
- 繼續直到到達數據集的末尾。
然後重複此過程多次，直到數據集完全排序。每次通過時，需要評估的項目更少，因為每次通過都會將至少一個項目留在正確的最終位置。為了更好地說明算法，考慮一個數組 [3, 2, 4, 5, 1] .
如果這個數組要按升序排序，第一步是比較 3 和 2。因為 3 應該在 2 之後，所以交換項目，結果是 [2, 3, 4, 5, 1] .接下來將3與4進行比較。由於已經安排妥當，所以不做任何更改。然後，將 4 與 5 進行比較，再次不採取任何行動。最後一步是將 5 與 1 進行比較，由於它們無序，因此交換它們。這導致 [2, 3, 4, 1, 5] .這樣就完成了第一次遍歷，數組中的最後一項現在位於正確的永久位置，因此下一次遍歷可以省略最後一項。
所以我們重新開始，比較 2 和 3（無交換）、3 和 4（無交換）以及 4 和 1（無序所以交換它們），結果為 [2, 3, 1, 4, 5] .這樣就完成了第二遍，現在最後兩個項目的順序正確。第三遍只進行兩次比較，2 和 3（無交換），然後 3 和 1（交換），得到 [2, 1, 3, 4, 5] .現在，最後三個項目的順序正確。最後一遍只是比較 2 和 1（交換），最終得到 [1, 2, 3, 4, 5] 的結果 .您還可以查看此視頻，以很好的圖形方式描述算法的工作原理。
實現冒泡排序的第一步是創建一個方法來交換數組中的兩個項目。這種方法在許多效率較低的排序算法中很常見。一個簡單的 JavaScript 實現是：
function swap(items, firstIndex, secondIndex){
var temp = items[firstIndex];
items[firstIndex] = items[secondIndex];
items[secondIndex] = temp;
}
如前所述，該算法效率極低，因為它需要與數據進行如此多的交互：對於每個 n 數組中的項，必須有 *n 2 * 實現算法的操作。通過在另一個循環中包含一個循環，這很容易在代碼中實現：
function bubbleSort(items){
var len = items.length,
i, j, stop;
for (i=0; i < len; i++){
for (j=0, stop=len-i; j < stop; j++){
if (items[j] > items[j+1]){
swap(items, j, j+1);
}
}
}
return items;
}
外部循環控制對數組進行多少次傳遞，而內部循環實際執行數組項的比較。內部循環通過使用外部循環計數並從數組中的項目總數中減去它來確定在哪個項目停止比較。雖然有一些方法可以稍微提高冒泡排序的性能，例如跟踪是否發生任何交換，但這是該算法的最簡單實現。
冒泡排序的另一種形式可以通過以相反的順序遍歷數組來完成，因此數組前面的項目首先按順序放置。為此，只需反轉循環：
function bubbleSort(items){
var len = items.length,
i, j;
for (i=len-1; i >= 0; i--){
for (j=len-i; j >= 0; j--){
if (items[j] < items[j-1]){
swap(items, j, j-1);
}
}
}
return items;
}
這兩個版本都可以在我的 GitHub 項目“JavaScript 中的計算機科學”中找到。
再一次，冒泡排序不是你在職業生涯中可能會用到的東西。它只是一種更深入地了解算法的工具，也是構建進一步知識的基礎。內置 Array.prototype.sort() 幾乎在所有情況下都應該使用這種方法，因為它可以快速有效地完成工作。
