[Swift]八大排序算法（三）：选择排序和简单选择排序

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› 移动开发›Swift 教程

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

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

热烈欢迎，请直接点击！！！

进入博主App Store主页，下载使用各个作品！！！

注：博主将坚持每月上线一个新app！！！

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

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

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

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

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

选择排序：

是对冒泡排序法的一种改进。冒泡排序通过依次交换相邻两个顺序不合法的元素位置，从而将当前最小（大）元素放到合适的位置；而选择排序每遍历一次都记住了当前最小（大）元素的位置，最后仅需一次交换操作即可将其放到合适的位置。

原理：每一趟从待排序的记录中选出最小的元素，顺序放在已排好序的序列最后，直到全部记录排序完毕。

也即，每一趟在n-i+1(i=1，2，…n-1)个记录中选取关键字最小的记录作为有序序列中第i个记录。基于此思想的算法主要有简单选择排序、树型选择排序和堆排序。

简单选择排序:

第1趟，在待排序记录r[1]~r[n]中选出最小的记录，将它与r[1]交换；

第2趟，在待排序记录r[2]~r[n]中选出最小的记录，将它与r[2]交换；

以此类推，第i趟在待排序记录r[i]~r[n]中选出最小的记录，将它与r[i]交换，使有序序列不断增长直到全部排序完毕。

选择排序：

ViewController.swift文件：运行时间（1.0873s）

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

简单选择排序:

ViewController.swift文件：运行时间（59.2052s）

  1 import UIKit
  2 
  3 extension Array
  4 {
  5     fileprivate mutating func swap(i:Int,j:Int)
  6     {
  7         let temp = self[i]
  8         self[i] = self[j]
  9         self[j] = temp
 10     }
 11 }
 12 
 13 extension Array where Element:Comparable
 14 {
 15     mutating func selectorSort() {
 16         
 17         var min = 0
 18         
 19         for i in 0..<self.count-1
 20         {
 21             min = i
 22             
 23             for j in i+1...self.count-1
 24             {
 25                 if self[j] < self[min]
 26                 {
 27                     min = j
 28                 }
 29             }
 30             
 31             if min != i
 32             {
 33                 swap(i: min, j: i)
 34             }
 35         }
 36     }
 37 }
 38 
 39 
 40 class ViewController: UIViewController {
 41     
 42     var result : Array<Int> = Array<Int>()
 43     var date : Date!
 44     
 45     override func viewDidLoad() {
 46         super.viewDidLoad()
 47         // Do any additional setup after loading the view, typically from a nib.
 48         var array : Array<Int> = Array<Int>()
 49         
 50         for i in 1...100
 51         {
 52             array.append(i)
 53         }
 54         
 55         for _ in 1...100
 56         {
 57             let temp = Int(arc4random() % UInt32(array.count))+1
 58             let num = array[temp-1]
 59             result.append(num)
 60             
 61             array.remove(at: temp-1)
 62         }
 63         
 64         for i in 1...100
 65         {
 66             let num = result[i-1]
 67             let view = SortView(frame: CGRect(x: 10+i*3, y: 200, width: 2, height: num * 2))
 68             view.backgroundColor = .black
 69             view.tag = i
 70             self.view.addSubview(view)
 71         }
 72         
 73         let bt = UIButton(frame: CGRect(x: 10, y: 340, width: 300, height: 40))
 74         bt.backgroundColor = .orange
 75         bt.setTitle("Sort", for: .normal)
 76         bt.addTarget(self, action: #selector(reOrderView), for: .touchUpInside)
 77         self.view.addSubview(bt)
 78         
 79         //self.result.selectorSort()
 80         //print(self.result)
 81     }
 82     
 83     @objc func reOrderView()
 84     {
 85         date = Date()
 86         DispatchQueue.global().async
 87         {
 88             self.selectorSort()
 89             
 90             let endDate = Date()
 91             print(endDate.timeIntervalSince(self.date))
 92         }
 93     }
 94     
 95     func selectorSort()
 96     {
 97         //print("简单选择排序")
 98         var list = self.result
 99         for i in 0..<list.count
100         {
101             //print("第\(i+1)轮选择，选择下标的范围为\(i)----\(list.count)")
102             var j = i + 1
103             var minValue = list[i]
104             var minIndex = i
105             
106             //寻找无序部分中的最小值
107             while j < list.count
108             {
109                 if minValue > list[j]
110                 {
111                     minValue = list[j]
112                     minIndex = j
113                 }
114                 self.udpateView(j: j, height: list[j])
115                 j = j + 1
116             }
117             //print("在后半部分乱序数列中，最小值为：\(minValue), 下标为：\(minIndex)")
118             //与无序表中的第一个值交换，让其成为有序表中的最后一个值
119             if minIndex != i
120             {
121                 //print("\(minValue)与\(list[i])交换")
122                 let temp = list[i]
123                 list[i] = list[minIndex]
124                 list[minIndex] = temp
125                 
126                 self.udpateView(j: i, height: list[i])
127                 self.udpateView(j: minIndex, height: list[minIndex])
128             }
129             //print("本轮结果为：\(list)\n")
130         }
131     }
132     
133     func udpateView(j: Int, height: Int)
134     {
135         weak var weak_self = self
136         DispatchQueue.main.async
137             {
138                 let view = weak_self?.view.viewWithTag(j+1)
139                 view?.frame.size.height = CGFloat(height*2)
140                 
141         }
142         Thread.sleep(forTimeInterval: 0.01)
143     }
144     
145     override func didReceiveMemoryWarning() {
146         super.didReceiveMemoryWarning()
147         // Dispose of any resources that can be recreated.
148     }
149 }

选择排序、简单选择排序

相同的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 }