数组-基数排序

采用基数排序方式对数组进行排序

基数排序百科:基数排序排序(Distribution Sort),属于分配式排序,又称桶子法.它是透过键值对部分资讯,将要排序的元素分配至某些桶中.藉以达到排序的作用.

摘一个示例做个说明.
示例 1：
输入: [0,5,9,3,12,7]
输出: [0,3,5,7,9,12]

算法原理:

将所有待比较数值（正整数）统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列。

基数排序的方式可以采用LSD（Least significant digital）或MSD（Most significant digital），LSD的排序方式由键值的最右边开始，而MSD则相反，由键值的最左边开始。

算法演示 基数排序演示.gif

算法分析:

1. 时间复杂度
   基数排序的时间复杂度为O(n*k).
2. 空间复杂度
   基数排序的时间复杂度为O(n + k).
3. 算法稳定性
   基数排序是一种稳定排序算法.

代码实现-Swift版本:

func radixSort(_ num: inout [Int], _ gap: Int){
    // 数组最大最小元素
    let maxNum: Int = num.max()!
    let minNum: Int = num.min()!
    let maxLength: Int = numberLength(maxNum)
    
    // 桶的个数
    let bucketCount: Int = (maxNum - minNum) / gap + 1
    // 初始化桶
    var  bucketArray: [[Int]] = [[Int]](repeating: [Int](), count: bucketCount)
    
    for digit in 1 ..< maxLength {
        for item in num {
            let baseNum = fetchBaseNumber(item, digit)
            bucketArray[baseNum].append(baseNum)
            
        }
        //出桶
        var index = 0
        for i in 0 ..< bucketArray.count{
            while !bucketArray[i].isEmpty {
                num[index] = bucketArray[i].remove(at: 0)
                index += 1
            }
        }
    }
}

func fetchBaseNumber(_ num : Int, _ digit : Int)->Int{
    if digit > 0 && digit <= numberLength(num) {
        var numArr : Array<Int> = []
        for char in "\(num)" {
            numArr.append(Int("\(char)")!)
        }
        return numArr[numArr.count-digit]
    }
    return 0
}

func numberLength(_ num : Int)->Int{
    return "\(num)".count
}

测试用例:

var nums = [3,44,38,5,47,15,36,26,27,2,46,4,19,50,48]

参考:

• 基数排序百科
• 一像素

考察要点:

• 数组
• 排序