最近幾天在系統的復習排序算法，之前都沒有系統性的學習過，也沒有留下過什么筆記，所以很快就忘了，這次好好地學習一下。

首先說明為了減少限制，以下代碼通通運行于Node V8引擎而非瀏覽器，源碼在我的GitHub，感興趣的話可以下載來然后運行試試。

為了方便對比各個排序算法的性能，這里先寫了一個生成大規模數組的方法——generateArray：

exports.generateArray = function(length) {let arr = Array(length);for(let i=0; i<length; i++) {arr[i] = Math.random();}return arr; }; 復制代碼

只需要輸入數組長度，即可生成一個符合長度要求的隨機數組。

一、冒泡排序

冒泡排序也成為沉淀排序(sinking sort)，冒泡排序得名于其排序方式，它遍歷整個數組，將數組的每一項與其后一項進行對比，如果不符合要求就交換位置，一共遍歷n輪，n為數組的長度。n輪之后，數組得以完全排序。整個過程符合要求的數組項就像氣泡從水底冒到水面一樣泡到數組末端，所以叫做冒泡排序。

冒泡排序是最簡單的排序方法，容易理解、實現簡單，但是冒泡排序是效率最低的排序算法，由于算法嵌套了兩輪循環（將數組遍歷了n遍），所以時間復雜度為O(n^2)。最好的情況下，給出一個已經排序的數組進行冒泡排序，時間復雜度也為O(n)。

特地感謝一下評論中@雪之祈舞的優化，每次冒泡都忽略尾部已經排序好的i項。

JavaScript實現（從小到大排序）：

