英文 | https://blog.bitsrc.io/a-guide-to-sorting-algorithms-in-javascript-5b32da4eae1e

翻譯 | 楊小愛

• 冒泡排序

• 插入排序

• 歸并排序

• 快速排序

const nums = [5, 10, 1, 9, 2, 8, 3, 7, 4, 6]bubbleSort(nums)

在您的輸出中，您會注意到算法在終止之前多次打印出最終結(jié)果。這是因為該算法對數(shù)組的所有元素進行最后一次運行，以確保它們正確排序。

2、插入排序算法

在插入排序算法中，我們讓代碼相信數(shù)組中的一項是排序列表。然后比較它之前的數(shù)組中的所有項目，并決定需要在數(shù)組中插入“排序列表”的位置。

這對您來說可能聽起來有點混亂。這是有道理的，因為我們需要兩個循環(huán)，一個在另一個循環(huán)中，以執(zhí)行此算法。

首先，我們將創(chuàng)建一個名為 insertSort 的函數(shù)，它將數(shù)組作為參數(shù)。我們將使用嵌套循環(huán)來執(zhí)行排序。

以下是循環(huán)的工作方式。

首先，我們將從數(shù)組中取出一個元素并檢查它是否大于或小于它旁邊的元素。外部 for 循環(huán)將從數(shù)組的第二個元素開始，并將運行整個數(shù)組長度。

內(nèi)循環(huán)將從數(shù)組的開頭開始，一直運行到外循環(huán)的當(dāng)前元素。每次外循環(huán)的迭代變量的值增加時，內(nèi)循環(huán)也會重置。

至于實際的排序，我們將比較外循環(huán)元素和內(nèi)循環(huán)元素。如果外循環(huán)的元素較小，那么我們將其移動到內(nèi)循環(huán)元素的位置，反之亦然。為此，我們將使用數(shù)組的 slice 方法。

讓我們使用我們之前使用的相同數(shù)組來測試這個算法。

const numbers = [8, 5, 6, 9, 3, 1, 4, 2, 7, 10]insertionSort(numbers)

這應(yīng)該有效！如果考慮 8 的移動，您會注意到 8 開始在同一位置停留一段時間，并且每次迭代的持續(xù)時間變長。那是因為，算法遍歷數(shù)組的所有項，然后遞增外循環(huán)迭代器的值，然后當(dāng)它遇到元素 8 時，它將在移動到數(shù)組中的下一個元素之前對其進行處理。

3、歸并排序算法

分而治之！這就是歸并排序算法的工作原理。該算法將數(shù)組分解為更小的數(shù)組。然后它將對這些較小的數(shù)組進行排序，因為它們的大小較小，因此速度更快。最后，將較小的數(shù)組組合在一起為我們提供最終的排序數(shù)組。

冒泡和插入排序算法使用迭代，而歸并排序使用遞歸。遞歸是函數(shù)調(diào)用自身的地方。另一方面，迭代涉及我們的代碼中多次運行代碼塊的其他內(nèi)容。

在這里，我們將數(shù)組分成兩部分，然后將其分成更小的部分，直到我們得到一組數(shù)組，其中每個數(shù)組只包含 2 個元素。然后我們將簡單地通過比較哪個元素更大/更小來對這個小數(shù)組進行排序，然后再次連接這些數(shù)組。

讓我們首先創(chuàng)建一個名為divide的函數(shù)，它將接收一個數(shù)組作為參數(shù)。然后該函數(shù)將檢查數(shù)組的長度是否已經(jīng)小于 2，因為如果是，則不需要除以任何內(nèi)容，因為小于 2 是 1，并且數(shù)組中實際上沒有其他任何內(nèi)容來比較。在這種情況下，算法將簡單地將相同的數(shù)組返回給我們。

如果數(shù)組長于 2，那么我們將把它分成兩部分。首先我們需要找到數(shù)組的中間數(shù)。一旦我們得到它，我們將使用它 splice 方法來創(chuàng)建兩個較小的數(shù)組。

