百萬考生分數如何排序 - 計數排序
關注 「碼哥位元組」，這裡有算法系列、大資料存儲系列、Spring 系列、源碼架構拆解系列、面試系列……敬請期待。設定星标不迷路
其實計數排序是桶排序的一種特殊情況。 桶排序的核心思想是将要排序的資料分到幾個有序的桶裡，每個桶裡的資料再單獨進行排序。桶内排完序之後，再把每個桶裡的資料按照順序依次取出，組成的序列就是有序的了。
「碼哥位元組」之前分享了百萬訂單如何根據金額排序，就是運用了桶排序。
計數排序的核心在于将輸入的資料值轉換成鍵儲存在數組下标，是以作為一種線性時間複雜度的排序，輸入的資料必須是有确定且範圍不大的整數。比如當要排序的 n 個資料，所處的範圍不大的時候，最大值是 m，我們就把資料化劃分成 m 個桶。每個桶内的資料都是相同的大小，也就不需要桶内排序，這是與桶排序最大的差別。
場景重制
聯考查分數系統，系統會展示我們的成績以及所在省的排名。假如 H 省有 80 萬考生，如何通過成績快速排序得出排名呢？
再比如統計每個省人口的每個年齡人數并且從小到大排序，又如何實作呢？
考生的滿分是 750 分，最小是 0 分，符合我們之前說的條件：資料範圍小且是整數。我們可以劃分為 751 個桶分别對應分數為 0 ~ 750 分數的考生。
接着開始周遊考生資料，每個考生按照分數則劃分到對應數組下标，相同數組的下标則将該下标的資料值 + 1。其實就是每個數組下标位置對應的是數列資料出現的次數，最後直接周遊該數組，輸出元素的下标就是對應的分數，下标對應的元素值是多少我們就輸出幾次。
桶内的資料都是分數相同的考生，是以并不需要再進行排序。我們隻需要依次掃描每個桶，将桶内的考生依次輸出到一個數組中，就實作了 80 萬考生的排序。因為隻涉及掃描周遊操作，是以時間複雜度是 O(n)。
計數排序的算法思想就是這麼簡單，跟桶排序非常類似，隻是桶的大小粒度不一樣。不過，為什麼這個排序算法叫“計數”排序呢？“計數”的含義來自哪裡呢？
剛剛所說的是樸素版的排序，隻是簡單的按照統計數組的下标輸出元素值，并沒有給原始數列進行排序。
在現實中，給學生排序遇到相同分數的就分不清誰是誰？比如并列 95 分的張無忌與周芷若，卻不知道是張無忌哪個是周芷若。帶着這些問題，請繼續看下面的圖解思路…...
圖解思路
為了友善了解，對資料進行簡化，假設隻有 8 個考生，分數在 0 ~ 5 之間，是以有 5 個桶對應考生分數，值代表每種分數的考生個數。考生的原始資料我們放在數組 SourceArray[8] = {2，5，3，0，2，3，0，3}。
考生的成績從 0 到 5，使用 大小數組為 6 的 countArray[6] 表示桶，下标對應分數，值存儲的是該分數的考生個數。我們隻要周遊一遍原始資料就可以得到 countArray[6]。
可以知道，分數為 3 分的學生有 3 個， < 3 分的學生有 4 個，是以成績 = 3 分的學生在排序後的有序數組 sortedArray[8] 中的下标會在 4, 5, 6 的位置，也就是排名是 5,6,7。如下圖所示
我們如何計算出每個分數的考生在有序數組對應的存儲位置呢？這個思路很巧妙，主要是對之前的 countArray[6] 做一下轉換。
劃重點了同學們：**我們對 countArray[6] 數組順序求和，countArray[k] 裡面存儲的是 ≤ k 分數的考生個數 **。這樣加的目的是什麼？
其實是讓統計數組存儲的元素值，等于相應考試成績資料的最終排序位置的序号。
現在我就要講計數排序中最複雜、最難了解的一部分了，堅持啃下來。
- 從後往前周遊原始輸入數組 SourceArray[8] = {2，5，3，0，2，3，0，3}，掃描成績為 3 的小強，我們就從 數組 countArray[6] 中取出下标 = 3 的值 = 7，也就意味着包括自己在内，分數 ≤ 3 的考生有 7 位，表示在 sortedArray 中排在第七位，當把小強成績放到 sortedArray 之後 ≤ 3 的成績就剩下 6 個了，是以 countArray[3] 要 - 1，變成 6.
- 周遊成績表倒數第二個資料，成績是 0，找到在 countArray[0] 的元素 = 2，表示排名第二，同時 countArray[0] 的元素值 -1。
- 以此類推，當掃描完整個原始數組之後， sortedArray 資料就是按照分數從小到大有序排列了。
代碼實戰
整個步驟:
- 查找數列最大值。
- 根據數列最大值确定 countArray 統計數組長度。
- 周遊原始資料填充統計數組，統計對應元素的個數。
- 統計數組做變形，後面的元素等于前面元素之和。
- 倒序周遊原始數組，從統計數組中找到元素的正确排位，輸出到結果數組中。
源碼詳見 GitHub: https://github.com/UniqueDong/algorithms
package com.zero.algorithms.linear.sort;
/**
* 公衆号：碼哥位元組
* 計數排序
*/
public class CountingSort {
public int[] sort(int[] sourceArray) {
if (sourceArray == null || sourceArray.length <= 1) {
return new int[0];
}
// 1.查找數列最大值
int max = sourceArray[0];
for (int value : sourceArray) {
max = Math.max(max, value);
}
// 2.根據資料最大值确定統計數組長度
int[] countArray = new int[max + 1];
// 3. 周遊原始數組映射到統計數組中,統計元素的個數
for (int value : sourceArray) {
countArray[value]++;
}
// 4.統計數組變形，後面的元素等于前面元素之和。目的是定位在結果數組中的排位
for (int i = 1; i <= max; i++) {
countArray[i] += countArray[i - 1];
}
// 5.倒序周遊原始數組，從統計數組查找對應的正确位置，輸出到結果表
int[] sortedArray = new int[sourceArray.length];
for (int i = sourceArray.length - 1; i >= 0; i--) {
int value = sourceArray[i];
// 分數在 countArray 中的排名, - 1 則是結果數組的下标
int index = countArray[value] - 1;
sortedArray[index] = value;
countArray[value]--;
}
return sortedArray;
}
}
複雜度分析
第 1、3、5 步都涉及周遊原始數組，時間複雜度都是 O(n)，第 4 步統計數組變形，時間複雜度是 O(m)，是以總體的時間複雜度是 O(3n +m)，去掉系數 O(n) 時間複雜度。
空間複雜度，結果數組 O(n)。
優化思路
前面的代碼，第一步我們查找最大值，假如原始資料是 {99,98,92,80,88,87,82,88,99,97,92},最大值是 99，最小值是 80，如果直接建立 100 長度的數組，那麼 從 0 到 79 的空間全都浪費了。
要怎麼解決呢？
跟着 「碼哥位元組」來優化，很簡單，我們不再使用 max + 1 作為統計數組的長度，而是 max - min + 1 作為統計數組的長度即可。
代碼如下:
package com.zero.algorithms.linear.sort;
/**
* 公衆号：碼哥位元組
* 計數排序
*/
public class CountingSort {
public int[] sort(int[] sourceArray) {
if (sourceArray == null || sourceArray.length <= 1) {
return new int[0];
}
// 1.查找數列最大值,最小值
int max = sourceArray[0];
int min = sourceArray[0];
for (int value : sourceArray) {
max = Math.max(max, value);
min = Math.min(min, value);
}
int d = max - min;
// 2.根據資料最大值确定統計數組長度
int[] countArray = new int[d + 1];
// 3. 周遊原始數組映射到統計數組中,統計元素的個數
for (int value : sourceArray) {
countArray[value - min]++;
}
// 4.統計數組變形，後面的元素等于前面元素之和。目的是定位在結果數組中的排位
for (int i = 1; i < countArray.length; i++) {
countArray[i] += countArray[i - 1];
}
// 5.倒序周遊原始數組，從統計數組查找對應的正确位置，輸出到結果表
int[] sortedArray = new int[sourceArray.length];
for (int i = sourceArray.length - 1; i >= 0; i--) {
int value = sourceArray[i];
// 分數在 countArray 中的排名, - 1 則是結果數組的下标
int index = countArray[value - min] - 1;
sortedArray[index] = value;
countArray[value - min]--;
}
return sortedArray;
}
}
總結一下
計數排序适用于在資料範圍不大的場景中，并且隻能給非負整數排序，對于其他類型的資料，要排序的話要在不改變相對大小的情況下，轉成非負整數。
比如資料範圍 [-1000, 1000] ，就對每個資料 +1000，轉換成非負整數。
計數排序這麼強大，但是局限性主要有如下兩點：
- 當數列的最大與最小值差距過大，不适合使用計數排序。
比如 20 個随機整數，範圍在 0 - 1 億之間，這時候使用計數排序需要建立長度為 1 億的數組，嚴重浪費空間。
- 數列元素不是整數，不适合使用
參考資料
極客時間 《資料結構與算法之美》
漫畫算法-小灰的算法之旅
關注 「碼哥位元組」背景回複加群，可添加個人微信進入專屬技術群。
讀者的分享、點贊、在看、收藏三連是最大的鼓勵
随手點選下方廣告，給「碼哥」加雞腿。