[Swift]基数排序 | Radix sort

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号：山青咏芝（shanqingyongzhi）
➤博客园地址：山青咏芝（https://www.cnblogs.com/strengthen/）
➤GitHub地址：https://github.com/strengthen/LeetCode
➤原文地址：https://www.cnblogs.com/strengthen/p/11075286.html 
➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。
➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

1、定义

基数排序是一种非比较型整数排序算法，又称“桶子法”（bucket sort）或bin sort，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。由于整数也可以表达字符串（比如名字或日期）和特定格式的浮点数，所以基数排序也不是只能使用于整数。

基数排序的方式可以采用：

 (1)、LSD（Least significant digital）：排序方式由数值的最右边（低位）开始。

 (2)、MSD（Most significant digital）：由数值的最左边（高位）开始。

2、基数排序、计数排序、桶排序中对桶的使用方法上的差异：

基数排序：根据键值的每位数字来分配桶。

计数排序：每个桶只存储单一键值。

桶排序：每个桶存储一定范围的数值。

3、算法原理：基数排序是通过“分配”和“收集”过程来实现排序。

(1)、分配，先从个位开始，根据位值(0-9)分别放到0~9号桶中（比如64,个位为4，则放入4号桶中）

(2)、收集，再将放置在0~9号桶中的数据按顺序放到数组中

重复(1)(2)过程，从个位到最高位（比如32位无符号整形最大数3494967296，最高位10位）。

4、算法分析

最坏时间复杂度：其中w是存储每个密钥所需的位数。

最坏空间复杂度：

5、LSD基数排序

最低位优先法首先依据最低位关键码Kd对所有对象进行一趟排序，再依据次低位关键码Kd-1对上一趟排序的结果再排序，依次重复，直到依据关键码K1最后一趟排序完成，就可以得到一个有序的序列。使用这种排序方法对每一个关键码进行排序时，不需要再分组，而是整个对象组。因为分配和收集阶段，数字符合先入先出的关系。因此可以用10个队列来保存 0-9 上分配的数字，在收集阶段，按先入先出的顺序取出每个桶中的数字，依次放到原数组中。

LSD代码1：

import Foundation
//MARK:基数排序LSD
func radixSort(_ unsortedArray: [Int]) -> [Int]{
    var unsortedArray = unsortedArray
    
    var tempArray = [Int]()
    var maxValue = 0
    var maxDigit = 0
    var level = 0
    
    repeat {
        var buckets = [[Int]]()
        for _ in 0..<10 {
            buckets.append([Int]())
        }
        
        for i in 0..<unsortedArray.count {
            let elementValue = unsortedArray[i]
            let num = pow(10.0, Double(level))
            let divident = level < 1 ? 1 : NSDecimalNumber(decimal:Decimal(num)).intValue
            let mod = elementValue / divident % 10
            buckets[mod].append(elementValue)
            
            if maxDigit == 0 {
                if elementValue > maxValue {
                    maxValue = elementValue
                }
            }
        }
        
        tempArray.removeAll()
        for element in buckets {
            tempArray.append(contentsOf: element)
        }
        
        if maxDigit == 0 {
            while maxValue > 0 {
                maxValue = maxValue / 10
                maxDigit += 1
            }
        }
        
        unsortedArray = tempArray
        level += 1
        
    } while (level < maxDigit)
    
    return tempArray
}

测试:

var arr:[Int] = [1,9,2,8,3,7,4,6,5,10,11,12]
print(radixSort(arr))
//Print [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]

LSD代码2：

