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

[Swift]八大排序算法(四):堆排序

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

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

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

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

注:博主将坚持每月上线一个新app!!!

排序分为内部排序和外部排序。

内部排序:是指待排序列完全存放在内存中所进行的排序过程,适合不太大的元素序列。

外部排序:指的是大文件的排序,即待排序的记录存储在外存储器上,待排序的文件无法一次装入内存,需要在内存和外部存储器之间进行多次数据交换,以达到排序整个文件的目的。

当N小于20的时候,插入排序具有最好的性能。

当N大于20时,快速排序具有最好的性能,尽管归并排序(merge sort)和堆排序(heap sort)复杂度都为nlog2(n)。


堆的操作

在堆的数据结构中,堆中的最大值总是位于根节点(在优先队列中使用堆的话堆中的最小值位于根节点)。堆中定义以下几种操作:

最大堆调整(Max Heapify):将堆的末端子节点作调整,使得子节点永远小于父节点

创建最大堆(Build Max Heap):将堆中的所有数据重新排序

堆排序(HeapSort):移除位在第一个数据的根节点,并做最大堆调整的递归运算

堆排序:

指利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构,并同时满足堆积的性质:即子结点的键值或索引总是小于(或者大于)它的父节点。

堆排序的基本思路:

a.将无需序列构建成一个堆,根据升序降序需求选择大顶堆或小顶堆;

b.将堆顶元素与末尾元素交换,将最大元素"沉"到数组末端;

c.重新调整结构,使其满足堆定义,然后继续交换堆顶元素与当前末尾元素,反复执行调整+交换步骤,直到整个序列有序。


