排序算法之Swift实践

当我们站在历史的今天,往过去回顾,总会发现一些在当下习以为常的观念,惊讶在过去竟然没人意识到,比如生产力决定生产关系,比如自由平等,这就是所谓的进步。我生于上世纪九十年代初,年纪尚轻,这些观念的巨大变革,我大多从书上学来的,如果要找一些真正有切身体会的,我想就是当下有点烂大街的用户体验。与过去单纯讲究功能性的时代相比,用户体验绝对是完全颠覆的,它完全变换了产品的核心,给人一种醍醐灌顶的顿悟感,想及此,还是要感谢乔布斯和他的苹果。

算法与用户体验看似没有关系,其实算法是上佳用户体验的基础,因为没有高效的算法,机子会卡。我至今仍是编程小白,为加深对算法的理解,本文尝试用Swift实现大部分常用的排序算法。

经典排序算法

插入排序

1
2
3
4
5
6
7
8
9
10
11
12
13
//不改变输入数组的状态,返回排序完成的降序数组
func insertionSort(var arr:[Int]) -> [Int] {
for var i = 1; i < arr.count; i++ {
let key = arr[i]
var j = i - 1
while j >= 0 && arr[j] > key {
arr[j+1] = arr[j]
j--
}
arr[j+1] = key
}
return arr
}

插入排序为原址排序,总耗时与输入的分布有关,当输入为倒序时,为最坏输入分布,排序时间为Θ(n^2),当输入为正序时,为最佳输入分布,排序时间为Θ(n),其中n是输入规模。

冒泡排序

1
2
3
4
5
6
7
8
9
10
11
12
func bubleSort(var arr: [Int]) -> [Int] {
for var i = arr.count - 1; i > 0; i-- {
for var j = 0; j < i; j++ {
if arr[j] > arr[j + 1] {
let temp = arr[j]
arr[j] = arr[j + 1]
arr[j + 1] = temp
}
}
}
return arr
}

冒泡排序为原址排序,总耗时与输入的分布无关,耗时O(n^2)

高阶排序算法

归并排序

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
//不改变输入数组的状态,返回排序完成的降序数组
func mergeSort(var arr: [Int]) -> [Int] {
func internalMergeSort(p: Int, _ r: Int) {
if p < r {
let q = Int(
floor(Double(p + r) / 2.0)
)
internalMergeSort(p, q)
internalMergeSort(q + 1, r)
merge(p, q, r)
}
}
func merge(p: Int, _ q: Int, _ r: Int ) {
var leftA = [Int]()
var rightA = [Int]()
for var i = p; i <= q; i++ {
leftA.append(arr[i])
}
for var i = q + 1; i <= r; i++ {
rightA.append(arr[i])
}

for var k = p; k <= r ; k++ {
if !leftA.isEmpty && !rightA.isEmpty && leftA[0] <= rightA[0] {
arr[k] = leftA.removeFirst()
} else if leftA.isEmpty && !rightA.isEmpty{
arr[k] = rightA.removeFirst()
} else if !leftA.isEmpty && rightA.isEmpty {
arr[k] = leftA.removeFirst()
} else {
arr[k] = rightA.removeFirst()
}
}
}
internalMergeSort(0, arr.count - 1)
return arr
}

归并算法的总耗时与输入分布无关,耗时Θ(nlgn),但不是原址排序,空间复杂度略高,占用较多内存。

堆排序

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
//代码中用到了floor:函数,因此必须导入UIKit模块
import UIKit
//不改变输入数组的状态,返回排序完成的降序数组
func heapSort(var arr: [Int]) -> [Int] {
func left(i: Int) -> Int {
return 2 * i + 1
}
func right(i: Int) -> Int {
return 2 * i + 2
}

func maxHeapify(i: Int, heapSize: Int) {
let l = left(i)
let r = right(i)
var largest = i

if l < heapSize && arr[largest] < arr[l] {
largest = l
}
if r < heapSize && arr[largest] < arr[r] {
largest = r
}

if largest != i {
let temp = arr[i]
arr[i] = arr[largest]
arr[largest] = temp
maxHeapify(largest, heapSize: heapSize)
}
}

func buildMaxHeap() {
for var i = Int(floor(Double(arr.count) / 2.0 - 1.0)); i >= 0; i-- {
maxHeapify(i, heapSize: arr.count)
}
}

func internalHeapSort() {
for var i = arr.count - 1; i > 0; i-- {
let temp = arr[i]
arr[i] = arr[0]
arr[0] = temp
maxHeapify(0, heapSize: i)
}
}
buildMaxHeap()
internalHeapSort()
return arr
}

堆排序算法耗时依赖输入的分布,其总耗时O(nlgn)。

快速排序

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
//经典快速排序,为原址排序
func quickSort(var arr: [Int]) -> [Int] {
func partition(p: Int, _ r: Int) -> Int {
var i = p - 1
let key = arr[r]
for var j = p; j < r; j++ {
if arr[j] < key {
i = i + 1
let temp = arr[j]
arr[j] = arr[i]
arr[i] = temp
}
}
arr[r] = arr[i + 1]
arr[i + 1] = key
return i + 1
}

func internalQuickSort(p: Int, _ r: Int) {
if p < r {
let q = partition(p, r)
internalQuickSort(p, q - 1)
internalQuickSort(q + 1, r)
}
}
internalQuickSort(0, arr.count - 1)
return arr
}

快速排序为原址排序,耗时依赖于输入分布,最坏耗时Θ(n^2),最好耗时Θ(nlgn),而平均耗时非常接近最好耗时情形,因此快速排序在实际中有广泛的应用。

上述排序算法没有利用Array的高阶函数filter:,如果用filter:函数重写,代码更加简洁:

1
2
3
4
5
6
7
8
9
10
//利用高阶函数filter:实现快速排序
func quickSort(var arr: [Int]) -> [Int] {
if arr.count > 0 {
let q = arr.removeFirst()
let leftA = arr.filter{$0 <= q}
let rightA = arr.filter{$0 > q}
return quickSort(leftA) + [q] + quickSort(rightA)
}
return arr
}

利用高阶函数filter:实现快速排序,虽然使代码开起来非常简洁,但却牺牲了原址排序的空间简洁性,大幅增大了内存的消耗。

验证

验证如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
let arr = [2, 1, 6, 4, 3]
print("-------- 输入数组 --------")
print(arr)
print("-------- 插入排序结果 --------")
print(insertionSort(arr))
print("-------- 冒泡排序结果 --------")
print(bubleSort(arr))
print("-------- 归并排序结果 --------")
print(mergeSort(arr))
print("-------- 堆排序结果 --------")
print(heapSort(arr))
print("-------- 快速排序结果 --------")
print(quickSort(arr))

输出结果为:

1
2
3
4
5
6
7
8
9
10
11
12
--------  输入数组  --------
[2, 1, 6, 4, 3]
-------- 插入排序结果 --------
[1, 2, 3, 4, 6]
-------- 冒泡排序结果 --------
[1, 2, 3, 4, 6]
-------- 归并排序结果 --------
[1, 2, 3, 4, 6]
-------- 堆排序结果 --------
[1, 2, 3, 4, 6]
-------- 快速排序结果 --------
[1, 2, 3, 4, 6]

总结

每一种算法都代表着一种不同的思路,甚至是一种思想,如归并排序代表着分治的思想,堆排序代表着堆的思想。思想的变化,看待问题角度的转换,总是给人无数的乐趣。也说明要想有大的突破,人不能太狭隘。

分享到 评论