客服电话
APP下载
迪恩网络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 }
|
请发表评论