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

[Swift]八大排序算法(八):基数排序

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

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

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

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

注:博主将坚持每月上线一个新app!!!

排序分为内部排序和外部排序。

内部排序:是指待排序列完全存放在内存中所进行的排序过程,适合不太大的元素序列。

外部排序:指的是大文件的排序,即待排序的记录存储在外存储器上,待排序的文件无法一次装入内存,需要在内存和外部存储器之间进行多次数据交换,以达到排序整个文件的目的。

当N小于20的时候,插入排序具有最好的性能。

当N大于20时,快速排序具有最好的性能,尽管归并排序(merge sort)和堆排序(heap sort)复杂度都为nlog2(n)。


基数排序

基数排序(Radix Sort)属于“分配式排序”(distribution sort),又称“桶子法”(bucket sort)或bin sort,顾名思义,它是透过键值的部份信息,将要排序的元素分配至某些“桶”中,藉以达到排序的作用。

基数排序法是属于稳定性的排序,其时间复杂度为O(nlog(r)m),其中r为所采取的基数,而m为堆数,在某些时候,基数排序法的效率高于其它的稳定性排序法。

基本思想:

将整数按位数切割成不同的数字,然后按每个位数分别比较。

具体做法:

将所有待比较数值统一为同样的数位长度,数位较短的数前面补零。

