資料結構與演算法學習筆記之為用於高考名次排序的排序演算法
前言
在高考結束以後，所有人都在等著成績，政府部門面對幾百萬的資料，你知道他們是怎麼算名次的麼？上一次學到遞迴排序以及快排，確實，用他們可以實現，可是他們的時間複雜度最低都是O（nlogn）。今天我們來看看有沒有更快捷的排序方法？
正文
桶排序
原理：
將需要排序的資料分到幾個有序的桶裡，每個桶裡的資料再單獨進行排序，排序完成，再將每個桶的資料都取出來，組成新的有序的資料。
時間複雜度：
排序的資料有n個，分在m個桶裡，每一個桶就有k=n/m個元素，每個桶都進行快排，時間複雜度為O（k*lognk），m個桶時間複雜度就為O(m*k*lognk)，因為k=n/m，所以整個桶排序的時間複雜度就 O(n*log(n/m))，當桶的個數m接近n時，桶排序的時間複雜度接近O（n）
侷限性 ：
在桶排序的過程中，劃分桶時，需要桶和桶之間有著天然的大小順序，這樣桶內元素排序完成以後就不需要在外部排序。
資料在桶之間的分佈是較均勻的。劃分不均，桶內資料，有些太多，有些太小。時間複雜度就不是常量級的。
適用環境：
適用於外部排序中， 外部排序就是資料儲存在外部磁碟中，資料量比較大記憶體有限，無法將資料全部載入到記憶體中。假如我們有30G的資料，記憶體只有8G，怎麼辦，我們可以使用桶排序的思想，將30G的資料分成6份，每個桶資料都足夠在記憶體中執行，依次排好序然後合併，就都是有序的。
計數排序
原理：
例如有8個年齡不同的人，年齡範圍為0-5之間，這8個人的考生的成績，我們放在A[8]陣列中，分別為2.5.3.0.2.3.0.3，我們分為6個桶，然後在新的陣列B[6]中，遍歷A陣列，在B中儲存對應年齡的個數。然後把陣列B[6]陣列，順序求和，變成陣列C[6].
B [6]陣列:
C[6]陣列：
後續求解如下圖
java 程式碼實現：
// 計數排序，a 是陣列，n 是陣列大小。假設陣列中儲存的都是非負整數。
public void countingSort(int[] a, int n) {
if (n <= 1) return;
// 查詢陣列中資料的範圍
int max = a[0];
for (int i = 1; i < n; ++i) {
if (max < a[i]) {
max = a[i];
}
}
int[] c = new int[max + 1]; // 申請一個計數陣列 c，下標大小 [0,max]
for (int i = 0; i <= max; ++i) {
c[i] = 0;
}
// 計算每個元素的個數，放入 c 中
for (int i = 0; i < n; ++i) {
c[a[i]]++;
}
// 依次累加
for (int i = 1; i <= max; ++i) {
c[i] = c[i-1] + c[i];
}
// 臨時陣列 r，儲存排序之後的結果
int[] r = new int[n];
// 計算排序的關鍵步驟，有點難理解
for (int i = n - 1; i >= 0; --i) {
int index = c[a[i]]-1;
r[index] = a[i];
c[a[i]]--;
}
// 將結果拷貝給 a 陣列
for (int i = 0; i < n; ++i) {
a[i] = r[i];
}
}
侷限：
1.計數排序只能用在資料範圍不大的場景中，如果資料範圍k比要排序的資料n大太多就不適合用計數排序了。
2.只能給非負整數排序。所以在給其他資料型別排序時，需要轉換為非負整數。
解答開題 ：
計算排序就像是桶排序的一種特殊排序。當排序資料為n時，所處的範圍並不大的時候，比如最大值是k，我們就將資料分為k個桶。這樣就剩去了桶內排序；
如何通過成績高效的排序出名次？
解答：我們都知道2018年高考總分為750分，我們可以分成751個桶，對應分數為0到750分，根據考生的成績，我們將所有的考生都劃分帶這些桶內，每一個桶的資料都是相同分數的考生，所有桶內的資料不需要進行排序，我們只需要依次掃描每個桶，將桶內的資料輸出到一個數組中，就實現了考生排序。
基數排序
原理：
非比較型整數排序法，其原理是將整數按位數切割成不同的數字，然後按每個位數分別比較。
侷限：
1.由於整數也可以表達字串（比如名字或日期）和特定格式的浮點數，所以也可以用基數排序演算法排序。
2.需要可以分割出獨立的“位”來比較，而且位之間有遞進關係
3.每一個“位”的資料範圍不能太大，要可以用線性排序演算法來排序。否則，時間複雜度就做不到O（n）
字母排序
為一串混亂的字元及數字排序，就像sdfHH4IUHIih8uih0HikJ1jHHHu8jyhG7YggUYF,要小寫字母排在前面，數字在中間，大寫字母在後面，我們又改怎麼排序？
解決：
利用桶排序思想，弄小寫，大寫，數字三個桶，遍歷一遍，都放進去，然後再從桶中取出來就行了。相當於遍歷了兩遍，複雜度O(n)