VisualAlgorithm-视觉化排序算法

  1. 1. VisualAlgorithm
    1. 1.1. 插入排序
    2. 1.2. 选择排序
    3. 1.3. 归并排序 自上而下
    4. 1.4. 归并排序 从下至上
  2. 2. UI实现方法
    1. 2.1. 动画显示
  3. 3. Links

VisualAlgorithm

Use Swift 3.0 build pass in Xcode8.1

  1. 插入排序
  2. 选择排序
  3. 归并排序 从上至下
  4. 归并排序 从下至上

插入排序

目标:将一个数据从高(低)到低(高)排序,下例有低到高。

  • 将数组放入一个堆中,这个堆是乱序的

  • 将第一个元素作为最小元素放入已排序堆中

  • 将第二个元素与之比较,插在前面或后面(😈),这样就有一个由两个元素组成的有序数组了,下一个元素和前两个依次比较,插入到恰当的位置

  • 重复上述操作,至遍历完数组

    img

1
2
3
4
5
6
7
8
9
10
11
12
13
14
func insertionSort(_ nowTime: TimeInterval, _ isOrderedBefore: @escaping (Int, Int) -> Bool) {
DispatchQueue.global(qos: .userInitiated).async {
var a = self.unsortedArray
for x in 1..<a.count{
var y = x
while y > 0 && isOrderedBefore(a[y], a[y - 1]) {
swap(&a[y-1],&a[y])
// MARK: - 动画操作
self.reloadView(nowTime: nowTime, array: a)
y -= 1
}
}
}
}

选择排序

  • 首先选择第一个元素为最小(最大)元素,记录下他的位置,遍历剩余数组如果有元素小于(大于)最小(最大)元素,更新最小(最大)元素位置信息,至遍历完毕,比较第一次设置的最小(最大)位置是否和最终的位置一致,否则为后者,并交换两个元素的位置。

  • 重复上述操作,这次将第二个元素设置为待交换元素。

    img

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
func SelectionSort(nowTime: TimeInterval) {
DispatchQueue.global(qos: .userInitiated).async {
var a = self.unsortedArray
for x in 0..<a.count - 1 {
var lowest = x
for y in x + 1 ..< a.count {
if a[y] < a[lowest] {
lowest = y
}
}
if x != lowest {
swap(&a[x], &a[lowest])
// MARK: - 动画操作
self.reloadView(nowTime: nowTime, array: a)
}
}
}
}

归并排序 自上而下

归并算法的思想:将大问题分解成小问题在合并。(下例从小到大)

  • 将一个数组一分为2,接着两个数组继续一分为二,keep doing,直至每个数组只含有一个元素

  • 开始合并它们,两两比较排序,原来1个1个的有序数组成了,2个2个的有序数组,继续合并直至全部排序

  • 函数mergeSort使用递归的方式分解合并一个数组

  • 合并函数merge的基本逻辑是:

    • 首先我们比较的对象是两个数组,分别加上两个游标,放置在数组的0位置,同步比较游标上的元素,较小一方放入新有序数组中,并且较小一方数组游标+1,相等则游标同时+1。继续比较游标当前元素大小,如果一个数组游标到达最后一个元素了,而另一个数组还有元素,由于每个数组的内部都是已经排序过的,所以只要把剩余的元素加入到一排序数组就可以了

      img

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
func mergeSort(_ array: [Int], _ nowTime: TimeInterval) -> [Int] {
guard array.count > 1 else {
return array
}
let middleIndex = array.count / 2
let leftArray = mergeSort(Array(array[0..<middleIndex]), nowTime)
let rightArray = mergeSort(Array(array[middleIndex..<array.count]), nowTime)
return merge(leftPile: leftArray, rightPile: rightArray, nowTime)
}
func merge(leftPile: [Int], rightPile: [Int], _ nowTime: TimeInterval) -> [Int] {
var leftIndex = 0
var rightIndex = 0
var orderedPile = [Int]()
while leftIndex < leftPile.count && rightIndex < rightPile.count {
if leftPile[leftIndex] < rightPile[rightIndex] {
orderedPile.append(leftPile[leftIndex])
self.reloadView(nowTime: nowTime, array: orderedPile)
leftIndex += 1
} else if leftPile[leftIndex] > rightPile[rightIndex] {
orderedPile.append(rightPile[rightIndex])
self.reloadView(nowTime: nowTime, array: orderedPile)
rightIndex += 1
} else {
orderedPile.append(leftPile[leftIndex])
leftIndex += 1
orderedPile.append(rightPile[rightIndex])
rightIndex += 1
self.reloadView(nowTime: nowTime, array: orderedPile)
}
}
while leftIndex < leftPile.count {
orderedPile.append(leftPile[leftIndex])
leftIndex += 1
self.reloadView(nowTime: nowTime, array: orderedPile)
}
while rightIndex < rightPile.count {
orderedPile.append(rightPile[rightIndex])
rightIndex += 1
self.reloadView(nowTime: nowTime, array: orderedPile)
}
return orderedPile
}

归并排序 从下至上