ViewController.swift文件:运行时间(9.9504s)

  1 import UIKit
  2 
  3 //利用堆堆特性对数组进行排序
  4 class ViewController: UIViewController {
  5     //属性1:用来存储需要排序的数组
  6     var result : Array<Int> = Array<Int>()
  7     //属性2:统计排序花费的时间
  8     var date : Date!
  9     
 10     override func viewDidLoad() {
 11         super.viewDidLoad()
 12         // Do any additional setup after loading the view, typically from a nib.
 13         //初始化一个整形数组
 14         var array : Array<Int> = Array<Int>()
 15         //将1至100的100个整数,存入到该数组中
 16         for i in 1...100
 17         {
 18             array.append(i)
 19         }
 20         //添加一个循环语句,
 21         //用来生成一个由100个随机整数组成的数组
 22         for _ in 1...100
 23         {
 24             //首先根据数组的长度,
 25             //获得一个1至100的随机整数
 26             let temp = Int(arc4random() % UInt32(array.count))+1
 27             //根据随机值从数组中获得指定位置的整数,
 28             //并存储在用来排序的数组中
 29             let num = array[temp-1]
 30             result.append(num)
 31             //从原数组中移该随机数,以避免获得重复的数字
 32             array.remove(at: temp-1)
 33         }
 34         //添加一个循环语句,
 35         //用来生成100个自定义视图对象
 36         for i in 1...100
 37         {
 38             //初始化自定义视图对象
 39             let num = result[i-1]
 40             //并设置它的显示区域。
 41             //其中视图的高度,是当前数组中的数字的两倍大小
 42             let view = SortView(frame: CGRect(x: 10+i*3, y: 200, width: 2, height: num * 2))
 43             view.backgroundColor = .black
 44             //设置视图的标识值
 45             view.tag = i
 46             //并将视图添加到当前视图控制器的根视图
 47             self.view.addSubview(view)
 48         }
 49         //然后添加一个按钮
 50         //当用户点击该按钮时对数组进行排序
 51         let bt = UIButton(frame: CGRect(x: 10, y: 340, width: 300, height: 40))
 52         //设置背景按钮的背景颜色为橙色
 53         bt.backgroundColor = .orange
 54         //设置按钮在正常状态下的标题文字
 55         bt.setTitle("Sort", for: .normal)
 56         //给按钮对象绑定点击事件,
 57         bt.addTarget(self, action: #selector(reOrderView), for: .touchUpInside)
 58         //将按钮添加到当前视图控制器的根视图
 59         self.view.addSubview(bt)
 60     }
 61 
 62     //添加一个方法,用来响应按钮的点击事件
 63     @objc func reOrderView()
 64     {
 65         //获得当前的日期和时间
 66         date = Date()
 67         //在一个全局队列中,以异步的方式对数组进行排序
 68         //并实时调整和数组中的数值相对应的视图的位置
 69         DispatchQueue.global().async
 70             {
 71                 //调用实例方法,用来实现可视化堆数排序,
 72                 //该方法在下方的代码中实现
 73                 self.sort(items: self.result)
 74                 //获得排序后的系统时间,
 75                 //并在控制台输出两个时间的差值,
 76                 //从而获得排序所花费的大致时间。
 77                 //考虑线程休眠的影响,此数据仅做参考
 78                 let endDate = Date()
 79                 print(endDate.timeIntervalSince(self.date))
 80         }
 81     }
 82 
 83     //添加一个方法,用来实现具体的可视化的堆排序的功能
 84     func sort(items: Array<Int>)
 85     {
 86         var list = items
 87         //获得数组的最后一个元素的索引位置,
 88         //该值将用于创建一个堆。
 89         var endIndex = items.count - 1
 90         //接着创建一个堆,
 91         //首先获得数组元素的长度
 92         var i = items.count
 93         //通过一个循环语句,
 94         //对数组从后往前进行调整,使其符合堆堆特性
 95         //即索引位置在i的父元素的值,
 96         //大于位置在(i*2)和(i*2+1)左右子集元素的值
 97         while i > 0
 98         {
 99             heapAdjast(items: &list, startIndex: i - 1, endIndex:items.count )
100             i -= 1
101         }
102         //如此就将数组转换成了堆结构的样式:
103         //索引位置在i的父元素的值,
104         //大于位置在(i*2)和(i*2+1)左右子集元素的值。
105         //添加另一个循环语句
106         while endIndex >= 0
107         {
108             //在这个循环语句中,
109             //重复交换第一个元素和指定索引位置的元素
110             let temp = list[0]
111             list[0] = list[endIndex]
112             list[endIndex] = temp
113             //同时更新两个元素对应的视图对象的高度
114             self.udpateView(j: 0, height: list[0])
115             self.udpateView(j: endIndex, height: list[endIndex])
116             //将索引递减,以满足循环停止的条件
117             endIndex -= 1
118             //同时对从数组的头部至递减后的索引位置之间的元素调整为堆样式
119             heapAdjast(items: &list, startIndex: 0,endIndex: endIndex + 1)
120         }
121     }
122 
123     //在上一个方法中,已经编写了用于创建堆堆代码。
124     //这里添加一个方法,用来将上面的创建堆的代码抽出
125     func heapCreate(items: inout Array<Int>)
126     {
127         //获得数组元素的长度
128         var i = items.count
129         //添加一个循环语句
130         while i > 0
131         {
132             //通过循环语句,对数组从后往前调整,
133             //使其符合堆堆特性。
134             heapAdjast(items: &items, startIndex: i - 1, endIndex:items.count )
135             i -= 1
136         }
137     }
138 
139     //添加一个方法,用来实现将数组调整为堆样式
140     func heapAdjast(items: inout Array<Int>, startIndex: Int, endIndex: Int)
141     {
142         //定义一个常量和两个变量,用于辅助堆样式的调整。
143         let temp = items[startIndex]
144         //变量1:表示父节点
145         var fatherIndex = startIndex + 1
146         //变量2:临时变量,表示父节点的左节点。
147         var maxChildIndex = 2 * fatherIndex
148         //添加一个循环语句,用来执行堆样式调整的操作。
149         while maxChildIndex <= endIndex
150         {
151             //判断如果左侧的子节点的值,小于右侧子节点的值,
152             //则更改最大子节点索引的值。
153             if maxChildIndex < endIndex && items[maxChildIndex-1] < items[maxChildIndex]
154             {
155                 maxChildIndex = maxChildIndex + 1
156             }
157             //判断最大子节点元素的值是否小于首节点的值,
158             //如果大于则表示完成堆样式的建立,并退出循环。
159             if temp < items[maxChildIndex-1]
160             {
161                 //否则将最大子节点元素的值,赋予父节点,
162                 //并同步更新父节点对应的视图对象的高度。
163                 items[fatherIndex-1] = items[maxChildIndex-1]
164                 self.udpateView(j: fatherIndex-1, height: items[fatherIndex-1])
165             }
166             else
167             {
168                 //如果大于则表示完成堆样式的建立,并退出循环。
169                 break
170             }
171             //更改两个变量的值,
172             //从而以最大子节点为父节点,
173             //继续循环语句的执行。
174             fatherIndex = maxChildIndex
175             maxChildIndex = 2 * fatherIndex
176         }
177         //完成循环之后,所有比temp大的子节点,
178         //都被赋予它们的父节点。
179         //此时的fatherIndex是最后一个被赋予其父节点的最大子节点。
180         //将temp值赋予该节点,并更新该节点对应的视图的高度。
181         items[fatherIndex-1] = temp
182         self.udpateView(j: fatherIndex-1, height: items[fatherIndex-1])
183     }
184 
185     //添加一个方法,用来更新视图的高度
186     func udpateView(j: Int, height: Int)
187     {
188         //由于需要对界面元素进行调整,
189         //所以需要切换至主线程
190         weak var weak_self = self
191         DispatchQueue.main.async
192         {
193                 //根据标识值,
194                 //获得和需要交换顺序的数组元素相对应的视图对象
195                 //并设置它的新的高度
196                 let view = weak_self?.view.viewWithTag(j+1)
197                 view?.frame.size.height = CGFloat(height*2)
198         }
199         //使线程休眠0.01秒,
200         //以方便观察排序的视觉效果
201         Thread.sleep(forTimeInterval: 0.01)
202     }
203     
204     override func didReceiveMemoryWarning() {
205         super.didReceiveMemoryWarning()
206         // Dispose of any resources that can be recreated.
207     }
208 }

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人参与评论

请发表评论

全部评论

专题导读
上一篇:
swift笔记(二)——运算符发布时间:2022-07-13
下一篇:
【Swift】iOS开发笔记(一)发布时间: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