本文是对 Swift Algorithm Club 翻译的一篇文章。 Swift Algorithm Club是 raywenderlich.com网站出品的用Swift实现算法和数据结构的开源项目，目前在GitHub上有18000+⭐️，我初略统计了一下，大概有一百左右个的算法和数据结构，基本上常见的都包含了，是iOSer学习算法和数据结构不错的资源。 🐙andyRon/swift-algorithm-club-cn是我对Swift Algorithm Club，边学习边翻译的项目。由于能力有限，如发现错误或翻译不妥，请指正，欢迎pull request。也欢迎有兴趣、有时间的小伙伴一起参与翻译和学习🤓。当然也欢迎加⭐️，🤩🤩🤩🤨🤪。本文的翻译原文和代码可以查看🐙swift-algorithm-club-cn/Radix Sort

基数排序(Radix Sort)

基数排序是一种排序算法，它将整数数组作为输入，并使用排序子程序（通常是另一种有效的排序算法）来按整数基数或者它们的数字对整数进行排序。 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]

第一步：

此算法的第一步是定义数字，或者更确切地说是我们将用于排序的“base”或基数。对于这个例子，我们将radix = 10，因为我们在示例中使用的整数是基数10。

第二步：

下一步是简单地迭代n次（其中n是输入数组中最大整数中的位数），并且在每次迭代时对当前数字执行排序子程序。

算法中的行动

我们来看看我们的示例输入数组。

我们数组中的最大整数是802，它有三位数（一，十，百）。因此，我们的算法将迭代三次，同时对每个整数的数字执行一些排序算法。

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

// 不能处理负数
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]] = []  // 我们的排序子程序是桶排序，所以让我们预定义我们的桶
        
        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
    }
}

// 小数组的测试
var array: [Int] = [19, 4242, 2, 9, 912, 101, 55, 67, 89, 32]
radixSort(&array)
print(array)

// 大数组的测试
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)

更多查看基数排序的维基百科
 基数排序的中文维基百科

作者：Christian Encarnacion
翻译：Andy Ron
校对：Andy Ron

翻译后补充

基数排序对数组[53, 3, 542, 748, 14, 214, 154, 63, 616]的排序，示意图(来源：https://www.cnblogs.com/skywang12345/p/3603669.html) 说明：