客服电话
APP下载
迪恩网络APP
随时随地掌握行业动态
官方微信
扫描二维码
关注迪恩网络微信公众号
|
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★ 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： 1 import Foundation 2 //MARK:基数排序LSD 3 func radixSort(_ unsortedArray: [Int]) -> [Int]{ 4 var unsortedArray = unsortedArray 5 6 var tempArray = [Int]() 7 var maxValue = 0 8 var maxDigit = 0 9 var level = 0 10 11 repeat { 12 var buckets = [[Int]]() 13 for _ in 0..<10 { 14 buckets.append([Int]()) 15 } 16 17 for i in 0..<unsortedArray.count { 18 let elementValue = unsortedArray[i] 19 let num = pow(10.0, Double(level)) 20 let divident = level < 1 ? 1 : NSDecimalNumber(decimal:Decimal(num)).intValue 21 let mod = elementValue / divident % 10 22 buckets[mod].append(elementValue) 23 24 if maxDigit == 0 { 25 if elementValue > maxValue { 26 maxValue = elementValue 27 } 28 } 29 } 30 31 tempArray.removeAll() 32 for element in buckets { 33 tempArray.append(contentsOf: element) 34 } 35 36 if maxDigit == 0 { 37 while maxValue > 0 { 38 maxValue = maxValue / 10 39 maxDigit += 1 40 } 41 } 42 43 unsortedArray = tempArray 44 level += 1 45 46 } while (level < maxDigit) 47 48 return tempArray 49 } 测试: 1 var arr:[Int] = [1,9,2,8,3,7,4,6,5,10,11,12] 2 print(radixSort(arr)) 3 //Print [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12] LSD代码2： 1 import Foundation 2 //MARK:基数排序LSD 3 func radixSort(_ arr:inout [Int]) { 4 if arr.count == 0 { 5 return 6 } 7 var list:[[Int]] = [[Int]](repeating:[Int](),count:10) 8 9 let maxDigit:Int = maxlength(arr: arr) 10 var tempArr:[Int] = arr 11 for i in 0..<maxDigit { 12 for j in 0..<arr.count { 13 let index:Int = highDigit(num: tempArr[j], index: i) 14 list[index].append(tempArr[j]) 15 } 16 saveBucketData(bucketlist: &list, arr: &tempArr) 17 } 18 arr = tempArr 19 } 20 21 // 桶的数据插入数组 22 private func saveBucketData(bucketlist:inout [[Int]],arr:inout [Int]) { 23 var index:Int = 0 24 for i in 0..<bucketlist.count { 25 var bucket:[Int] = bucketlist[i] 26 if bucket.count > 0 { 27 for j in 0..<bucket.count { 28 arr[index] = bucket[j] 29 index += 1 30 } 31 } 32 bucketlist[i].removeAll() // 注意清空桶数据 33 } 34 } 35 36 private func highDigit(num:Int,index:Int)->Int { 37 let base:Double = pow(10, Double(index)) 38 let high:Int = (num / Int(base)) % 10 39 return high 40 } 41 42 // 最大数字的位数 43 private func maxlength(arr:[Int])->Int { 44 var max:Int = 0 45 for i in 0..<arr.count { 46 let count:Int = positionOfNum(number: arr[i]) 47 if count > max { 48 max = count 49 } 50 } 51 return max 52 } 53 54 // 统计数字的位数 55 private func positionOfNum(number:Int)->Int { 56 var count:Int = 0 57 var num:Int = number 58 while num%10 > 0 { 59 count += 1 60 num = num / 10 61 } 62 return count 63 } 测试： 1 var arr:[Int] = [1,9,2,8,3,7,4,6,5,10,11,12] 2 print(radixSort(arr)) 3 //Print [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12] LSD代码3： 1 import Foundation 2 //MARK:基数排序LSD 3 func radixSort(_ arr:inout [Int]){ 4 let n = arr.count 5 let maxNum:Int = arr.max()! 6 let d:Double = pow(10.0, Double(String(maxNum).count)) 7 var k:Int = 1 8 //桶 9 var t:[[Int]] = [[Int]](repeating:[Int](repeating:0,count:n), count: 10) 10 //记录每个桶中存入数的个数 11 var num:[Int] = [Int](repeating: 0, count: n) 12 while(Double(k) < d) 13 { 14 for a in arr 15 { 16 let m:Int = (a / k) % 10 17 t[m][num[m]] = a 18 num[m] += 1 19 } 20 var c:Int = 0 21 for i in 0..<n 22 { 23 if num[i] != 0 24 { 25 for j in 0..<num[i] 26 { 27 arr[c] = t[i][j] 28 c += 1 29 } 30 } 31 num[i] = 0 32 } 33 k = k * 10 34 } 35 } 测试： 1 var arr:[Int] = [1,9,2,8,3,7,4,6,5,10,11,12] 2 print(radixSort(arr)) 3 //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)、 最后，把所有子组中的对象依次连接起来，就得到一个有序的对象序列。 1 import Foundation 2 //MARK:基数排序MSD 3 //MSD调用时指定最高位数d 4 func radixSort(_ arr:inout [Int],_ d:Int){ 5 let len:Int = arr.count 6 //分为0~9的序列空间，用队列保存每个桶分配的数据 7 var radixArray:[[Int]] = [[Int]](repeating: [Int](), count: 10) 8 //位数大于0，且数组长度大于1 9 if d >= 1 && len > 1 10 { 11 //分配过程 12 for i in 0..<len 13 { 14 let num:Int = GetNumInPos(arr[i], d) 15 radixArray[num].append(arr[i]) 16 } 17 var i:Int = 0 18 var j:Int = 0 19 //收集 20 while(i < 10) 21 { 22 //递归,对每个子桶从次高位开始分配 23 radixSort(&radixArray[i], d - 1) 24 25 while(!radixArray[i].isEmpty) 26 { 27 //取队列首部数据依次插入原数组 28 arr[j] = radixArray[i].first! 29 j += 1 30 radixArray[i].removeFirst() 31 } 32 i += 1 33 } 34 } 35 } 36 37 func GetNumInPos(_ num:Int, _ pos:Int)-> Int 38 { 39 var temp:Int = 1 40 for _ in 0..<(pos - 1) 41 { 42 temp *= 10 43 } 44 return (num / temp) % 10 45 } 测试： 1 var arr:[Int] = [1,9,2,8,3,7,4,6,5,10,11,12] 2 radixSort(&arr,arr.count) 3 print(arr) 4 //Print [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12] |
请发表评论