本文是對(duì) Swift Algorithm Club 翻譯的一篇文章。
Swift Algorithm Club是 raywenderlich.com網(wǎng)站出品的用Swift實(shí)現(xiàn)算法和數(shù)據(jù)結(jié)構(gòu)的開源項(xiàng)目，目前在GitHub上有18000+??浸须，我初略統(tǒng)計(jì)了一下移怯，大概有一百左右個(gè)的算法和數(shù)據(jù)結(jié)構(gòu)，基本上常見的都包含了和橙，是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/Radix Sort
基數(shù)排序(Radix Sort)
基數(shù)排序是一種排序算法，它將整數(shù)數(shù)組作為輸入建丧，并使用排序子程序（通常是另一種有效的排序算法）來按整數(shù)基數(shù)或者它們的數(shù)字對(duì)整數(shù)進(jìn)行排序排龄。 Counting Sort和Bucket Sort通常用作Radix Sort的子程序。
例子
- Input Array: [170, 45, 75, 90, 802, 24, 2, 66]
- Output Array (Sorted): [2, 24, 45, 66, 75, 90, 170, 802]
第一步：
此算法的第一步是定義數(shù)字翎朱，或者更確切地說是我們將用于排序的“base”或基數(shù)橄维。
對(duì)于這個(gè)例子，我們將radix = 10拴曲，因?yàn)槲覀冊(cè)谑纠惺褂玫恼麛?shù)是基數(shù)10争舞。
第二步：
下一步是簡(jiǎn)單地迭代n次（其中n是輸入數(shù)組中最大整數(shù)中的位數(shù)），并且在每次迭代時(shí)對(duì)當(dāng)前數(shù)字執(zhí)行排序子程序澈灼。
算法中的行動(dòng)
我們來看看我們的示例輸入數(shù)組竞川。
我們數(shù)組中的最大整數(shù)是802，它有三位數(shù)（一叁熔，十委乌，百）。 因此荣回，我們的算法將迭代三次遭贸，同時(shí)對(duì)每個(gè)整數(shù)的數(shù)字執(zhí)行一些排序算法。
- Iteration 1: 170, 90, 802, 2, 24, 45, 75, 66
- Iteration 2: 802, 2, 24, 45, 66, 170, 75, 90
- Iteration 3: 2, 24, 45, 66, 75, 90, 170, 802
代碼
import Foundation
// 不能處理負(fù)數(shù)
public func radixSort(_ array: inout [Int]) {
let radix = 10
var done = false
var index: Int
var digit = 1
while !done {
done = true
var buckets: [[Int]] = [] // 我們的排序子程序是桶排序心软，所以讓我們預(yù)定義我們的桶
for _ in 1...radix {
buckets.append([])
}
for number in array {
index = number / digit
buckets[index % radix].append(number)
if done && index > 0 {
done = false
}
}
var i = 0
for j in 0..<radix {
let bucket = buckets[j]
for number in bucket {
array[i] = number
i += 1
}
}
digit *= radix
}
}
// 小數(shù)組的測(cè)試
var array: [Int] = [19, 4242, 2, 9, 912, 101, 55, 67, 89, 32]
radixSort(&array)
print(array)
// 大數(shù)組的測(cè)試
var bigArray = [Int](repeating: 0, count: 1000)
var i = 0
while i < 100 {
bigArray[i] = Int(arc4random_uniform(1000) + 1)
i += 1
}
radixSort(&bigArray)
print(bigArray)
更多查看基數(shù)排序的維基百科
基數(shù)排序的中文維基百科
作者：Christian Encarnacion
翻譯：Andy Ron
校對(duì)：Andy Ron
翻譯后補(bǔ)充
基數(shù)排序?qū)?shù)組[53, 3, 542, 748, 14, 214, 154, 63, 616]的排序壕吹，示意圖(來源：https://www.cnblogs.com/skywang12345/p/3603669.html) 說明：
