計數排序的2種對應關係，4個步驟，1個小技巧
計數排序
是一種
非比較、 穩定、線性時間
排序演算法，利用
額外陣列C
來統計 待排序陣列A 中元素出現的次數，然後根據陣列C輸出排序後的陣列A。其中額外陣列C第i個元素是待排序陣列A中等於i的元素出現次數。
2種對應關係
從上面的概念，可以抽象出2種對應關係：
陣列C的下標 ----------------> 陣列A中元素
陣列C的元素-----------------> 陣列A的中元素出現次數
4個演算法步驟及作用
找出陣列A中的最小值和最大值，
確定陣列C的長度
。
統計陣列A中值為i的元素出現的次數，存入陣列C的第i項
從
i=1
開始累加陣列C的計數，即：C［i］=C［i］+C［i-1］，此時C［i］值是i元素最後一次的位置，
確定元素位置。
反向遍歷陣列A填充到目標陣列，將每個元素i放在目標陣列的第C（i）項，每放一個元素就將C（i）減去1，
用來保證穩定性。
1個小技巧
累積頻率直方圖
思想，即：
C［i］=C［i］+C［i-1］，C［i］告訴我們陣列中有多少個元素小於等於它，也就是說它最後一次出現的位置。
下圖中累積後額外陣列C［2］的值4，就是說最後這個【2】元素排在陣列A的4號位置，那前面的那個【2】呢，應該排在3號位置（C［2］-1），在前面的以此類推。
程式碼實現
說這麼概念性的東西了，讓我們來看看程式碼吧。
/** * 計數排序原理： * 1。 找出陣列A中的最小值和最大值，**確定陣列C的長度**。 * 2。 統計陣列A中值為i的元素出現的次數，存入陣列C的第i項 * 3。 從**i=1**開始累加陣列C的計數，即：C［i］=C［i］+C［i-1］，此時C［i］值是i元素最後一次的位置，**用來保證穩定性。** * 4。 反向遍歷陣列A填充到目標陣列B。 */ public static int［］ sort（int［］ arr）{ int max = arr［0］； int min = arr［0］； // 1。 找出陣列arr中的最小值和最大值 for （int i = 0； i < arr。length； i++）{ if （arr［i］ > max） { max = arr［i］； } if （arr［i］ < min） { min = arr［i］； } } // 確定陣列bucket的長度： len = max - min + 1 int［］ bucket = new int［max - min +1］； // 2。 統計陣列arr中值為i的元素出現的次數，存入陣列bucket的第i項 for （int i = 0； i < arr。length； i++）{ // 注意： bucket位置是距min的偏移量 bucket［arr［i］ - min］++； } // 3。 從**i=1**開始累加陣列bucket的計數，確定i元素最後一次的位置 for （int i = 1； i < bucket。length； i++）{ bucket［i］ = bucket［i-1］ + bucket［i］； } // 4。 反向遍歷陣列A填充到目標陣列sort。 int［］ sort = new int［arr。length］； for （int i = arr。length - 1； i >= 0； i——）{ // 獲取arr［i］的位置 int position = bucket［arr［i］ - min］； // 填充到目標陣列sort， 注意： position-1 sort［position - 1］ = arr［i］； // bucket［arr［i］］減一操作， 下次所在的位置 bucket［arr［i］ - min］——； } return sort； } public static void main（String［］ args） { int［］ arr = {2，3，4，3，6，1，2，7}； System。out。println（“排序前：” + JSON。toJSONString（arr））； int［］ sortArr = sort（arr）； System。out。println（“排序後：” + JSON。toJSONString（sortArr））； }
排序結果如下：
排序前：［2，3，4，3，6，1，2，7］
排序後：［1，2，2，3，3，4，6，7］
思考問題
陣列C的長度如何確定？
從第1個對應關係可知，陣列C的長度len=陣列A中最大值 max+1。
Q1：如果陣列A中最大值是1000，那麼我們就定義陣列C的長度len為1001吧？
定義這麼大的陣列是不是有點不合理啊。我們在深入思考下第1個對應關係，其實陣列C的下標i的取值範圍是 ［陣列A的min， 陣列A的max］，那麼就有
len=max-min+1
。如果陣列A的資料範圍很大的話，此時計數排序就需要大量的記憶體和時間，這也是使用計數排序的一個限制條件。
Q2：為什麼要加1呢？
因為陣列A中元素對應的是陣列C的下標。比如，陣列A中最大值是6，從第1個對應關係可知，陣列C的最大下標值為6，即陣列C的長度為7。
總結：陣列C的長度len=max-min+1。
為什麼要進行C[i]=C[i-1]+C[i]?
https：//stackoverflow。com/questions/32223517/counting-sort-why-we-need-sum-of-previous-counts
為什麼要反向遍歷陣列？
從上面的連結裡提取了下，主要是為了解決穩定性，重複元素誰前誰後的問題。說到重複元素主要是針對
物件陣列
來說的。
經典面試題
重複值判斷問題
三色排序問題
