[Swift]八大排序算法（六）：希尔排序

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› 移动开发›Swift 教程

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

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

热烈欢迎，请直接点击！！！

进入博主App Store主页，下载使用各个作品！！！

注：博主将坚持每月上线一个新app！！！

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

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

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

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

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

希尔排序

希尔排序(Shell's Sort)是插入排序的一种又称“缩小增量排序”（Diminishing Increment Sort），是直接插入排序算法的一种更高效的改进版本。

希尔排序是非稳定排序算法。该方法因D.L.Shell于1959年提出而得名。

希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。

基本思想：先取一个小于n的整数d1作为第一个增量，把文件的全部记录分组。所有距离为d1的倍数的记录放在同一个组中。先在各组内进行直接插入排序；然后，取第二个增量d2<d1重复上述的分组和排序，直至所取的增量 =1( < …<d2<d1)即所有记录放在同一组中进行直接插入排序为止。

希尔排序是基于插入排序的以下两点性质而提出改进方法的：

(1)、插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率。

(2)、但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位。

ViewController.swift文件：运行时间（4.4775s）

  1 import UIKit
  2 
  3 class ViewController: UIViewController {
  4     //属性1:用来存储需要排序的数组
  5     var result : Array<Int> = Array<Int>()
  6     //属性2:统计排序花费的时间
  7     var date : Date!
  8     
  9     override func viewDidLoad() {
 10         super.viewDidLoad()
 11         // Do any additional setup after loading the view, typically from a nib.
 12         //初始化一个整形数组
 13         var array : Array<Int> = Array<Int>()
 14         //将1至100的100个整数，存入到该数组中
 15         for i in 1...100
 16         {
 17             array.append(i)
 18         }
 19         //添加一个循环语句，
 20         //用来生成一个由100个随机整数组成的数组
 21         for _ in 1...100
 22         {
 23             //首先根据数组的长度，
 24             //获得一个1至100的随机整数
 25             let temp = Int(arc4random() % UInt32(array.count))+1
 26             //根据随机值从数组中获得指定位置的整数，
 27             //并存储在用来排序的数组中
 28             let num = array[temp-1]
 29             result.append(num)
 30             //从原数组中移该随机数，以避免获得重复的数字
 31             array.remove(at: temp-1)
 32         }
 33         //添加一个循环语句，
 34         //用来生成100个自定义视图对象
 35         for i in 1...100
 36         {
 37             //初始化自定义视图对象
 38             let num = result[i-1]
 39             //并设置它的显示区域。
 40             //其中视图的高度，是当前数组中的数字的两倍大小
 41             let view = SortView(frame: CGRect(x: 10+i*3, y: 200, width: 2, height: num * 2))
 42             view.backgroundColor = .black
 43             //设置视图的标识值
 44             view.tag = i
 45             //并将视图添加到当前视图控制器的根视图
 46             self.view.addSubview(view)
 47         }
 48         //然后添加一个按钮
 49         //当用户点击该按钮时对数组进行排序
 50         let bt = UIButton(frame: CGRect(x: 10, y: 340, width: 300, height: 40))
 51         //设置背景按钮的背景颜色为橙色
 52         bt.backgroundColor = .orange
 53         //设置按钮在正常状态下的标题文字
 54         bt.setTitle("Sort", for: .normal)
 55         //给按钮对象绑定点击事件，
 56         bt.addTarget(self, action: #selector(reOrderView), for: .touchUpInside)
 57         //将按钮添加到当前视图控制器的根视图
 58         self.view.addSubview(bt)
 59     }
 60     
 61     //添加一个方法，用来响应按钮的点击事件
 62     @objc func reOrderView()
 63     {
 64         //获得当前的日期和时间
 65         date = Date()
 66         //在一个全局队列中，以异步的方式对数组进行排序
 67         //并实时调整和数组中的数值相对应的视图的位置
 68         DispatchQueue.global().async
 69             {
 70                 //调用实例方法，用来进行可视化的希尔排序。
 71                 //该方法在下方的代码中实现
 72                 self.sort(items: self.result)
 73                 //获得排序后的系统时间，
 74                 //并在控制台输出两个时间的差值，
 75                 //从而获得排序所花费的大致时间。
 76                 //考虑线程休眠的影响，此数据仅做参考
 77                 let endDate = Date()
 78                 print(endDate.timeIntervalSince(self.date))
 79         }
 80     }
 81 
 82     //添加一个方法，用来实现具体的可视化的希尔排序的功能
 83     func sort(items: Array<Int>)
 84     {
 85         //首先设置希尔排序的增量，
 86         //将它的值设置为数组长度的一半。
 87         //希尔排序对增量序列的选择没有严格的规定。
 88         var list = items
 89         var step: Int = list.count / 2
 90         //通过增量创建一个循环语句
 91         while step >= 1
 92         {
 93             //下方代码和插入排序的代码相同
 94             //首先将数组中的第一个元素，看成是已经完成排序的数组。
 95             for i in 0..<list.count
 96             {
 97                 //然后从第二个元素开始，通过循环语句，
 98                 //将未排序的元素，
 99                 //由后向前完成排序的数组进行比较和插入
100                 var j = i + step
101                 while j >= step && j < list.count
102                 {
103                     //将待排序的元素，
104                     //由后向前，和每个已经完成排序的元素进行比较，
105                     //当该元素小于已经完成排序的元素时，
106                     //将该元素插入到找到的元素的前方，
107                     //否则退出循环
108                     if list[j] < list[j - step]
109                     {
110                         //由于需要对界面元素进行调整，
111                         //所以需要切换至主线程
112                         weak var weak_self = self
113                         DispatchQueue.main.async
114                         {
115                             //根据标识值，
116                             //获得和需要交换顺序的数组元素相对应的视图对象
117                             let view1 = weak_self?.view.viewWithTag(j+1)
118                             let view2 = weak_self?.view.viewWithTag(j-step+1)
119                             //获得两个视图对象的水平坐标X的值
120                             let posX1 = view1?.frame.origin.x
121                             let posX2 = view2?.frame.origin.x
122                             //然后交换两个视图对象的水平坐标的值
123                             //从而实现两个视图对象的位置的交
124                             view1?.frame.origin.x = posX2!
125                             view2?.frame.origin.x = posX1!
126                                //记得更换两个视图对象的标识值
127                             view1?.tag = j-step+1
128                             view2?.tag = j+1
129                             //交换数组中的两个元素的位置
130                             let temp = list[j]
131                             list[j] = list[j-step]
132                             list[j-step] = temp
133                             //将第二个循环语句的索引值减去增量，实现从后往前的遍历和比较
134                             j = j - step
135                         }
136                         //使线程休眠0.01秒，
137                         //以方便观察排序的视觉效果
138                         Thread.sleep(forTimeInterval: 0.01)
139                     }
140                     else
141                     {
142                         //否则退出循环
143                         break
144                     }
145                 }
146             }
147             //使增量逐渐减半，直至达到结束循环的条件
148             step = step / 2
149         }
150     }
151     
152     override func didReceiveMemoryWarning() {
153         super.didReceiveMemoryWarning()
154         // Dispose of any resources that can be recreated.
155     }
156 }

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 }