import Foundation
//MARK:基数排序LSD
func radixSort(_ arr:inout [Int]) {
    if arr.count == 0 {
        return
    }
    var list:[[Int]] = [[Int]](repeating:[Int](),count:10)
    
    let maxDigit:Int = maxlength(arr: arr)
    var tempArr:[Int] = arr
    for i in 0..<maxDigit {
        for j in 0..<arr.count {
            let index:Int = highDigit(num: tempArr[j], index: i)
            list[index].append(tempArr[j])
        }
        saveBucketData(bucketlist: &list, arr: &tempArr)
    }
    arr = tempArr
}
​
// 桶的数据插入数组
private func saveBucketData(bucketlist:inout [[Int]],arr:inout [Int]) {
    var index:Int = 0
    for i in 0..<bucketlist.count {
        var bucket:[Int] = bucketlist[i]
        if bucket.count > 0 {
            for j in 0..<bucket.count {
                arr[index] = bucket[j]
                index += 1
            }
        }
        bucketlist[i].removeAll() // 注意清空桶数据
    }
}
​
private func highDigit(num:Int,index:Int)->Int {
    let base:Double = pow(10, Double(index))
    let high:Int = (num / Int(base)) % 10
    return high
}
​
// 最大数字的位数
private func maxlength(arr:[Int])->Int {
    var max:Int = 0
    for i in 0..<arr.count {
        let count:Int = positionOfNum(number: arr[i])
        if count > max {
            max = count
        }
    }
    return max
}
​
// 统计数字的位数
private func positionOfNum(number:Int)->Int {
    var count:Int = 0
    var num:Int = number
    while num%10 > 0  {
        count += 1
        num = num / 10
    }
    return count
}

测试：

var arr:[Int] = [1,9,2,8,3,7,4,6,5,10,11,12]
print(radixSort(arr))
//Print [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]

LSD代码3：

import Foundation
//MARK:基数排序LSD
func radixSort(_ arr:inout [Int]){
    let n = arr.count
    let maxNum:Int = arr.max()!
    let d:Double = pow(10.0, Double(String(maxNum).count))
    var k:Int = 1
    //桶
    var t:[[Int]] = [[Int]](repeating:[Int](repeating:0,count:n), count: 10)
    //记录每个桶中存入数的个数
    var num:[Int] = [Int](repeating: 0, count: n)
    while(Double(k) < d)
    {
        for a in arr
        {
            let m:Int = (a / k) % 10
            t[m][num[m]] = a
            num[m] += 1
        }
        var c:Int = 0
        for i in 0..<n
        {
            if num[i] != 0
            {
                for j in 0..<num[i]
                {
                    arr[c] = t[i][j]
                    c += 1
                }
            }
            num[i] = 0
        }
        k = k * 10
    }
}

测试：

var arr:[Int] = [1,9,2,8,3,7,4,6,5,10,11,12]
print(radixSort(arr))
//Print [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]

6、MSD基数排序

最高位优先法通常是一个递归的过程：

(1)、先根据最高位关键码K1排序，得到若干对象组，对象组中每个对象都有相同关键码K1。

(2)、再分别对每组中对象根据关键码K2进行排序，按K2值的不同，再分成若干个更小的子组，每个子组中的对象具有相同的K1和K2值。

(3)、依此重复，直到对关键码Kd完成排序为止。

(4)、 最后，把所有子组中的对象依次连接起来，就得到一个有序的对象序列。

import Foundation
//MARK:基数排序MSD
//MSD调用时指定最高位数d
func radixSort(_ arr:inout [Int],_ d:Int){
    let len:Int = arr.count
    //分为0~9的序列空间，用队列保存每个桶分配的数据
    var radixArray:[[Int]] = [[Int]](repeating: [Int](), count: 10)
    //位数大于0，且数组长度大于1
    if d >= 1 && len > 1
    {
        //分配过程
        for i in 0..<len
        {
            let num:Int = GetNumInPos(arr[i], d)
            radixArray[num].append(arr[i])
        }
        var i:Int = 0
        var j:Int = 0
         //收集
        while(i < 10)
        {
            //递归,对每个子桶从次高位开始分配
            radixSort(&radixArray[i], d - 1)
            
            while(!radixArray[i].isEmpty)
            {
                //取队列首部数据依次插入原数组
                arr[j] = radixArray[i].first!
                j += 1
                radixArray[i].removeFirst()
            }
            i += 1
        }
    }
}
​
func GetNumInPos(_ num:Int, _ pos:Int)-> Int
{
    var temp:Int =  1
    for _ in 0..<(pos - 1)
    {
        temp *= 10
    }
    return (num / temp) % 10
}

测试：

var arr:[Int] = [1,9,2,8,3,7,4,6,5,10,11,12]
radixSort(&arr,arr.count)
print(arr)
//Print [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]