|
1、算法原理： (1)、比较相邻的元素。如果第一个比第二个大，就交换他们两个。 (2)、对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。 (3)、针对所有的元素重复以上的步骤，除了最后一个。 (4)、持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较 2、算法分析：时间复杂度 (1)、若文件的初始状态是正序的，一趟扫描即可完成排序。 所需的关键字比较次数 所以，冒泡排序最好的时间复杂度为 (2)、若初始文件是反序的，需要进行 趟排序。每趟排序要进行
冒泡排序的最坏时间复杂度为 综上，因此冒泡排序总的平均时间复杂度为 3、算法稳定性 冒泡排序就是把小的元素往前调或者把大的元素往后调。比较是相邻的两个元素比较，交换也发生在这两个元素之间。所以，如果两个元素相等，是不会再交换的；如果两个相等的元素没有相邻，那么即使通过前面的两两交换把两个相邻起来，这时候也不会交换，所以相同元素的前后顺序并没有改变，所以冒泡排序是一种稳定排序算法。 ViewController.swift文件 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 required init?(coder aDecoder: NSCoder) {
13 fatalError("init(coder:) has not been implemented")
14 }
15 //重写父类的重新布局子视图方法
16 //将在此视图中对视图进行外观设置
17 override func layoutSubviews()
18 {
19 //首先获得自定义视图在界面中对Y轴坐标
20 let y: CGFloat = 300 - frame.height
21 //然后重新设置自定义视图的位置
22 self.frame = frame
23 self.frame.origin.y = y
24 //根据自定义视图的高度，计算一个权重数值
25 //用于生成不同的背景颜色
26 let weight = frame.height / 200
27 //生成不同y色相的颜色对象，从而给自定义视图设置不同的背景颜色
28 //然后打开ViewController.swift文件
29 let color = UIColor(hue: weight, saturation: 1, brightness: 1, alpha: 1)
30 self.backgroundColor = color
31 }
32 /*
33 // Only override draw() if you perform custom drawing.
34 // An empty implementation adversely affects performance during animation.
35 override func draw(_ rect: CGRect) {
36 // Drawing code
37 }
38 */
39 }
来源：http://www./content-1-73401.html |
|
|
和记录移动次数
均达到最小值：
，
。
(1≤i≤n-1)次关键字的比较，且每次比较都必须移动记录三次来达到交换记录位置。在这种情况下，比较和移动次数均达到最大值：
。
。
