作者： Tom哥
簡介：計算機研究生，校招進阿里，期間還拿過百度、華為、中興、騰訊等6家大廠offer，P7 技術專家，出過專利，CSDN博客專家，
公眾號：微觀技術，分享其他地方看不到的知識與思考，歡迎關注
有這么一道題：
今年高考，有1000萬的考生參加了考試，滿分750，小明靠了680分，他想知道自己的全國排名，如何快速排序呢？
這里面會給大家介紹幾種演算法：
一、桶排序
演算法思想
將要排序的資料拆分、分組放入幾個有序的桶里，然后分別對每一個桶中的元素排序，最后將桶中的元素依次取出，就完成了最終的排序，
例子：
對 9，8，19，2，7，15，20，6，4，1，11，17 等數字排序，（為了簡化描述，這里只列舉了12個數）
其中，最小值是 1，最大值是 20，整個區間最大跨度是 20，我們將其分成了4個桶，然后再采用
快速排序對每個桶里的元素排序，
如果待排序的資料是m個，均勻的分到n個桶中，每個桶中的元素個數 j=m/n
每個桶采用快速排序，時間復雜度是 O(j*log(j))，所有桶的時間復雜度是 O(n*j*log(j))
整理后，該演算法的時間復雜度是 O(m*log(m/n))
如果桶個數n無限接近m，那桶排序的時間復雜度近似 O(m)
適用場景
1、資料均勻分布，沒有嚴重傾斜，否則，很容易發生大部分資料集中在某幾個桶中
2、桶容易劃分，如：手機號排序就不太適合
3、桶與桶之間天然有序，不需要再單獨排序
4、一些特殊的場景，比如資料檔案很大，有幾十個G，記憶體無法一次全部加載，可以考慮分桶，分批排序
整理了一份大廠常考面試題，這份pdf包括 Java基礎、Java并發、JVM、MySQL、Redis、Spring、MyBatis、Kafka、設計模式等面試題，分享給大家，
下載地址：百度云鏈接：https://pan.baidu.com/s/1XHT4ppXTp430MEMW2D0-Bg 提取碼: s3ab
如果桶中的資料分布不均勻怎么辦？
一圖勝千言，“拆”字萬里行，大事化小，小事化了，
我們對原始資料分組選桶時，可以為每個桶設定一個計數器，當發現某個分桶的資料量偏大時，可以考慮將該桶二次拆分為若干子桶，
當然，如果子桶的資料量還是很大，我們可以進一步拆分為子子桶，
拆分的深度，可以結合具體業務情況，自己把控，
如果排序的資料的范圍不大（比如人的年齡、考試成績），采用先分桶再快速排序有些浪費，我們可以采用下面這種排序方式，
二、計數排序
計數排序的要求是排序的資料范圍不大，比如有m個數，其中最大值是i，那么可以分成i個桶，每個桶里的資料都是相同的，這樣就省掉了對桶內元素的排序，
舉個典型的場景：
我們都參加過高考，今年有1000萬的考生參加考試，滿分750，小明考了680分，他想知道自己的全國排名，如何快速排序呢？
滿分750，考生的分數最小可能是0分，最高是750分，所以我們就分為了 751 個桶，按分數將考生放入對應的桶中，
然后，再依次讀取每個桶中的資料，寫入一個陣列中，便得到了 1000萬考生的分數排名，
小明考了680分，他想快速知道自己的排名，如何實作？
方案一：遍歷排序好的陣列，由于是由大到小且有序的，我們找到第一個680的元素，便得到最終的排名，
方案二：對演算法進行優化，每個桶配備一個計數器，桶中每添加一個元素，計數器加一，這樣，你只需要將681~750 之間的桶的計數器累計求和，便得到最終的排名，
三、基數排序
上面的兩種排序，還是很好理解的，可以解決很多業務場景問題，
但如果是對若干數量的手機號由小到大排序，怎么解決呢？
我們知道，手機號是11位，范圍太大，而桶排序和計數排序，對資料范圍有較高要求，顯然手機號不太合適，
這里介紹一種新的排序演算法，基數排序，
核心思想
先比較高位的值，如果a的高位大于b的高位，那么a肯定是大于b的，后面的低位值就可以不用比較，
比如：對下面的若干英文名做排序
解題思路，如上圖所示
首先，對每個名稱的第一個字母做排序，可以采用分桶或計數排序，
同一個桶內的元素，然后提取第二個字母，再次分桶或計數排序，
回圈遍歷，直到比較完第11位，
當然，比較期間，如果某個階段，桶中的元素只有一個，那么該階段可以終止，
有點類似上面的《如果桶中的資料分布不均勻怎么辦？》解決思路，
特別注意：
上面排序的英文名字長度可能不同，我們先要做資料預處理，取最大的長度，將位數不夠的后面補"0"，
因為ASCII 值，最小的是字母A，對應的十進制是65，也是大于0，所以，補“0” 不影響排序，
適用場景
如果整體比較難度較大，數值的區間較大，不適合分桶，我們可以考慮采用分割的思想，分割出若干小段，依次對小段來比較，各個小段存在遞進關系，
關于我：Tom哥，前阿里P7技術專家，出過專利，競賽拿過獎，CSDN博客專家，負責過電商交易、社區生鮮、互聯網金融等業務，多年團隊管理經驗，
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/354631.html
標籤：java