由于Int数组,可以直接合并,不需要分解的这个步骤,有点类似冒泡,所以以下是数组直接合并的写法

  • 由于不能够直接对要排序数组作修改,所以需要一个临时数组。为了节省空间,使用了一个二维数组z来存放两个数组

  • 逻辑和上述的合并逻辑一致:设置两个游标0和1,设置合并宽度width为1,最开始所有数组元素都是独立的,也就完成了分解的步骤,所以我们直接合并。

  • 合并成2个2个的数组并且排序,元素0、1,元素2、3 …

  • 将width设置为2,于是4个4个的数组,直至width > n,合并完毕

    img

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
func mergeSortBottomUp(nowTime: TimeInterval ,_ isOrderedBefore: @escaping (Int, Int) -> Bool) {
DispatchQueue.global(qos: .userInitiated).async {
let n = self.unsortedArray.count
var z = [self.unsortedArray, self.unsortedArray]
var d = 0
var width = 1
while width < n {
var i = 0
while i < n {
var j = i
var l = i
var r = i + width
let lmax = min(l + width, n)
let rmax = min(r + width, n)
while l < lmax && r < rmax {
if isOrderedBefore(z[d][l], z[d][r]) {
z[1 - d][j] = z[d][l]
l += 1
self.reloadView(nowTime: nowTime, array: z[1-d])
} else {
z[1 - d][j] = z[d][r]
r += 1
self.reloadView(nowTime: nowTime, array: z[1-d])
}
j += 1
}
while l < lmax {
z[1 - d][j] = z[d][l]
j += 1
l += 1
self.reloadView(nowTime: nowTime, array: z[1-d])
}
while r < rmax {
z[1 - d][j] = z[d][r]
j += 1
r += 1
self.reloadView(nowTime: nowTime, array: z[1-d])
}
i += width*2
}
width *= 2
d = 1 - d
}
}
}

UI实现方法

排序方法里只会去调用绘图方法,本身的实现完全可以脱离视图

传入参数nowTime为当前时间计算出算法动画实现时间(并不是真实的算法速度),’<’ 是比较clourse的操作符

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
switch self.segmentControl.selectedSegmentIndex {
case 0:
// 归并
DispatchQueue.global(qos: .userInitiated).async {
_ = self.mergeSort(self.unsortedArray, NSDate().timeIntervalSince1970)
}
case 1:
// 插入
insertionSort(NSDate().timeIntervalSince1970, <)
case 2:
// 归并 冒泡版
mergeSortBottomUp(nowTime: NSDate().timeIntervalSince1970, < )
case 3:
// 选择
SelectionSort(nowTime: NSDate().timeIntervalSince1970)
default:
break
}

函数initData 构造了一个count -1大小的一个随机数组,范围在1~1000

1
2
3
4
5
6
7
8
9
func initData() {
var i = 1
unsortedArray.removeAll()
while i < count {
unsortedArray.append(Int(arc4random()%1000)+1)
i += 1
}
setupUI(unsortedArray)
}

函数setupUI 绘制了数组元素值占1000的比值 乘以 所在UIView的高度,来视觉化一个数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
func setupUI(_ array: [Int]) {
releaseMemory()
var i = 0
let Arrayview = UIView()
Arrayview.backgroundColor = UIColor.white
Arrayview.frame = CGRect(x: 0 , y: 64 + 29 , width: kScreenW, height:kScreenH - 44)
for x in array {
let width: CGFloat = (kScreenW / (CGFloat)(count))
let height: CGFloat = ((kScreenH - 50) * (CGFloat)(x) / 1000)
let make = CGRect(x: 5 + (CGFloat)(i) * width, y: kScreenH + 44 - 93 , width: width / 2, height:-height)
let view = UIView.init(frame: make)
view.backgroundColor = UIColor.blue
Arrayview.addSubview(view)
i += 1
}
self.view.addSubview(Arrayview)
}
  • 如果我的数组有100个元素也就是说我要画100个UIView,会占据几M的内存而已。但是如果我每次数组变化的时候都只往上加而不remove的话,你知道比较的次数有多少吧!对的内存爆炸了,我们需要release掉前面加的UIView,然后再添加我们需要的最后一个看的见的

  • 断点查看后,从第6个开始我们都可以去除掉,这样100个元素的排序从内存消耗只增不减到不超过5M

1
2
3
4
5
func releaseMemory() {
while self.view.subviews.count > 5 {
self.view.subviews[5].removeFromSuperview()
}
}

动画显示

  • 在处理完怎么把数组视觉化后,这个变化的动画效果要怎么显现出来呢?在我花了一个下午的调试多线程后,终于解决了。其实原理我是知道的,但是怎么写,怎么实现,花了比较长的时间。

  • 原理:UI的刷新需要在主线程,所以排序算法就需要在另一个线程中执行了。下面就是调用绘制动画的方法。其中semaphore是值为1的信号量,为了在绘制UI的时候阻塞排序线程,为了让动画有时间可以让肉眼可见,人为的设置了一个短暂的休眠时间,在这个时间之后我们使得信号量+1,排序线程继续执行

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
let semaphore = DispatchSemaphore(value: 1)
func SortAlgorithm() {
DispatchQueue.global(qos: .userInitiated).async {
当数组元素发生变化,调用动画绘制方法
self.reloadView(nowTime: nowTime, array: a)
}
}
func reloadView(nowTime: TimeInterval,array: [Int]) {
self.semaphore.wait()
DispatchQueue.main.async {
self.setupUI(array)
sleep(UInt32(0.002))
self.semaphore.signal()
// 动画的显示速度不与真实算法速度匹配,原因: 动画刷新在元素有交换时,所以同样的归并算法动画速度并不一致
let interval = (NSDate().timeIntervalSince1970 - nowTime)
self.title = "耗时(秒): \(interval)"
}
}

Links

Merge Sort

Insert Sort

Selection Sort

我的微博

Github