客服电话
APP下载
迪恩网络APP
随时随地掌握行业动态
官方微信
扫描二维码
关注迪恩网络微信公众号
|
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★ 排序分为内部排序和外部排序。 内部排序：是指待排序列完全存放在内存中所进行的排序过程，适合不太大的元素序列。 外部排序：指的是大文件的排序，即待排序的记录存储在外存储器上，待排序的文件无法一次装入内存，需要在内存和外部存储器之间进行多次数据交换，以达到排序整个文件的目的。 当N小于20的时候，插入排序具有最好的性能。 当N大于20时，快速排序具有最好的性能，尽管归并排序(merge sort)和堆排序(heap sort)复杂度都为nlog2(n)。 快速排序算法：快速排序是C.R.A.Hoare于1962年提出的一种划分交换排序。它采用了一种分治的策略，通常称其为分治法(Divide-and-ConquerMethod)。 （1）分治法的基本思想：将原问题分解为若干个规模更小但结构与原问题相似的子问题。递归地解这些子问题，然后将这些子问题的解组合为原问题的解。 （2）快速排序的基本思想：设当前待排序的无序区为R[low..high]，利用分治法可将快速排序的基本思想描述为：
①分解： 划分的结果可以简单地表示为(注意pivot=R[pivotpos]) ：R[low..pivotpos-1].keys≤R[pivotpos].key≤R[pivotpos+1..high].keys 其中low≤pivotpos≤high。
②求解： ③组合： 快速排序具有最好的平均性能（average behavior），但最坏性能（worst case behavior）和插入排序相同，也是O(n^2)。比如一个序列5,4,3,2,1，要排为1,2,3,4,5。按照快速排序方法，每次只会有一个数据进入正确顺序。 ViewController.swift文件：运行时间（4.6361s） 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 //添加i一个扩展方法，用来实现具体的排序功能 21 func quickSort(list: inout Array<Int>, low: Int, high: Int) 22 { 23 //首先将需要排序的数组首次分成两个部分， 24 if low < high 25 { 26 //并返回将数组进行分隔成两个部分的中间值， 27 //位于中间值左侧的数据都比它小， 28 //右侧的数据都比它大。 29 //此方法在下方的代码中实现 30 let mid = partition(list: &list, low: low, high: high) 31 //接着通过递归的方式， 32 //对左右两侧的数组进行统一的排序， 33 //最终将获得一个有序的数组 34 quickSort(list: &list, low: low, high: mid - 1) 35 quickSort(list: &list, low: mid + 1, high: high) 36 } 37 } 38 39 //添加一个方法，用来将数组一分为二， 40 //并返回一个中间值， 41 //位于中间值左侧的数据都比它小， 42 //右侧的数据都比它大 43 private func partition(list: inout Array<Int>, low: Int, high: Int) -> Int { 44 //将数组中的最左侧的值作为临时常量，对数组进行分隔 45 var low = low 46 var high = high 47 let temp = list[low] 48 //添加一个指定区间的循环语句 49 while low < high 50 { 51 //继续添加一个循环语句，从数组的尾部向头部进行遍历， 52 //用来获得比临时值小的元素所在的位置 53 while low < high && list[high] >= temp 54 { 55 high -= 1 56 } 57 //然后将该元素的值，替代原来的最小值 58 list[low] = list[high] 59 //继续添加一个循环语句，从数组的头部， 60 //向上一个循环语句找到的， 61 //比临时值小的元素所在的索引位置 62 //用来获得比临时值小的元素所在的位置 63 while low < high && list[low] <= temp 64 { 65 low += 1 66 } 67 //然后将该元素的值，替代原来的最大值 68 list[high] = list[low] 69 } 70 //这样就完成了对数组分成两部分的任务， 71 //然后将用来分割值的索引， 72 //替换low(此时low和high是相等的)索引所在的位置的元素即可。 73 list[low] = temp 74 //最后返回low作为分割值的索引 75 return low 76 } 77 } 78 79 class ViewController: UIViewController { 80 //上面是选择排序算法的编写。 81 //现在通过可视化的方式，使用冒泡排序算法 82 83 //属性1:用来存储需要排序的数组 84 var result : Array<Int> = Array<Int>() 85 //属性2:统计排序花费的时间 86 var date : Date! 87 88 override func viewDidLoad() { 89 super.viewDidLoad() 90 // Do any additional setup after loading the view, typically from a nib. 91 //初始化一个整形数组 92 var array : Array<Int> = Array<Int>() 93 //将1至100的100个整数，存入到该数组中 94 for i in 1...100 95 { 96 array.append(i) 97 } 98 //添加一个循环语句， 99 //用来生成一个由100个随机整数组成的数组 100 for _ in 1...100 101 { 102 //首先根据数组的长度， 103 //获得一个1至100的随机整数 104 let temp = Int(arc4random() % UInt32(array.count))+1 105 //根据随机值从数组中获得指定位置的整数， 106 //并存储在用来排序的数组中 107 let num = array[temp-1] 108 result.append(num) 109 //从原数组中移该随机数，以避免获得重复的数字 110 array.remove(at: temp-1) 111 } 112 //添加一个循环语句， 113 //用来生成100个自定义视图对象 114 for i in 1...100 115 { 116 //初始化自定义视图对象 117 let num = result[i-1] 118 //并设置它的显示区域。 119 //其中视图的高度，是当前数组中的数字的两倍大小 120 let view = SortView(frame: CGRect(x: 10+i*3, y: 200, width: 2, height: num * 2)) 121 view.backgroundColor = .black 122 //设置视图的标识值 123 view.tag = i 124 //并将视图添加到当前视图控制器的根视图 125 self.view.addSubview(view) 126 } 127 //然后添加一个按钮 128 //当用户点击该按钮时对数组进行排序 129 let bt = UIButton(frame: CGRect(x: 10, y: 340, width: 300, height: 40)) 130 //设置背景按钮的背景颜色为橙色 131 bt.backgroundColor = .orange 132 //设置按钮在正常状态下的标题文字 133 bt.setTitle("Sort", for: .normal) 134 //给按钮对象绑定点击事件， 135 bt.addTarget(self, action: #selector(reOrderView), for: .touchUpInside) 136 //将按钮添加到当前视图控制器的根视图 137 self.view.addSubview(bt) 138 } 139 140 //添加一个方法，用来响应按钮的点击事件 141 @objc func reOrderView() 142 { 143 //获得当前的日期和时间 144 date = Date() 145 //在一个全局队列中，以异步的方式对数组进行排序 146 //并实时调整和数组中的数值相对应的视图的位置 147 DispatchQueue.global().async 148 { 149 //调用实例方法，用来进行可视化的选择排序。 150 //该方法在下方的代码中实现 151 self.quickSort(list: &self.result, low: 0, high: self.result.count-1) 152 //获得排序后的系统时间， 153 //并在控制台输出两个时间的差值， 154 //从而获得排序所花费的大致时间。 155 //考虑线程休眠的影响，此数据仅做参考 156 let endDate = Date() 157 print(endDate.timeIntervalSince(self.date)) 158 } 159 } 160 161 //添加一个方法，用来实现具体可视化的快速排序的功能 162 func quickSort(list: inout Array<Int>, low: Int, high: Int) 163 { 164 //首先将需要排序的数组首次分成两个部分， 165 if low < high 166 { 167 //并返回将数组进行分隔成两个部分的中间值， 168 //位于中间值左侧的数据都比它小， 169 //右侧的数据都比它大。 170 //此方法在下方的代码中实现 171 let mid = partition(list: &list, low: low, high: high) 172 //接着通过递归的方式， 173 //对左右两侧的数组进行统一的排序， 174 //最终将获得一个有序的数组 175 quickSort(list: &list, low: low, high: mid - 1) 176 quickSort(list: &list, low: mid + 1, high: high) 177 } 178 } 179 180 //并返回一个中间值， 181 //位于中间值左侧的数据都比它小， 182 //右侧的数据都比它大 183 private func partition(list: inout Array<Int>, low: Int, high: Int) -> Int { 184 //将数组中的最左侧的值作为临时常量，对数组进行分隔 185 var low = low 186 var high = high 187 let temp = list[low] 188 //添加一个指定区间的循环语句 189 while low < high 190 { 191 //继续添加一个循环语句，从数组的尾部向头部进行遍历， 192 //用来获得比临时值小的元素所在的位置 193 while low < high && list[high] >= temp 194 { 195 high -= 1 196 } 197 //然后将该元素的值，替代原来的最小值 198 list[low] = list[high] 199 //同时调用另外一个实例方法， 200 //同步更新界面中的对应的视图对象的位置 201 udpateView(j: low, height: list[high]) 202 203 //继续添加一个循环语句，从数组的头部， 204 //向上一个循环语句找到的， 205 //比临时值小的元素所在的索引位置 206 //用来获得比临时值小的元素所在的位置 207 while low < high && list[low] <= temp 208 { 209 low += 1 210 } 211 //然后将该元素的值，替代原来的最大值 212 list[high] = list[low] 213 //同时调用另外一个实例方法， 214 //同步更新界面中的对应的视图对象的高度 215 udpateView(j: high, height: list[low]) 216 } 217 //这样就完成了对数组分成两部分的任务， 218 //然后将用来分割值的索引， 219 //替换low(此时low和high是相等的)索引所在的位置的元素即可。 220 list[low] = temp 221 //同时调用另外一个实例方法， 222 //同步更新界面中的对应的视图对象的高度 223 udpateView(j: low, height: temp) 224 //最后返回low作为分割值的索引 225 return low 226 } 227 228 //添加一个方法，用来同步更新界面中视图的高度 229 func udpateView(j: Int, height: Int) 230 { 231 //由于需要对界面元素进行调整， 232 //所以需要切换至主线程 233 weak var weak_self = self 234 DispatchQueue.main.async 235 { 236 //根据标识值，获得需要更换高度的视图对象 237 //然后修改其值为指定的高度 238 let view = weak_self?.view.viewWithTag(j+1) 239 view?.frame.size.height = CGFloat(height*2) 240 } 241 //使线程休眠0.01秒， 242 //以方便观察排序的视觉效果 243 Thread.sleep(forTimeInterval: 0.01) 244 } 245 246 override func didReceiveMemoryWarning() { 247 super.didReceiveMemoryWarning() 248 // Dispose of any resources that can be recreated. 249 } 250 } 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 }
|
请发表评论