計(jì)數(shù)排序
計(jì)數(shù)排序是一種非基于比較的排序算法，其空間復(fù)雜度和時(shí)間復(fù)雜度均為O(n+k)拱燃，其中k是整數(shù)的范圍迅办』滋恚基于比較的排序算法時(shí)間復(fù)雜度最小是O(nlogn)的。該算法于1954年由 Harold H. Seward 提出松邪。
計(jì)數(shù)排序的核心在于將輸入的數(shù)據(jù)值轉(zhuǎn)化為鍵存儲(chǔ)在額外開辟的數(shù)組空間中坞琴。作為一種線性時(shí)間復(fù)雜度的排序，計(jì)數(shù)排序要求輸入的數(shù)據(jù)必須是有確定范圍的整數(shù)逗抑。
算法步驟
花O(n)的時(shí)間掃描一下整個(gè)序列 A剧辐，獲取最小值 min 和最大值 max
開辟一塊新的空間創(chuàng)建新的數(shù)組 B，長度為 ( max - min + 1)
數(shù)組 B 中 index 的元素記錄的值是 A 中某元素出現(xiàn)的次數(shù)
最后輸出目標(biāo)整數(shù)序列邮府，具體的邏輯是遍歷數(shù)組 B荧关，輸出相應(yīng)元素以及對(duì)應(yīng)的個(gè)數(shù)
算法演示
排序動(dòng)畫過程解釋
首先，掃描一下整個(gè)序列
獲得最小值為 2 褂傀，最大值為 7
新建數(shù)組包含 2~7 的元素
再次掃描序列忍啤，將序列的值放置在新建數(shù)組中
掃描數(shù)字 5，數(shù)組中 index 為 3 的值為 5仙辟，次數(shù)為 1
掃描數(shù)字 3同波，數(shù)組中 index 為 1 的值為 3，次數(shù)為 1
掃描數(shù)字 4叠国，數(shù)組中 index 為 2 的值為 4未檩，次數(shù)為 1
掃描數(shù)字 7，數(shù)組中 index 為 5 的值為 7粟焊，次數(shù)為 1
掃描數(shù)字 2冤狡，數(shù)組中 index 為 0 的值為 2，次數(shù)為 1
掃描數(shù)字 4项棠，數(shù)組中 index 為 2 的值為 4悲雳，次數(shù)為 2
掃描數(shù)字 3，數(shù)組中 index 為 1 的值為 3香追，次數(shù)為 2
按照這種節(jié)奏合瓢，掃描結(jié)束后，新建數(shù)組中存放了整個(gè)序列以及每個(gè)數(shù)字出現(xiàn)的次數(shù)
最后輸出目標(biāo)整數(shù)序列
輸出數(shù)字 2透典，同時(shí)數(shù)組中 index 為 0 的值為 2 的元素次數(shù)變?yōu)?0
輸出數(shù)字 3晴楔，同時(shí)數(shù)組中 index 為 1 的值為 3 的元素次數(shù)變?yōu)?1
同樣的操作迁央，整個(gè)序列就完全輸出了
代碼實(shí)現(xiàn)
作者：五分鐘學(xué)算法
鏈接：http://www.reibang.com/p/315000771cea
來源：簡書
著作權(quán)歸作者所有。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系作者獲得授權(quán)滥崩，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處。
