前端排序演算法總結

作者：zimo

https://segmentfault.com/a/1190000011294349

前言

排序演算法可能是你學編程第一個學習的演算法，還記得冒泡嗎？

當然，排序和查找兩類演算法是面試的熱門選項。如果你是一個會寫快排的程序猿，面試官在比較你和一個連快排都不會寫的人的時候，會優先選擇你的。那麼，前端需要會排序嗎？答案是毋庸置疑的，必須會。現在的前端對計算機基礎要求越來越高了，如果連排序這些演算法都不會，那麼發展前景就有限了。本篇將會總結一下，在前端的一些排序演算法。如果你喜歡我的文章，歡迎評論，歡迎Star~。歡迎關注我的github博客

正文

首先，我們可以先來看一下js自身的排序演算法sort()

Array.sort

相信每個使用js的都用過這個函數，但是，這個函數本身有些優點和缺點。我們可以通過一個例子來看一下它的功能：

相信你也已經看出來它在處理上的一些差異了吧。首先，js中的sort會將排序的元素類型轉化成字元串進行排序。不過它是一個高階函數，可以接受一個函數作為參數。而我們可以通過傳入內部的函數，來調整數組的升序或者降序。

sort函數的性能：相信對於排序演算法性能來說，時間複雜度是至關重要的一個參考因素。那麼，sort函數的演算法性能如何呢？通過v8引擎的源碼可以看出，Array.sort是通過javascript來實現的，而使用的演算法是快速排序，但是從源碼的角度來看，在實現上明顯比我們所使用的快速排序複雜多了，主要是做了性能上的優化。所以，我們可以放心的使用sort()進行排序。

冒泡排序

冒泡排序，它的名字由來於一副圖——魚吐泡泡，泡泡越往上越大。

回憶起這個演算法，還是最初大一的c++課上面。還是自己上台，在黑板上實現的呢！

思路：第一次循環，開始比較當前元素與下一個元素的大小，如果比下一個元素小或者相等，則不需要交換兩個元素的值；若比下一個元素大的話，則交換兩個元素的值。然後，遍歷整個數組，第一次遍歷完之後，相同操作遍歷第二遍。

圖例：

代碼實現：

代碼地址：https://jsbin.com/wawusap/edit?js,console

性能：

時間複雜度：平均時間複雜度是O(n^2)

空間複雜度：由於輔助空間為常數，所以空間複雜度是O(1);

改進：

我們可以對冒泡排序進行改進，使得它的時間複雜度在大多數順序的情況下，減小到O(n);

1.加一個標誌位，如果沒有進行交換，將標誌位置為false，表示排序完成。

代碼地址：https://jsbin.com/seyonuq/edit?js,console

2.記錄最後一次交換的位置， 因為最後一次交換的數，是在這一次排序當中最大的數，之後的數都比它大。在最佳狀態時，時間複雜度也會縮小到O(n);

代碼地址：https://jsbin.com/moruvet/edit?js,console

選擇排序

選擇排序，即每次都選擇最小的，然後換位置

思路：

第一遍，從數組中選出最小的，與第一個元素進行交換；第二遍，從第二個元素開始，找出最小的，與第二個元素進行交換；依次循環，完成排序

圖例：

代碼實現：

代碼地址：https://jsbin.com/tagutas/edit?js,console

性能：

時間複雜度：平均時間複雜度是O(n^2)，這是一個不穩定的演算法，因為每次交換之後，它都改變了後續數組的順序。

空間複雜度：輔助空間是常數，空間複雜度為O(1);

插入排序

插入排序，即將元素插入到已排序好的數組中

思路：

首先，循環原數組，然後，將當前位置的元素，插入到之前已排序好的數組中，依次操作。

圖例：

代碼實現：

代碼地址：https://jsbin.com/punuta/edit?js,console

性能：

時間複雜度：平均演算法複雜度為O(n^2)

空間複雜度：輔助空間為常數，空間複雜度是O(1)

我們仨之間

其實，三個演算法都是難兄難弟，因為演算法的時間複雜度都是在O(n^2)。在最壞情況下，它們都需要對整個數組進行重新調整。只是選擇排序比較不穩定。

快速排序

快速排序，從它的名字就應該知道它很快，時間複雜度很低，性能很好。它將排序演算法的時間複雜度降低到O(nlogn)

思路：

首先，我們需要找到一個基數，然後將比基數小的值放在基數的左邊，將比基數大的值放在基數的右邊，之後進行遞歸那兩組已經歸類好的數組。

圖例：

原圖片太大，放一張小圖，並且附上原圖片地址，有興趣的可以看一下：

GIF

原圖片地址

代碼實現：

代碼地址：https://jsbin.com/jeqayi/edit?js,console

性能：

時間複雜度：平均時間複雜度O(nlogn)，只有在特殊情況下會是O(n^2)，不過這種情況非常少

空間複雜度：輔助空間是logn，所以空間複雜度為O(logn)

歸併排序

歸併排序，即將數組分成不同部分，然後注意排序之後，進行合併

思路：

首先，將相鄰的兩個數進行排序，形成n/2對，然後在每兩對進行合併，不斷重複，直至排序完。

圖例：

代碼實現：

代碼地址：https://jsbin.com/qazupis/edit?js,console

代碼地址：https://jsbin.com/fojuyuh/edit?js,console

性能：

時間複雜度：平均時間複雜度是O(nlogn)

空間複雜度：輔助空間為n，空間複雜度為O(n)

基數排序

基數排序，就是將數的每一位進行一次排序，最終返回一個正常順序的數組。

思路：

首先，比較個位的數字大小，將數組的順序變成按個位依次遞增的，之後再比較十位，再比較百位的，直至最後一位。

圖例：

代碼實現：

代碼地址：https://jsbin.com/yewonaq/edit?js,console

性能：

時間複雜度：平均時間複雜度O(k*n)，最壞的情況是O(n^2)

總結

我們一共實現了6種排序演算法，對於前端開發來說，熟悉前面4種是必須的。特別是快排，基本面試必考題。本篇的內容總結分為六部分：

冒泡排序

選擇排序

插入排序

快速排序

歸併排序

基數排序

排序演算法，是演算法的基礎部分，需要明白它的原理，總結下來排序可以分為比較排序和統計排序兩種方式，本篇前5種均為比較排序，基數排序屬於統計排序的一種。希望看完的你，能夠去動手敲敲代碼，理解一下

如果你對我寫的有疑問，可以評論，如我寫的有錯誤，歡迎指正。你喜歡我的博客，請給我關注Star~呦。大家一起總結一起進步。歡迎關注我的github博客

覺得本文對你有幫助？請分享給更多人

關注「前端大學」，提升前端技能

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！