然后,从最低位开始,依次进行一次排序。这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列。


 ViewController.swift文件:运行时间(3.3862s)

  1 import UIKit
  2 
  3 class ViewController: UIViewController {
  4     //属性1:用来存储需要排序的数组
  5     var result : Array<Int> = Array<Int>()
  6     //属性2:统计排序花费的时间
  7     var date : Date!
  8     
  9     override func viewDidLoad() {
 10         super.viewDidLoad()
 11         // Do any additional setup after loading the view, typically from a nib.
 12         //初始化一个整形数组
 13         var array : Array<Int> = Array<Int>()
 14         //将1至100的100个整数,存入到该数组中
 15         for i in 1...100
 16         {
 17             array.append(i)
 18         }
 19         //添加一个循环语句,
 20         //用来生成一个由100个随机整数组成的数组
 21         for _ in 1...100
 22         {
 23             //首先根据数组的长度,
 24             //获得一个1至100的随机整数
 25             let temp = Int(arc4random() % UInt32(array.count))+1
 26             //根据随机值从数组中获得指定位置的整数,
 27             //并存储在用来排序的数组中
 28             let num = array[temp-1]
 29             result.append(num)
 30             //从原数组中移该随机数,以避免获得重复的数字
 31             array.remove(at: temp-1)
 32         }
 33         //添加一个循环语句,
 34         //用来生成100个自定义视图对象
 35         for i in 1...100
 36         {
 37             //初始化自定义视图对象
 38             let num = result[i-1]
 39             //并设置它的显示区域。
 40             //其中视图的高度,是当前数组中的数字的两倍大小
 41             let view = SortView(frame: CGRect(x: 10+i*3, y: 200, width: 2, height: num * 2))
 42             view.backgroundColor = .black
 43             //设置视图的标识值
 44             view.tag = i
 45             //并将视图添加到当前视图控制器的根视图
 46             self.view.addSubview(view)
 47         }
 48         //然后添加一个按钮
 49         //当用户点击该按钮时对数组进行排序
 50         let bt = UIButton(frame: CGRect(x: 10, y: 340, width: 300, height: 40))
 51         //设置背景按钮的背景颜色为橙色
 52         bt.backgroundColor = .orange
 53         //设置按钮在正常状态下的标题文字
 54         bt.setTitle("Sort", for: .normal)
 55         //给按钮对象绑定点击事件,
 56         bt.addTarget(self, action: #selector(reOrderView), for: .touchUpInside)
 57         //将按钮添加到当前视图控制器的根视图
 58         self.view.addSubview(bt)
 59     }
 60 
 61      //添加一个方法,用来响应按钮的点击事件
 62     @objc func reOrderView()
 63     {
 64         //获得当前的日期和时间
 65         date = Date()
 66         //在一个全局队列中,以异步的方式对数组进行排序
 67         //并实时调整和数组中的数值相对应的视图的位置
 68         DispatchQueue.global().async
 69         {
 70             //调用实例方法,用来实现可视化的基数排序,
 71             //该方法在下方的代码中实现
 72             self.radixSort(list: &self.result)
 73             //获得排序后的系统时间,
 74             //并在控制台输出两个时间的差值,
 75             //从而获得排序所花费的大致时间。
 76             //考虑线程休眠的影响,此数据仅做参考
 77             let endDate = Date()
 78             print(endDate.timeIntervalSince(self.date))
 79         }
 80     }
 81 
 82      //添加一个方法,用来实现具体的可视化的基数排序的功能
 83     private func radixSort(list: inout Array<Int>)
 84     {
 85         //首先初始化一个二维数组,作为10个空桶
 86         //每个空桶作为子数组,
 87         //分别存储位数为0至9的所有元素
 88         var bucket: Array<Array<Int>> = []
 89         //通过一循环语句,
 90         //往二维数组中添加10个空数组
 91         for _ in 0..<10
 92         {
 93             bucket.append([])
 94         }
 95         //接着来获得数组中的所有元素的最大值,
 96         //从而获得位数最多的元素。
 97         //例如数组中的最大值为1234
 98         //那么它的位数为4,并且也是数组中所有元素最大的位数。
 99         var maxNumber = list[0]
100         //通过循环语句,获得数组中元素的最大值
101         for item in list
102         {
103             if maxNumber < item
104             {
105                 maxNumber = item
106             }
107         }
108         //将该元素转换为字符串,
109         //从而通过字符串的长度,
110         //获得该元素的位数。
111         let maxLength = "\(maxNumber)".count
112         //添加一个循环语句,循环区间为1到最大位数。
113         //该循环语句用来进行基数排序
114         for digit in 1...maxLength
115         {
116             //通过一个实例方法,获得指定位数的值,并添加到对应的桶数组中。
117             //例如当digit的值为1时,表示获得个位数的值,
118             //并存储在对应的桶(子数组)中
119             for item in list
120             {
121                 let baseNumber = fetchBaseNumber(number: item, digit: digit)
122                 bucket[baseNumber].append(item)
123             }
124             //到此完成了入桶操作,接着进行出桶操作。
125             //即将所有桶中的数据全部取出,并依次放在数组中。
126             //首先初始化一个整形变量,作为索引值。
127             var index = 0
128             //添加一个循环语句,对十个桶进行遍历
129             for i in 0..<bucket.count
130             {
131                 //添加另一个循环语句,进行出桶的操作,
132                 //直到桶的数据为空。
133                 while !bucket[i].isEmpty
134                 {
135                     //将桶中的第一个元素删除
136                     //并将返回的被删除的元素,
137                     //存入数组中指定的索引位置。
138                     list[index] = bucket[i].remove(at: 0)
139                     //接着同步更新界面中对应的视图对象的高度
140                     self.udpateView(j: index, height: list[index])
141                     index += 1
142                 }
143             }
144         }
145     }
146 
147     //添加一个方法,用来获得指定位数的值,
148     //例如获取某个数字的个位、十位、千位等的值
149     func fetchBaseNumber(number: Int, digit: Int) -> Int
150     {
151         //在此将数字转换为字符串的方式
152         //来获得指定位数的值
153         if digit > 0 && digit <= "\(number)".count
154         {
155             //初始化一个整形数组,用来存储数字的每个位数的值
156             var numbersArray: Array<Int> = []
157             //通过一个循环语句,将数字的每个位数,
158             //添加到整形数组中
159             for char in "\(number)".characters
160             {
161                 numbersArray.append(Int("\(char)")!)
162             }
163             //最后根据位数,获取并返回数组中的值
164             return numbersArray[numbersArray.count - digit]
165         }
166         //采用0作为默认值
167         return 0
168     }
169 
170     //添加一个方法,用来更新视图的高度
171     func udpateView(j: Int, height: Int)
172     {
173         //由于需要对界面元素进行调整,
174         //所以需要切换至主线程
175         weak var weak_self = self
176         DispatchQueue.main.async
177         {
178             //根据标识值,
179             //获得和需要交换顺序的数组元素相对应的视图对象
180             //并设置它的新的高度
181             let view = weak_self?.view.viewWithTag(j+1)
182             view?.frame.size.height = CGFloat(height*2)
183         }
184         //使线程休眠0.01秒,
185         //以方便观察排序的视觉效果
186         Thread.sleep(forTimeInterval: 0.01)
187     }
188 
189     override func didReceiveMemoryWarning() {
190         super.didReceiveMemoryWarning()
191         // Dispose of any resources that can be recreated.
192     }
193 }

SortView.swift文件

 1 import UIKit
 2 
 3 class SortView: UIView {
 4     //首先重写父类的初始化方法
 5     override init(frame: CGRect)
 6     {
 7         //设置自定义视图对象的显示区域
 8         super.init(frame: frame)
 9         self.frame = frame
10     }
11 
12     //添加一个必须实现的初始化方法
13     required init?(coder aDecoder: NSCoder) {
14         fatalError("init(coder:) has not been implemented")
15     }
16     
17     //重写父类的重新布局子视图方法
18     //将在此视图中对视图进行外观设置
19     override func layoutSubviews()
20     {
21         //首先获得自定义视图在界面中对Y轴坐标
22         let y: CGFloat = 300 - frame.height
23         //然后重新设置自定义视图的位置
24         self.frame = frame
25         self.frame.origin.y = y
26         //根据自定义视图的高度,计算一个权重数值
27         //用于生成不同的背景颜色
28         let weight = frame.height / 200
29         //生成不同y色相的颜色对象,从而给自定义视图设置不同的背景颜色
30         //然后打开ViewController.swift文件
31         let color = UIColor(hue: weight, saturation: 1, brightness: 1, alpha: 1)
32         self.backgroundColor = color
33     }
34     /*
35     // Only override draw() if you perform custom drawing.
36     // An empty implementation adversely affects performance during animation.
37     override func draw(_ rect: CGRect) {
38         // Drawing code
39     }
40     */
41 }

 


鲜花

握手

雷人

路过

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

请发表评论

全部评论

专题导读
上一篇:
Swift语言指南(十)--字符串与字符发布时间:2022-07-13
下一篇:
[Swift]LeetCode114.二叉树展开为链表|FlattenBinaryTreetoLinkedList发布时间: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