采用基数排序方式对数组进行排序
基数排序百科:基数排序排序(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
算法分析:
- 时间复杂度
基数排序的时间复杂度为O(n*k). - 空间复杂度
基数排序的时间复杂度为O(n + k). - 算法稳定性
基数排序是一种稳定排序算法.
代码实现-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]
参考:
考察要点:
- 数组
- 排序