我們將創(chuàng)建另一個執(zhí)行實際排序的函數(shù)。我會叫它......種類。sort 函數(shù)將兩個小數(shù)組作為參數(shù)，并分別對它們進行排序，然后將它們連接在一起。該函數(shù)將包含一個數(shù)組，其中將存儲已排序的元素。

會有這樣一種情況，我們已經(jīng)對兩個較小的數(shù)組進行了排序，但原始數(shù)組中仍有元素。在這種情況下，我們需要首先將兩個小數(shù)組連接在一起，并將剩余的元素放入一個新數(shù)組中。

我們可以使用擴展運算符 ( ... ) 將元素“擴展”到這個新數(shù)組中。

如上所示，我們在除法函數(shù)中使用了排序函數(shù)。并且，我們將劃分函數(shù)作為參數(shù)傳遞給排序函數(shù)。銜尾蛇的一個非常復(fù)雜的案例。

您可以通過將數(shù)字數(shù)組傳遞給除法函數(shù)來測試此算法。

const numbers = [8, 5, 6, 9, 3, 1, 4, 2, 7, 10]console.log(divide(numbers))

4、快速排序

這是遵循“分而治之”方法的另一種算法。該算法首先創(chuàng)建兩個較小的數(shù)組，并從數(shù)組中選取一個索引。數(shù)組的所有元素都與該元素進行比較，并根據(jù)比較被推入兩個數(shù)組之一。然后對兩個數(shù)組之一進行排序。

與本文中的所有其他算法一樣，我們將創(chuàng)建一個將數(shù)字數(shù)組作為輸入?yún)?shù)的函數(shù)。如果數(shù)組只有一個元素，可以忽略排序并返回相同的數(shù)組。

然后我們將選擇數(shù)組的元素將它存儲在一個單獨的變量中。然后，我們將創(chuàng)建兩個數(shù)組，其中的元素將在與數(shù)組的最后一個元素進行比較后被推送。為此，我們將使用 for 循環(huán)遍歷數(shù)組中的每個元素。

與 mergeSort 類似，我們將使用擴展運算符 ( ... ) 將兩個數(shù)組中的元素和所選元素插入到新的最終數(shù)組中。

用一組數(shù)字測試這個算法應(yīng)該會給我們以下輸出：

const numbers = [8, 5, 6, 9, 3, 1, 4, 2, 7, 10]quickSort(numbers)// Output5 63 4 5 61 2 3 4 5 68 91 2 3 4 5 6 7 8 91 2 3 4 5 6 7 8 9 10 // Final Answer

結(jié)論

在這篇文章中，我們研究了 JavaScript 中一些眾所周知的排序算法。這些算法中的每一個都有自己的優(yōu)點和缺點。

冒泡排序算法可能更容易理解，但它是本文四種算法中效率最低的。如果我們給它一個包含 10 個元素的數(shù)組，那么更糟糕的是它會將每個元素與列表中的每個其他元素進行比較，導(dǎo)致最多 100 (10*10) 個循環(huán)。

插入排序使用兩個循環(huán)。并且由于這些循環(huán)被放置在另一個循環(huán)中，時間復(fù)雜度將為 0(n^2) 形式，其中 n 是數(shù)組中的元素數(shù)。一線希望，如果數(shù)組元素需要較少的排序，該算法將比冒泡排序執(zhí)行得更好。

歸并排序使用遞歸，極大地提高了排序過程的效率。歸并排序要求算法至少遍歷數(shù)組的每個元素一次。但是對于每次遞歸調(diào)用，我們只操作一半的元素。所以即使元素數(shù)量增加到原來大小的兩倍，算法也只需要我們再調(diào)用一次遞歸。

快速排序是本文四種算法中最有效的算法。與歸并排序類似，該算法也需要至少一次遍歷整個數(shù)組。但是數(shù)組大小的任何增加都不會導(dǎo)致任何類型的操作增加。將數(shù)組大小加倍只會導(dǎo)致算法的一個額外操作級別。

最后，感謝您閱讀到此！我希望它能幫助你更好地理解 JavaScript 算法。如果你喜歡這篇文章，那么請記得給我點贊。同時，也歡迎您發(fā)表評論，提出任何問題！

學(xué)習(xí)更多技能

請點擊下方公眾號