本文是對(duì) Swift Algorithm Club 翻譯的一篇文章伪朽。
Swift Algorithm Club是 raywenderlich.com網(wǎng)站出品的用Swift實(shí)現(xiàn)算法和數(shù)據(jù)結(jié)構(gòu)的開(kāi)源項(xiàng)目导犹，目前在GitHub上有18000+??湖苞，我初略統(tǒng)計(jì)了一下彬檀，大概有一百左右個(gè)的算法和數(shù)據(jù)結(jié)構(gòu)，基本上常見(jiàn)的都包含了，是iOSer學(xué)習(xí)算法和數(shù)據(jù)結(jié)構(gòu)不錯(cuò)的資源。
??andyRon/swift-algorithm-club-cn是我對(duì)Swift Algorithm Club摇庙，邊學(xué)習(xí)邊翻譯的項(xiàng)目。由于能力有限遥缕，如發(fā)現(xiàn)錯(cuò)誤或翻譯不妥卫袒，請(qǐng)指正，歡迎pull request单匣。也歡迎有興趣夕凝、有時(shí)間的小伙伴一起參與翻譯和學(xué)習(xí)??烤蜕。當(dāng)然也歡迎加??，??????????迹冤。
本文的翻譯原文和代碼可以查看??swift-algorithm-club-cn/Counting Sort
計(jì)數(shù)排序(Counting Sort)
Counting sort is an algorithm for sorting a collection of objects according to keys that are small integers. It operates by counting the number of objects that have each distinct key values, and using arithmetic on those counts to determine the positions of each key value in the output sequence.
計(jì)數(shù)排序是一種根據(jù)小整數(shù)鍵對(duì)對(duì)象集合進(jìn)行排序的算法。通過(guò)計(jì)算具有每個(gè)不同鍵值的對(duì)象的數(shù)量來(lái)操作虎忌，并對(duì)這些計(jì)數(shù)使用算術(shù)來(lái)確定輸出序列中每個(gè)鍵值的位置泡徙。
例子
為了理解算法，讓我們來(lái)看一個(gè)小例子膜蠢。
考慮數(shù)組: [ 10, 9, 8, 7, 1, 2, 7, 3 ]
第一步：
第一步是計(jì)算數(shù)組中每個(gè)項(xiàng)的總出現(xiàn)次數(shù)堪藐。 第一步的輸出將是一個(gè)新的數(shù)組，如下所示：
Index 0 1 2 3 4 5 6 7 8 9 10
Count 0 1 1 1 0 0 0 2 1 1 1
譯注： 這邊Index的最大值對(duì)應(yīng)于挑围，數(shù)組中最大值10礁竞。
這是完成第一步的代碼：
let maxElement = array.max() ?? 0
var countArray = [Int](repeating: 0, count: Int(maxElement + 1))
for element in array {
countArray[element] += 1
}
第二步：
在此步驟中，算法嘗試確定在每個(gè)元素之前放置的元素的數(shù)量杉辙。通過(guò)第一步已經(jīng)知道每個(gè)元素的總出現(xiàn)次數(shù)模捂，可以得到。方法就是把前一個(gè)計(jì)數(shù)和當(dāng)前計(jì)數(shù)相加存儲(chǔ)到每個(gè)索引中（對(duì)應(yīng)代碼就是countArray[index] + countArray[index - 1]）蜘矢。
計(jì)數(shù)數(shù)組如下：
Index 0 1 2 3 4 5 6 7 8 9 10
Count 0 1 2 3 3 3 3 5 6 7 8
第二步的代碼：
for index in 1 ..< countArray.count {
let sum = countArray[index] + countArray[index - 1]
countArray[index] = sum
}
第三步
這是算法的最后一步狂男。 原始數(shù)組中的每個(gè)元素都放置在第二步的輸出定義的位置。例如品腹，數(shù)字10將放在輸出數(shù)組中的索引7處岖食。 此外，當(dāng)您放置元素時(shí)舞吭，您需要將計(jì)數(shù)減少1泡垃，因?yàn)閺臄?shù)組中減少了許多元素。
最終的輸出是：
Index 0 1 2 3 4 5 6 7
Output 1 2 3 7 7 8 9 10
以下是最后一步的代碼：
var sortedArray = [Int](repeating: 0, count: array.count)
for element in array {
countArray[element] -= 1
sortedArray[countArray[element]] = element
}
return sortedArray
性能
該算法使用簡(jiǎn)單循環(huán)對(duì)集合進(jìn)行排序羡鸥。 因此蔑穴，運(yùn)行整個(gè)算法的時(shí)間是O(n+k)其中O(n)表示初始化輸出數(shù)組所需的循環(huán)，O(k)是創(chuàng)建計(jì)數(shù)數(shù)組所需的循環(huán)兄春。
該算法使用長(zhǎng)度為n + 1和n的數(shù)組澎剥，因此所需的總空間為O(2n)。 因此赶舆，對(duì)于密鑰沿著數(shù)字線分散在密集區(qū)域中的集合哑姚，它可以節(jié)省空間。
作者：Ali Hafizji
翻譯：Andy Ron
校對(duì)：Andy Ron
翻譯后補(bǔ)充
計(jì)數(shù)排序假設(shè)n個(gè)輸入元素中的每一個(gè)都是在0到k區(qū)間內(nèi)的一個(gè)整數(shù)芜茵，其中k為某個(gè)整數(shù)叙量。當(dāng)k=O(n)時(shí)，排序的運(yùn)行時(shí)間為Θ(n)九串。
計(jì)數(shù)排序的思想是绞佩，對(duì)每一個(gè)輸入元素寺鸥，計(jì)算小于它的元素個(gè)數(shù)，如果有10個(gè)元素小于它品山，那么它就應(yīng)該放在11的位置上胆建，如果有17個(gè)元素小于它，它就應(yīng)該放在18的位置上肘交。當(dāng)有幾個(gè)元素相同時(shí)笆载，這一方案要略做修改，因?yàn)椴荒馨阉鼈兎旁谕粋€(gè)輸出位置上涯呻。下圖（來(lái)源于《算法導(dǎo)論》）展示了實(shí)際的運(yùn)行過(guò)程凉驻。
構(gòu)造輔助數(shù)組C，C的長(zhǎng)度為k复罐。第一次遍歷A后涝登，得到[0,k)區(qū)間上每個(gè)數(shù)出現(xiàn)的次數(shù)，將這些次數(shù)寫入C效诅，得到圖(a)的結(jié)果胀滚。然后把C中每個(gè)元素變成前面所有元素的累加和，得到圖(b)的結(jié)果填帽。接下來(lái)蛛淋，再次從后向前遍歷數(shù)組A，根據(jù)取出的元素查找C中對(duì)應(yīng)下標(biāo)的值篡腌，再把這個(gè)值作為下標(biāo)找到B中的位置褐荷，即是該元素排序后的位置。例如嘹悼，圖中A的最后一個(gè)元素是3叛甫，找到C[3]是7，再令B[7]=3即可杨伙，然后順便把C[3]減一其监，這是防止相同的數(shù)被放到同一個(gè)位置。
計(jì)數(shù)排序的時(shí)間代價(jià)可以這樣計(jì)算限匣，第一次遍歷A并計(jì)算C所花時(shí)間是Θ(n)抖苦，C累加所花時(shí)間是Θ(k)，再次遍歷A并給B賦值所花時(shí)間是Θ(n)米死，因此锌历，總時(shí)間為Θ(k + n)。在實(shí)際中峦筒，當(dāng)k=O(n)時(shí)究西，我們一般會(huì)采用計(jì)數(shù)排序，這時(shí)的運(yùn)行時(shí)間為Θ(n)物喷。
