• 设为首页
  • 点击收藏
  • 手机版
    手机扫一扫访问
    迪恩网络手机版
  • 关注官方公众号
    微信扫一扫关注
    公众号

[Swift]八大排序算法(一):冒泡排序

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

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

热烈欢迎,请直接点击!!!

进入博主App Store主页,下载使用各个作品!!!

注:博主将坚持每月上线一个新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 }

 


鲜花

握手

雷人

路过

鸡蛋
该文章已有0人参与评论

请发表评论

全部评论

专题导读
上一篇:
iOS Swift Charts 的使用(四):k线的实现发布时间:2022-07-13
下一篇:
[Swift]LeetCode404.左叶子之和|SumofLeftLeaves发布时间:2022-07-13
热门推荐
热门话题
阅读排行榜

扫描微信二维码

查看手机版网站

随时了解更新最新资讯

139-2527-9053

在线客服(服务时间 9:00~18:00)

在线QQ客服
地址:深圳市南山区西丽大学城创智工业园
电邮:jeky_zhao#qq.com
移动电话:139-2527-9053

Powered by 互联科技 X3.4© 2001-2213 极客世界.|Sitemap