巧用數組下標完成O(n)排序？

來自專欄阿里雲中台前端/全棧團隊專欄60 人贊了文章

前言：

其實不管你用哪門語言，都會涉及到排序，而且排序是直接影響一個程序性能的關鍵詞，所以顯得尤為重要，而且我們通常也會從時間複雜度和空間複雜度的角度去定義一個排序演算法的優劣，排序的演算法也有很多，最普遍為人所知的就是快速排序，時間複雜度是:最優：O(n),最差：O(n*n),期望：O(n*logn),空間複雜度就是：最優：O(1) 最差：O(n) 期望：O(logn)，今天我們就來看一下，如何完成數據的O(n)時間複雜度排序！

姻緣：

我上大二的時候開始學習的演算法和數據結構，當時剛接觸排序演算法，一個夏天的下午，無意中想到一個問題，能不能通過某些方式，通過映射，為排序的目標增加有序的權重，最後按順序輸出呢？於是想到了數組的方式，因為數組本身的下標就是有序的，而減法是最直接的映射方式了，當時有些興奮的告訴老師，結果一頓質疑，後來看到了計數排序之後，也很驚訝，驚訝的不是和我的想法不謀而合，而是，為什麼老師都不知道這個的存在，之後工作後，發現，好像大家對這些演算法相關的也開始淡化開來，所以下面就簡單講下計數排序吧

計數排序：

你可以想像下面的桶就是數組了，然後目標和0相減就能映射到桶的位置，也就是在數組的位置，這樣最後一次輸出就能得到一個有序的序列了，時間複雜度就是O(n)了，話不多少上代碼：

//需要排序的數組const sources = [5,8,1,24,4,52,3,23,42,4,5,3,42,3,5,62,35];//標識最大最小值，確定桶區間let min = 0;let max = 0;//用於存放有序數組的桶let listArr = null;//尋找桶區間for(let num of sources){ num < min && (min = num); num > max && (max = num);}listArr = new Array(max-min+1);//排序for(let num of sources){ listArr[num-min] = listArr[num-min] || {value:0,repeat:0}; listArr[num-min].value = num; listArr[num-min].repeat++; }//輸出 去重for(let cj of listArr){ ci && cj.value && console.log(cj.value);}

優點：

插入排序，快速，穩定

缺點：

之前我們也說了，評價一個演算法的重要標誌除了時間複雜度之外還有的就是空間複雜度了，也能想到，試想下如果只有兩個數字的排序，[0,10000000]，那我們至少準備多少桶子？

結論：

時間複雜度：O(n+k) n為個數，k為區間

空間複雜度：O(K)

計數排序：100以內最快的排序，非常適合做大數據量的尾部排序和壓縮

桶排序：

計數排序是插入排序，桶就開始具有了比較的概念，重點在下面的桶

你會發現計數排序的桶每次只能裝載一個位置，取決於它插入無比較的特殊性，桶排序就是下面的桶可以裝10個數字，然後每個桶內再做桶排序或者其他排序

優點：

穩定，快速

缺點：

適合均勻區間

總結：

時間複雜度：桶排序的平均時間複雜度為線性的O(n+c)，c=n*(logn-logm), m為桶的個數,期望為線性的O(n)

空間複雜度：O(n+m)

適合均勻區間的排序，此時效率會遠高於快排，數量越大越快但是也越浪費空間

思考（map-reduce）：

其實我覺得桶排序優點hadoop 的 map-reduce思想，舉個栗子：我手上有一副撲克牌，怎樣完成快速的排序？其實我們都知道一副撲克牌有四種花色，我們可以將這四種花色映射的分發給四個人，然後這四個人排完序之後匯總到一個人手裡就完成了排序，其實這裡就是簡單的map-reduce的思想了，這裡的map是第一步映射分配花色，map的切片大小是4，reduce就是這四個人了

所以，我們可以先為大量數據進行一個有效的map，然後每個reduce進行自己的排序，這樣最後進行一個匯總

但是這個方法也存在一個很強的局限條件內：大數據量，跳躍區間，區間內高密度

而且不同的數據根據map切片的大小，效果差距明顯，不一定越大越好，時間複雜度也不一定會保證在理論值，但是也是一種特殊數據處理的思路吧

總結：

自己本身作為前端來說，隨著前端角色的變化有page變為app的過程，我相信對於前端性能的要求也越來越高，前端處理數據的場景也會越來越多的，所以，我相信演算法在前端的角色也會慢慢的增加