以前的文章中，我们主要是在讲数据结构：比如数组、链表、队列、树。这些数据结构都是了解Swift和算法的基础。从今以后的文章，我们将更多的关注于通用算法，这次我们就来聊聊排序。这次的主要内容有：
- 基本概念
- 排序实战
基本概念
我们平常用的排序算法一般就以下几种：
| 名称 | 时间复杂度 | 空间复杂度 | 是否稳定 |
|---|---|---|---|
| 冒泡排序 | O(n^2) | O(1) | 是 |
| 插入排序 | O(n^2) | O(1) | 是 |
| 选择排序 | O(n^2) | O(1) | 否 |
| 堆排序 | O(nlogn) | O(1) | 否 |
| 归并排序 | O(nlogn) | O(1) | 是 |
| 快速排序 | O(nlogn) | O(1) | 否 |
| 桶排序 | O(n) | O(k) | 是 |
这些算法具体的定义本文不再赘述。一般情况下，好的排序算法性能是O(nlogn)，坏的性能是O(n^2)。本文在此用swift示范实现归并排序：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
func mergeSort(array: [Int]) -> [Int] { var helper = Array(count: array.count, repeatedValue: 0) var array = array mergeSort(&array, &helper, 0, array.count - 1) return array } func mergeSort(inout array: [Int], inout _ helper: [Int], _ low: Int, _ high: Int) { guard low = 0 else { return } for i in 0 ... middle - helperLeft { array[current + i] = helper[helperLeft + i] } } |
表格中有一个特例是桶排序，它是将输入的数组分配到一定数量的空桶中，每个空桶再单独排序。当输入的数组是均匀分配时，桶排序的时间复杂度为O(n)。举个微软的面试题来当例子：
有三种颜色（红，黄，蓝）的球若干，要求将所有红色的球放在黄色球的前面，最后放上所有的蓝色球。
这道题目最直接的解法就是桶排序。首先第一次遍历，统计有多少个红色球（假设x个），多少个黄色球（假设y个），和多少个蓝色球（假设z个）。然后再一次遍历，数组前部x个位置填充红色球，中间y个位置放上对应数量的黄色球，最后z个位置再放上蓝色球。
另外解释一下稳定的意思：相等的键值，如果排过序后与原来未排序的次序相同，则称此排序算法为稳定。举个例子：
|
1 2 3 4 5 6 7 |
// 原数组 [[2, 1], [1,3], [1,4]] // 排序算法一 [[1,3], [1,4], [2, 1]] // 排序算法二 [[1,4], [1,3], [2, 1]] |
我们注意到排序算法一和二的区别就在于对[1, 3], [1, 4]这两个元素的处理。排序算法一中，这两个元素位置与原数组相同，故称其为稳定算法。而排序算法二则是不稳定算法。
Swift中，排序的使用如下：
|
1 2 3 4 5 6 7 8 9 10 |
// 以升序排列为例，原数组可改变 array.sortInPlace() // 字典键值排序示例 let keys = Array(map.keys) let sortedKeys = keys.sort() { let value1 = map[$0] let value2 = map[$1] return value1 > value2 } |
在其他语言比如Java中，其自带的sort函数是用归并排序实现的。而在Swift源代码中，sort函数采用的是一种内审算法(IntroSort)。它由堆排序、插入排序、快速排序三种算法构成，依据输入的深度相应选择最佳的算法来完成。本文关注的重点是实战，所以不做展开。对源代码感兴趣的朋友可以去Github读苹果的Swift的开源库。
排序实战
直接来看一道Facebook, Google, Linkedin都考过的面试题。
已知有很多会议，如果有这些会议时间有重叠，则将它们合并。
比如有一个会议的时间为3点到5点，另一个会议时间为4点到6点，那么合并之后的会议时间为3点到6点
解决算法题目第一步永远是把具体问题抽象化。这里每一个会议我们已知开始时间和结束时间，就可以写一个类来定义它：
|
1 2 3 4 5 6 7 8 |
public class MeetingTime { public var start: Int public var end: Int public init(_ start: Int, _ end: Int) { self.start = start self.end = end } } |
然后题目说已知有很多会议，就是说我们已知有一个MeetingTime的数组、所以题目就转化为写一个函数，输入为一个MeetingTime的数组，输出为一个将原数组中所有重叠时间都处理过的新数组。
|
1 |
func merge(meetingTimes: [MeetingTime]) -> [MeetingTime] {} |
下面来分析一下题目怎么解。最基本的思路是遍历一次数组，然后归并所有重叠时间。举个例子：[[1, 3], [5, 6], [4, 7], [2, 3]]。这里我们可以发现[1, 3]和[2, 3]可以归并为[1, 3]，[5, 6]和[4, 7]可以归并为[5, 7]。所以这里就提出一个要求：要将所有可能重叠的时间尽量放在一起，这样遍历的时候可以就可以从前往后一个接着一个的归并。于是很自然的想到 — 按照会议开始的时间排序。
这里我们要对一个class进行排序，而且要自定义排序方法，在Swift中可以这样写：
|
1 2 3 |
meetingTimes.sortInPlace() { if $0.start != $1.start { return $0.start |
意思就是首先对开始时间进行升序排列，如果它们相同，就比较结束时间。
有了排好顺序的数组，要得到新的归并后的结果数组，我们只需要在遍历的时候，每次比较原数组（排序后）当前会议时间与结果数组中当前的会议时间，假如它们有重叠，则归并；如果没有，则直接添加进结果数组之中。所有代码如下：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
func merge(meetingTimes: [MeetingTime]) -> [MeetingTime] { // 处理特殊情况 guard meetingTimes.count > 1 else { return meetingTimes } // 排序 var meetingTimes = meetingTimes.sort() { if $0.start != $1.start { return $0.start last.end { res.append(current) } else { last.end = max(last.end, current.end) } } return res } |
展望
排序在Swift中的应用场景很多，比如tableView中对于dataSource的处理。当然很多时候，排序都是和搜索，尤其是二分搜索配合使用。下期探讨搜索的时候，会对排序进行进一步拓展。
