• 设为首页
  • 点击收藏
  • 手机版
    手机扫一扫访问
    迪恩网络手机版
  • 关注官方公众号
    微信扫一扫关注
    公众号

[Swift]基数排序|Radixsort

原作者: [db:作者] 来自: [db:来源] 收藏 邀请

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号:山青咏芝(shanqingyongzhi)
➤博客园地址:山青咏芝(https://www.cnblogs.com/strengthen/
➤GitHub地址:https://github.com/strengthen/LeetCode
➤原文地址:

热烈欢迎,请直接点击!!!

进入博主App Store主页,下载使用各个作品!!!

注:博主将坚持每月上线一个新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]
 

鲜花

握手

雷人

路过

鸡蛋
该文章已有0人参与评论

请发表评论

全部评论

专题导读
上一篇:
Swift 2.0初探发布时间:2022-07-13
下一篇:
Swift基础语法发布时间:2022-07-13
热门推荐
热门话题
阅读排行榜

扫描微信二维码

查看手机版网站

随时了解更新最新资讯

139-2527-9053

在线客服(服务时间 9:00~18:00)

在线QQ客服
地址:深圳市南山区西丽大学城创智工业园
电邮:jeky_zhao#qq.com
移动电话:139-2527-9053

Powered by 互联科技 X3.4© 2001-2213 极客世界.|Sitemap