客服电话
APP下载
迪恩网络APP
随时随地掌握行业动态
官方微信
扫描二维码
关注迪恩网络微信公众号
|
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★ 排序分为内部排序和外部排序。 内部排序：是指待排序列完全存放在内存中所进行的排序过程，适合不太大的元素序列。 外部排序：指的是大文件的排序，即待排序的记录存储在外存储器上，待排序的文件无法一次装入内存，需要在内存和外部存储器之间进行多次数据交换，以达到排序整个文件的目的。 当N小于20的时候，插入排序具有最好的性能。 当N大于20时，快速排序具有最好的性能，尽管归并排序(merge sort)和堆排序(heap sort)复杂度都为nlog2(n)。 冒泡排序算法 1、算法原理： (1)、比较相邻的元素。如果第一个比第二个大，就交换他们两个。 (2)、对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。 (3)、针对所有的元素重复以上的步骤，除了最后一个。 (4)、持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较 2、算法分析：时间复杂度 (1)、若文件的初始状态是正序的，一趟扫描即可完成排序。 所需的关键字比较次数和记录移动次数均达到最小值：， 所以，冒泡排序最好的时间复杂度为 。 (2)、若初始文件是反序的，需要进行 趟排序。每趟排序要进行(1≤i≤n-1)次关键字的比较，且每次比较都必须移动记录三次来达到交换记录位置。在这种情况下，比较和移动次数均达到最大值：
冒泡排序的最坏时间复杂度为 。 综上，因此冒泡排序总的平均时间复杂度为 。 3、算法稳定性 冒泡排序就是把小的元素往前调或者把大的元素往后调。比较是相邻的两个元素比较，交换也发生在这两个元素之间。所以，如果两个元素相等，是不会再交换的；如果两个相等的元素没有相邻，那么即使通过前面的两两交换把两个相邻起来，这时候也不会交换，所以相同元素的前后顺序并没有改变，所以冒泡排序是一种稳定排序算法。 ViewController.swift文件：运行时间（29.0735s） 1 import UIKit 2 //对数组类型进行扩展 3 extension Array 4 { 5 //扩展方法：用来交换数组中的两个位置的元素 6 fileprivate mutating func swap(i:Int,j:Int) 7 { 8 //通过一个临时变量，交换数组中的两个不同位置的元素 9 let temp = self[i] 10 self[i] = self[j] 11 self[j] = temp 12 } 13 } 14 15 //对具有可比较性的数组进行扩展 16 //以实现冒泡排序功能 17 extension Array where Element:Comparable 18 { 19 //添加一个方法，用来实现具体的排序功能 20 //使用mutating关键字修饰方法， 21 //是为了能在方法内部修改自身变量的值 22 mutating func bubbleSort() 23 { 24 //对数组自身进行从头至倒数第二的遍历 25 for i in 0..<self.count-1 26 { 27 //从数组的尾部开始 28 //向上一个循环语句遍历到的元素进行遍历 29 for j in (i+1...self.count-1).reversed() 30 { 31 //判断两个相邻元素的大小 32 if self[j] < self[j-1] 33 { 34 //以交换值的方式，调整两个元素的顺序 35 swap(i: j, j: j-1) 36 } 37 } 38 } 39 } 40 } 41 42 class ViewController: UIViewController { 43 //上面是冒泡排序算法的编写。 44 //现在通过可视化的方式，使用冒泡排序算法 45 46 //属性1:用来存储需要排序的数组 47 var result : Array<Int> = Array<Int>() 48 //属性2:统计排序花费的时间 49 var date : Date! 50 51 override func viewDidLoad() { 52 super.viewDidLoad() 53 // Do any additional setup after loading the view, typically from a nib. 54 //初始化一个整形数组 55 var array : Array<Int> = Array<Int>() 56 //将1至100的100个整数，存入到该数组中 57 for i in 1...100 58 { 59 array.append(i) 60 } 61 //添加一个循环语句， 62 //用来生成一个由100个随机整数组成的数组 63 for _ in 1...100 64 { 65 //首先根据数组的长度， 66 //获得一个1至100的随机整数 67 let temp = Int(arc4random() % UInt32(array.count))+1 68 //根据随机值从数组中获得指定位置的整数， 69 //并存储在用来排序的数组中 70 let num = array[temp-1] 71 result.append(num) 72 //从原数组中移该随机数，以避免获得重复的数字 73 array.remove(at: temp-1) 74 } 75 //添加一个循环语句， 76 //用来生成100个自定义视图对象 77 for i in 1...100 78 { 79 //初始化自定义视图对象 80 let num = result[i-1] 81 //并设置它的显示区域。 82 //其中视图的高度，是当前数组中的数字的两倍大小 83 let view = SortView(frame: CGRect(x:10+i*3,y:200,width:2,height:num*2)) 84 view.backgroundColor = .black 85 //设置视图的标识值 86 view.tag = i 87 //并将视图添加到当前视图控制器的根视图 88 self.view.addSubview(view) 89 } 90 //然后添加一个按钮 91 //当用户点击该按钮时对数组进行排序 92 let bt = UIButton(frame: CGRect(x: 10, y: 340, width: 300, height: 40)) 93 //设置背景按钮的背景颜色为橙色 94 bt.backgroundColor = .orange 95 //设置按钮在正常状态下的标题文字 96 bt.setTitle("Sort", for: .normal) 97 //给按钮对象绑定点击事件， 98 bt.addTarget(self, action: #selector(reOrderView), for: .touchUpInside) 99 //将按钮添加到当前视图控制器的根视图 100 self.view.addSubview(bt) 101 } 102 103 //添加一个方法，用来响应按钮的点击事件 104 @objc func reOrderView() 105 { 106 //获得当前的日期和时间 107 date = Date() 108 //在一个全局队列中，以异步的方式对数组进行排序 109 //并实时调整和数组中的数值相对应的视图的位置 110 DispatchQueue.global().async 111 { 112 //下面的代码，是对上方的冒泡排序代码的拷贝： 113 //首先添加一个循环语句 114 //对数组自身进行从头至尾的遍历 115 for i in 0..<self.result.count-1 116 { 117 //从数组尾部开始 118 //向上一个循环语句遍历到的元素进行遍历 119 for j in (i+1...self.result.count-1).reversed() 120 { 121 //判断两个相邻元素的大小， 122 //并以交换值的方式，调整两个元素的顺序 123 if self.result[j] < self.result[j-1] 124 { 125 //由于需要对界面元素进行调整， 126 //所以需要切换至主线程 127 weak var weak_self = self 128 DispatchQueue.main.async 129 { 130 //根据标识值， 131 //获得和需要交换顺序的数组元素相对应的视图对象 132 let view1 = weak_self?.view.viewWithTag(j+1) 133 let view2 = weak_self?.view.viewWithTag(j) 134 //获得两个视图对象的水平坐标X的值 135 let posX1 = view1?.frame.origin.x 136 let posX2 = view2?.frame.origin.x 137 //然后交换两个视图对象的水平坐标的值 138 //从而实现两个视图对象的位置的交换 139 view1?.frame.origin.x = posX2! 140 view2?.frame.origin.x = posX1! 141 //记得更换两个视图对象的标识值 142 view1?.tag = j 143 view2?.tag = j+1 144 //交换数组中两个元素的位置， 145 //从而实现了数据和界面的同步更新 146 self.result.swap(i: j, j: j-1) 147 } 148 //使线程休眠0.01秒， 149 //以方便观察排序的视觉效果 150 Thread.sleep(forTimeInterval: 0.01) 151 } 152 } 153 } 154 //获得排序后的系统时间， 155 //并在控制台输出两个时间的差值， 156 //从而获得排序所花费的大致时间。 157 //考虑线程休眠的影响，此数据仅做参考 158 let endDate = Date() 159 print(endDate.timeIntervalSince(self.date)) 160 } 161 } 162 163 override func didReceiveMemoryWarning() { 164 super.didReceiveMemoryWarning() 165 // Dispose of any resources that can be recreated. 166 } 167 } 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 }
|
请发表评论