英文 | https://blog.bitsrc.io/a-guide-to-sorting-algorithms-in-javascript-5b32da4eae1e
翻譯 | 楊小愛
排序被認為是許多程式設計語言中的一個重要概念，因為它可以幫助我們以更快、更輕松的方式定位元素。
在這篇文章中，我們将使用排序算法對數組進行排序。JavaScript 中至少有 8 種不同的排序算法。為了使這篇文章簡短但仍然充滿有用的知識，我将重點介紹以下4種算法：
- 冒泡排序
- 插入排序
- 歸并排序
- 快速排序
1、冒泡排序
冒泡排序算法是一種非常常見的算法，通常是計算機科學課程中最先教授的内容之一。這是因為冒泡排序的工作方式與我們人類對項目進行排序的方式非常相似。
讓我們從建立一個名為 bubbleSort 的函數開始。該函數将接受一個數組作為參數，它将對其進行操作以進行排序，然後将該數組傳回給我們。
在這個算法中，我們将建立一個循環，将一個項目與數組中的下一個項目進行比較。如果目前項大于下一項，則它們将被交換。這個循環将不斷重複，直到我們遇到目前項目都不大于它旁邊的項目的場景。這就是為什麼我們将使用 do while 循環而不是正常的 while 循環。
do while 循環需要一個參數，它将在運作前檢查。讓我們将此參數命名為 swap 并将其初始值設定為 false。
在循環内部，我們将檢查目前項是否大于數組中的下一項。如果是，那麼我們将首先将其存儲在一個臨時變量中，然後執行交換。為了訓示交換已執行，我們将交換的值設定為 true。
要測試此算法，隻需建立一個數字數組并将其傳遞給 bubbleSort 函數，如下所示：
const nums = [5, 10, 1, 9, 2, 8, 3, 7, 4, 6]
bubbleSort(nums) 在您的輸出中，您會注意到算法在終止之前多次列印出最終結果。這是因為該算法對數組的所有元素進行最後一次運作，以確定它們正确排序。
2、插入排序算法
在插入排序算法中，我們讓代碼相信數組中的一項是排序清單。然後比較它之前的數組中的所有項目，并決定需要在數組中插入“排序清單”的位置。
這對您來說可能聽起來有點混亂。這是有道理的，因為我們需要兩個循環，一個在另一個循環中，以執行此算法。
首先，我們将建立一個名為 insertSort 的函數，它将數組作為參數。我們将使用嵌套循環來執行排序。
以下是循環的工作方式。
首先，我們将從數組中取出一個元素并檢查它是否大于或小于它旁邊的元素。外部 for 循環将從數組的第二個元素開始，并将運作整個數組長度。
内循環将從數組的開頭開始，一直運作到外循環的目前元素。每次外循環的疊代變量的值增加時，内循環也會重置。
至于實際的排序，我們将比較外循環元素和内循環元素。如果外循環的元素較小，那麼我們将其移動到内循環元素的位置，反之亦然。為此，我們将使用數組的 slice 方法。
讓我們使用我們之前使用的相同數組來測試這個算法。
const numbers = [8, 5, 6, 9, 3, 1, 4, 2, 7, 10]
insertionSort(numbers) 這應該有效！如果考慮 8 的移動，您會注意到 8 開始在同一位置停留一段時間，并且每次疊代的持續時間變長。那是因為，算法周遊數組的所有項，然後遞增外循環疊代器的值，然後當它遇到元素 8 時，它将在移動到數組中的下一個元素之前對其進行處理。
3、歸并排序算法
分而治之！這就是歸并排序算法的工作原理。該算法将數組分解為更小的數組。然後它将對這些較小的數組進行排序，因為它們的大小較小，是以速度更快。最後，将較小的數組組合在一起為我們提供最終的排序數組。
冒泡和插入排序算法使用疊代，而歸并排序使用遞歸。遞歸是函數調用自身的地方。另一方面，疊代涉及我們的代碼中多次運作代碼塊的其他内容。
在這裡，我們将數組分成兩部分，然後将其分成更小的部分，直到我們得到一組數組，其中每個數組隻包含 2 個元素。然後我們将簡單地通過比較哪個元素更大/更小來對這個小數組進行排序，然後再次連接配接這些數組。
讓我們首先建立一個名為divide的函數，它将接收一個數組作為參數。然後該函數将檢查數組的長度是否已經小于 2，因為如果是，則不需要除以任何内容，因為小于 2 是 1，并且數組中實際上沒有其他任何内容來比較。在這種情況下，算法将簡單地将相同的數組傳回給我們。
如果數組長于 2，那麼我們将把它分成兩部分。首先我們需要找到數組的中間數。一旦我們得到它，我們将使用它 splice 方法來建立兩個較小的數組。
我們将建立另一個執行實際排序的函數。我會叫它......種類。sort 函數将兩個小數組作為參數，并分别對它們進行排序，然後将它們連接配接在一起。該函數将包含一個數組，其中将存儲已排序的元素。
會有這樣一種情況，我們已經對兩個較小的數組進行了排序，但原始數組中仍有元素。在這種情況下，我們需要首先将兩個小數組連接配接在一起，并将剩餘的元素放入一個新數組中。
我們可以使用擴充運算符 ( ... ) 将元素“擴充”到這個新數組中。
如上所示，我們在除法函數中使用了排序函數。并且，我們将劃分函數作為參數傳遞給排序函數。銜尾蛇的一個非常複雜的案例。
您可以通過将數字數組傳遞給除法函數來測試此算法。
const numbers = [8, 5, 6, 9, 3, 1, 4, 2, 7, 10]
console.log(divide(numbers)) 4、快速排序
這是遵循“分而治之”方法的另一種算法。該算法首先建立兩個較小的數組，并從數組中選取一個索引。數組的所有元素都與該元素進行比較，并根據比較被推入兩個數組之一。然後對兩個數組之一進行排序。
與本文中的所有其他算法一樣，我們将建立一個将數字數組作為輸入參數的函數。如果數組隻有一個元素，可以忽略排序并傳回相同的數組。
然後我們将選擇數組的元素将它存儲在一個單獨的變量中。然後，我們将建立兩個數組，其中的元素将在與數組的最後一個元素進行比較後被推送。為此，我們将使用 for 循環周遊數組中的每個元素。
與 mergeSort 類似，我們将使用擴充運算符 ( ... ) 将兩個數組中的元素和所選元素插入到新的最終數組中。
用一組數字測試這個算法應該會給我們以下輸出：
const numbers = [8, 5, 6, 9, 3, 1, 4, 2, 7, 10]
quickSort(numbers)
// Output
5 6
3 4 5 6
1 2 3 4 5 6
8 9
1 2 3 4 5 6 7 8 9
1 2 3 4 5 6 7 8 9 10 // Final Answer 結論
在這篇文章中，我們研究了 JavaScript 中一些衆所周知的排序算法。這些算法中的每一個都有自己的優點和缺點。
冒泡排序算法可能更容易了解，但它是本文四種算法中效率最低的。如果我們給它一個包含 10 個元素的數組，那麼更糟糕的是它會将每個元素與清單中的每個其他元素進行比較，導緻最多 100 (10*10) 個循環。
插入排序使用兩個循環。并且由于這些循環被放置在另一個循環中，時間複雜度将為 0(n^2) 形式，其中 n 是數組中的元素數。一線希望，如果數組元素需要較少的排序，該算法将比冒泡排序執行得更好。
歸并排序使用遞歸，極大地提高了排序過程的效率。歸并排序要求算法至少周遊數組的每個元素一次。但是對于每次遞歸調用，我們隻操作一半的元素。是以即使元素數量增加到原來大小的兩倍，算法也隻需要我們再調用一次遞歸。
快速排序是本文四種算法中最有效的算法。與歸并排序類似，該算法也需要至少一次周遊整個數組。但是數組大小的任何增加都不會導緻任何類型的操作增加。将數組大小加倍隻會導緻算法的一個額外操作級别。
最後，感謝您閱讀到此！我希望它能幫助你更好地了解 JavaScript 算法。如果你喜歡這篇文章，那麼請記得給我點贊。同時，也歡迎您發表評論，提出任何問題！