function bubbleSort(arr) {//console.time('BubbleSort');// 獲取數組長度，以確定循環次數。let len = arr.length;// 遍歷數組len次，以確保數組被完全排序。for(let i=0; i<len; i++) {// 遍歷數組的前len-i項，忽略后面的i項（已排序部分）。for(let j=0; j<len - 1 - i; j++) {// 將每一項與后一項進行對比，不符合要求的就換位。if(arr[j] > arr[j+1]) {[arr[j+1], arr[j]] = [arr[j], arr[j+1]];}}}//console.timeEnd('BubbleSort');return arr; } 復制代碼

代碼中的注釋部分的代碼都用于輸出排序時間，供測試使用，下文亦如是。

二、選擇排序

選擇排序是一種原址比較排序法，大致思路：

找到數組中的最小（大）值，并將其放到第一位，然后找到第二小的值放到第二位……以此類推。

JavaScript實現（從小到大排序）：

function selectionSort(arr) {//console.time('SelectionSort');// 獲取數組長度，確保每一項都被排序。let len = arr.length;// 遍歷數組的每一項。for(let i=0; i<len; i++) {// 從數組的當前項開始，因為左邊部分的數組項已經被排序。let min = i;for(let j=i; j<len; j++) {if(arr[j]<arr[i]) {min = j;}}if(min !== i) {[arr[min], arr[i]] = [arr[i], arr[min]];}}//console.timeEnd('SelectionSort');return arr; } 復制代碼

由于嵌套了兩層循環，其時間復雜度也是O(n^2)，

三、插入排序

插入排序是最接近生活的排序，因為我們打牌時就差不多是采用的這種排序方法。該方法從數組的第二項開始遍歷數組的n-1項（n為數組長度），遍歷過程中對于當前項的左邊數組項，依次從右到左進行對比，如果左邊選項大于（或小于）當前項，則左邊選項向右移動，然后繼續對比前一項，直到找到不大于（不小于）自身的選項為止，對于所有大于當前項的選項，都在原來位置的基礎上向右移動了一項。

示例：

// 對于如下數組 var arr = [2,1,3,5,4,3]; // 從第二項（即arr[1]）開始遍歷， // 第一輪： // a[0] >= 1為true，a[0]右移， arr = [2,2,3,5,4,3]; // 然后1賦給a[0]， arr = [1,2,3,5,4,3]; // 然后第二輪： // a[1] >= 3不成立，該輪遍歷結束。 // 第三輪; // a[2] >= 5不成立，該輪遍歷結束。 // 第四輪： // a[3] >= 4為true，a[3]右移， arr = [1,2,3,5,5,3]; // a[2] >= 4不成立，將4賦給a[3]，然后結束該輪遍歷。 arr = [1,2,3,4,5,3]; // a[4] >= 3成立，a[4]右移一位， arr = [1,2,3,4,5,5]; // arr[3] >= 3成立，arr[3]右移一位， arr = [1,2,3,4,4,5]; // arr[2] >= 3成立，arr[2]右移一位， arr = [1,2,3,3,4,5]; // arr[1] >= 3不成立，將3賦給a[2]，結束該輪。 arr = [1,2,3,3,4,5]; // 遍歷完成，排序結束。 復制代碼

如果去掉比較時的等號的話，可以減少一些步驟，所以在JavaScript代碼中減少了這部分， JavaScript實現（從小到大排序）：

function insertionSort(arr) {//console.time('InsertionSort');let len = arr.length;for(let i=1; i<len; i++) {let j = i;let tmp = arr[i];while(j > 0 && arr[j-1] > tmp) {arr[j] = arr[j-1];j--;}arr[j] = tmp;}//console.timeEnd('InsertionSort');return arr; } 復制代碼

插入排序比一般的高級排序算法（快排、堆排）性能要差，但是還是具有以下優點的：

• 實現起來簡單，理解起來不是很復雜。
• 對于較小的數據集而言比較高效。
• 相對于其他復雜度為O(n^2)的排序算法（冒泡、選擇）而言更加快速。這一點在文章最后的測試中可以看出來。
• 穩定、及時……

四、歸并排序

到目前為止，已經介紹了三種排序方法，包括冒泡排序、選擇排序和插入排序。這三種排序方法的時間復雜度都為O(n^2)，其中冒泡排序實現最簡單，性能最差，選擇排序比冒泡排序稍好，但是還不夠，插入排序是這三者中表現最好的，對于小數據集而言效率較高。這些原因導致三者的實用性并不高，都是最基本的簡單排序方法，多用于教學，很難用于實際中，從這節開始介紹更加高級的排序算法。

歸并排序是第一個可以用于實際的排序算法，前面的三個性能都不夠好，歸并排序的時間復雜度為O(nlogn)，這一點已經由于前面的三個算法了。

值得注意的是，JavaScript中的Array.prototype.sort方法沒有規定使用哪種排序算法，允許瀏覽器自定義，FireFox使用的是歸并排序法，而Chrome使用的是快速排序法。

歸并排序的核心思想是分治，分治是通過遞歸地將問題分解成相同或者類型相關的兩個或者多個子問題，直到問題簡單到足以解決，然后將子問題的解決方案結合起來，解決原始方案的一種思想。

歸并排序通過將復雜的數組分解成足夠小的數組（只包含一個元素），然后通過合并兩個有序數組（單元素數組可認為是有序數組）來達到綜合子問題解決方案的目的。所以歸并排序的核心在于如何整合兩個有序數組，拆分數組只是一個輔助過程。

示例：

// 假設有以下數組，對其進行歸并排序使其按從小到大的順序排列： var arr = [8,7,6,5]; // 對其進行分解，得到兩個數組： [8,7]和[6,5] // 然后繼續進行分解，分別再得到兩個數組，直到數組只包含一個元素： [8]、[7]、[6]、[5] // 開始合并數組，得到以下兩個數組： [7,8]和[5,6] // 繼續合并，得到 [5,6,7,8] // 排序完成 復制代碼

JavaScript實現（從小到大排序）：

function mergeSort(arr) {//console.time('MergeSort');//let count = 0;console.log(main(arr));//console.timeEnd('MergeSort');//return count;// 主函數。function main(arr) {// 記得添加判斷，防止無窮遞歸導致callstack溢出，此外也是將數組進行分解的終止條件。if(arr.length === 1) return arr;// 從中間開始分解，并構造左邊數組和右邊數組。let mid = Math.floor(arr.length/2);let left = arr.slice(0, mid);let right = arr.slice(mid);// 開始遞歸調用。return merge(arguments.callee(left), arguments.callee(right));}// 數組的合并函數，left是左邊的有序數組，right是右邊的有序數組。function merge(left, right) {// il是左邊數組的一個指針，rl是右邊數組的一個指針。let il = 0,rl = 0,result = [];// 同時遍歷左右兩個數組，直到有一個指針超出范圍。while(il < left.length && rl < right.length) {//count++;// 左邊數組的當前項如果小于右邊數組的當前項，那么將左邊數組的當前項推入result，反之亦然，同時將推入過的指針右移。if(left[il] < right[rl]) {result.push(left[il++]);}else {result.push(right[rl++]);}}// 記得要將未讀完的數組的多余部分讀到result。return result.concat(left.slice(il)).concat(right.slice(rl));} } 復制代碼

注意是因為數組被分解成為了只有一個元素的許多子數組，所以merge函數從單個元素的數組開始合并，當合并的數組的元素個數超過1時，即為有序數組，仍然還可以繼續使用merge函數進行合并。

歸并排序的性能確實達到了應用級別，但是還是有些不足，因為這里的merge函數新建了一個result數組來盛放合并后的數組，導致空間復雜度增加，這里還可以進行優化，使得數組進行原地排序。

五、快速排序

快速排序由Tony Hoare在1959年發明，是當前最為常用的排序方案，如果使用得當，其速度比一般算法可以快兩到三倍，比之冒泡排序、選擇排序等可以說快成千上萬倍。快速排序的復雜度為O(nlogn)，其核心思想也是分而治之，它遞歸地將大數組分解為小數組，直到數組長度為1，不過與歸并排序的區別在于其重點在于數組的分解，而歸并排序的重點在于數組的合并。

基本思想：

在數組中選取一個參考點（pivot），然后對于數組中的每一項，大于pivot的項都放到數組右邊，小于pivot的項都放到左邊，左右兩邊的數組項可以構成兩個新的數組（left和right），然后繼續分別對left和right進行分解，直到數組長度為1，最后合并（其實沒有合并，因為是在原數組的基礎上操作的，只是理論上的進行了數組分解）。

基本步驟：

• （1）首先，選取數組的中間項作為參考點pivot。
• （2）創建左右兩個指針left和right，left指向數組的第一項，right指向最后一項，然后移動左指針，直到其值不小于pivot，然后移動右指針，直到其值不大于pivot。
• （3）如果left仍然不大于right，交換左右指針的值（指針不交換），然后左指針右移，右指針左移，繼續循環直到left大于right才結束，返回left指針的值。
• （4）根據上一輪分解的結果（left的值），切割數組得到left和right兩個數組，然后分別再分解。
• （5）重復以上過程，直到數組長度為1才結束分解。

JavaScript實現（從小到大排序）：

function quickSort(arr) {let left = 0,right = arr.length - 1;//console.time('QuickSort');main(arr, left, right);//console.timeEnd('QuickSort');return arr;function main(arr, left, right) {// 遞歸結束的條件，直到數組只包含一個元素。if(arr.length === 1) {// 由于是直接修改arr，所以不用返回值。return;}// 獲取left指針，準備下一輪分解。let index = partition(arr, left, right);if(left < index - 1) {// 繼續分解左邊數組。main(arr, left, index - 1);}if(index < right) {// 分解右邊數組。main(arr, index, right);}}// 數組分解函數。function partition(arr, left, right) {// 選取中間項為參考點。let pivot = arr[Math.floor((left + right) / 2)];// 循環直到left > right。while(left <= right) {// 持續右移左指針直到其值不小于pivot。while(arr[left] < pivot) {left++;}// 持續左移右指針直到其值不大于pivot。while(arr[right] > pivot) {right--;}// 此時左指針的值不小于pivot，右指針的值不大于pivot。// 如果left仍然不大于right。if(left <= right) {// 交換兩者的值，使得不大于pivot的值在其左側，不小于pivot的值在其右側。[arr[left], arr[right]] = [arr[right], arr[left]];// 左指針右移，右指針左移準備開始下一輪，防止arr[left]和arr[right]都等于pivot然后導致死循環。left++;right--;}}// 返回左指針作為下一輪分解的依據。return left;} } 復制代碼

快速排序相對于歸并排序而言加強了分解部分的邏輯，消除了數組的合并工作，并且不用分配新的內存來存放數組合并結果，所以性能更加優秀，是目前最常用的排序方案。

之前還在知乎上看到過一個回答，代碼大致如下（從小到大排序）：

function quickSort(arr) {// 當數組長度不大于1時，返回結果，防止callstack溢出。if(arr.length <= 1) return arr;return [// 遞歸調用quickSort，通過Array.prototype.filter方法過濾小于arr[0]的值，注意去掉了arr[0]以防止出現死循環。...quickSort(arr.slice(1).filter(item => item < arr[0])),arr[0],...quickSort(arr.slice(1).filter(item => item >= arr[0]))]; } 復制代碼

以上代碼有利于對快排思想的理解，但是實際運用效果不太好，不如之前的代碼速度快。

六、堆排序

如果說快速排序是應用性最強的排序算法，那么我覺得堆排序是趣味性最強的排序方法，非常有意思。

堆排序也是一種很高效的排序方法，因為它把數組作為二叉樹排序而得名，可以認為是歸并排序的改良方案，它是一種原地排序方法，但是不夠穩定，其時間復雜度為O(nlogn)。

實現步驟：

• （1）由數組構造一個堆結構，該結構滿足父節點總是大于（或小于）其子節點。
• （2）從堆結構的最右邊的葉子節點開始，從右至左、從下至上依次與根節點進行交換，每次交換后，都要再次構建堆結構。值得注意的是每次構建堆結構時，都要忽略已經交換過的非根節點。

數組構建的堆結構：

// 數組 var arr = [1,2,3,4,5,6,7]; // 堆結構1/ \2 3/ \ / \ 4 5 6 7 復制代碼

可以發現對于數組下標為i的數組項，其左子節點的值為下標2*i + 1對應的數組項，右子節點的值為下標2*i + 2對應的數組項。

實際上并沒有在內存中開辟一塊空間構建堆結構來存儲數組數據，只是在邏輯上把數組當做二叉樹來對待，構建堆結構指的是使其任意父節點的子節點都不大于（不小于）父節點。

JavaScript實現（從小到大排序）：

function heapSort(arr) {//console.time('HeapSort');buildHeap(arr);for(let i=arr.length-1; i>0; i--) {// 從最右側的葉子節點開始，依次與根節點的值交換。[arr[i], arr[0]] = [arr[0], arr[i]];// 每次交換之后都要重新構建堆結構，記得傳入i限制范圍，防止已經交換的值仍然被重新構建。heapify(arr, i, 0);}//console.timeEnd('HeapSort');return arr;function buildHeap(arr) {// 可以觀察到中間下標對應最右邊葉子節點的父節點。let mid = Math.floor(arr.length / 2);for(let i=mid; i>=0; i--) {// 將整個數組構建成堆結構以便初始化。heapify(arr, arr.length, i);}return arr;}// 從i節點開始下標在heapSize內進行堆結構構建的函數。function heapify(arr, heapSize, i) {// 左子節點下標。let left = 2 * i + 1,// 右子節點下標。right = 2 * i + 2,// 假設當前父節點滿足要求（比子節點都大）。largest = i;// 如果左子節點在heapSize內，并且值大于其父節點，那么left賦給largest。if(left < heapSize && arr[left] > arr[largest]) {largest = left;}// 如果右子節點在heapSize內，并且值大于其父節點，那么right賦給largest。if(right < heapSize && arr[right] > arr[largest]) {largest = right;}if(largest !== i) {// 如果largest被修改了，那么交換兩者的值使得構造成一個合格的堆結構。[arr[largest], arr[i]] = [arr[i], arr[largest]];// 遞歸調用自身，將節點i所有的子節點都構建成堆結構。arguments.callee(arr, heapSize, largest);}return arr;} } 復制代碼

堆排序的性能稍遜于快速排序，但是真的很有意思。

七、性能對比

通過console.time()和console.timeEnd()查看排序所用時間，通過generateArray()產生大規模的數據，最終得到如下結論：

通過對冒泡排序的測試，得到以下數據：

BubbleSort: 406.567ms 復制代碼

給10000（一萬）條數據進行排序，耗時406毫秒。

BubbleSort: 1665.196ms 復制代碼

給20000（兩萬）條數據進行排序，耗時1.6s。

BubbleSort: 18946.897ms 復制代碼

給50000（五萬）條數據進行排序，耗時19s。 由于機器不太好，當數據量達到100000時基本就非常漫長了，具體多久也沒等過，這已經可以看出來性能非常不好了。

通過對選擇排序的測試，得到以下數據：

SelectionSort: 1917.083ms 復制代碼

對20000（兩萬）條數據進行排序，耗時1.9s。

SelectionSort: 12233.060ms 復制代碼

給50000（五萬）條數據進行排序時，耗時12.2s，可以看出相對于冒泡排序而言已經有了進步，但是遠遠不夠。還可以看出隨著數據量的增長，排序的時間消耗越來越大。

通過對插入排序的測試，得到以下數據：

InsertionSort: 273.891ms 復制代碼

對20000（兩萬）條數據進行排序，耗時0.27s。

InsertionSort: 1500.631ms 復制代碼

對50000（五萬）條數據進行排序，耗時1.5s。

InsertionSort: 7467.029ms 復制代碼

對100000（十萬）條數據進行排序，耗時7.5秒，對比選擇排序，又有了很大的改善，但是仍然不夠。

通過對歸并排序的測試，得到以下數據：

MergeSort: 287.361ms 復制代碼

對100000（十萬）條數據進行排序，耗時0.3秒，真的很優秀了hhh，

MergeSort: 2354.007ms 復制代碼

對1000000（一百萬）條數據進行排序，耗時2.4s，絕對的優秀，難怪FireFox會使用這個來定義Array.prototype.sort方法，

MergeSort: 26220.459ms 復制代碼

對10000000（一千萬）條數據進行排序，耗時26s，還不錯。 接下來看快排。

通過對快速排序的測試，得到以下數據：

QuickSort: 51.446ms 復制代碼

100000（十萬）條數據排序耗時0.05s，達到了可以忽略的境界，

QuickSort: 463.528ms 復制代碼

1000000（一百萬）條數據排序耗時0.46s，也基本可以忽略，太優秀了，

QuickSort: 5181.508ms 復制代碼

10000000（一千萬）條數據排序耗時5.2s，完全可以接受。

通過對堆排序的測試，得到以下數據：

HeapSort: 3124.188ms 復制代碼

對1000000（一百萬）條數據進行排序，耗時3.1s，遜色于快速排序和歸并排序，但是對比其他的排序方法還是不錯的啦。

HeapSort: 41746.788ms 復制代碼

對10000000（一千萬）條數據進行排序，耗時41.7s，不太能接受。

八、結論

以前都認為排序方法隨便用用無可厚非，現在想想確實挺naive的hhh，想到了以前實習的時候，SQL Server幾百萬數據幾秒鐘就排序完成了，這要是用冒泡排序還不得等到兩眼發黑？通過這次學習總結排序算法，尤其是對于每種方法性能的測試，我深刻地認識到了算法設計的重要性，只有重視算法的設計、復雜度的對比，才能寫出優秀的算法，基于優秀的算法才能寫出性能出色的應用！

此外，由于對于算法復雜度的研究不夠深入，理解只停留在表面，所以文中如果存在有錯誤，懇請大牛不吝賜教！

最后，我想說一聲，支持阮老師！

原文發布時間為：2018年05月24日 原文作者：DM.Zhong 本文來源掘金如需轉載請聯系原作者

總結

以上是生活随笔為你收集整理的六种排序算法的JavaScript实现以及总结的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。