以前的文章中近她，我們主要是在講數(shù)據(jù)結(jié)構(gòu)：比如數(shù)組叉瘩、鏈表、隊(duì)列粘捎、樹薇缅。這些數(shù)據(jù)結(jié)構(gòu)都是了解Swift和算法的基礎(chǔ)。從今以后的文章攒磨，我們將更多的關(guān)注于通用算法泳桦，這次我們就來聊聊排序。這次的主要內(nèi)容有：
- 基本概念
- 排序?qū)崙?zhàn)
基本概念
我們平常用的排序算法一般就以下幾種：
| 名稱 | 時(shí)間復(fù)雜度 | 空間復(fù)雜度 | 是否穩(wěn)定 |
|---|---|---|---|
| 冒泡排序 | O(n^2) | O(1) | 是 |
| 插入排序 | O(n^2) | O(1) | 是 |
| 選擇排序 | O(n^2) | O(1) | 否 |
| 堆排序 | O(nlogn) | O(1) | 否 |
| 歸并排序 | O(nlogn) | O(n) | 是 |
| 快速排序 | O(nlogn) | O(1) | 否 |
| 桶排序 | O(n) | O(k) | 是 |
這些算法具體的定義本文不再贅述娩缰。一般情況下灸撰，好的排序算法性能是O(nlogn)，壞的性能是O(n^2)拼坎。本文在此用swift示范實(shí)現(xiàn)歸并排序：
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 < high else {
return
}
let middle = (high - low) / 2 + low
mergeSort(&array, &helper, low, middle)
mergeSort(&array, &helper, middle + 1, high)
merge(&array, &helper, low, middle, high)
}
func merge(inout array: [Int], inout _ helper: [Int], _ low: Int, _ middle: Int, _ high: Int) {
// copy both halves into a helper array
for i in low ... high {
helper[i] = array[i]
}
var helperLeft = low
var helperRight = middle + 1
var current = low
// iterate through helper array and copy the right one to original array
while helperLeft <= middle && helperRight <= high {
if helper[helperLeft] <= helper[helperRight] {
array[current] = helper[helperLeft]
helperLeft += 1
} else {
array[current] = helper[helperRight]
helperRight += 1
}
current += 1
}
// handle the rest
guard middle - helperLeft >= 0 else {
return
}
for i in 0 ... middle - helperLeft {
array[current + i] = helper[helperLeft + i]
}
}
表格中有一個(gè)特例是桶排序浮毯，它是將輸入的數(shù)組分配到一定數(shù)量的空桶中，每個(gè)空桶再單獨(dú)排序泰鸡。當(dāng)輸入的數(shù)組是均勻分配時(shí)债蓝，桶排序的時(shí)間復(fù)雜度為O(n)。舉個(gè)微軟的面試題來當(dāng)例子：
有三種顏色（紅盛龄，黃饰迹，藍(lán)）的球若干，要求將所有紅色的球放在黃色球的前面余舶，最后放上所有的藍(lán)色球蹦锋。
這道題目最直接的解法就是桶排序。首先第一次遍歷欧芽，統(tǒng)計(jì)有多少個(gè)紅色球（假設(shè)x個(gè)）莉掂，多少個(gè)黃色球（假設(shè)y個(gè)），和多少個(gè)藍(lán)色球（假設(shè)z個(gè)）千扔。然后再一次遍歷憎妙，數(shù)組前部x個(gè)位置填充紅色球，中間y個(gè)位置放上對(duì)應(yīng)數(shù)量的黃色球曲楚，最后z個(gè)位置再放上藍(lán)色球厘唾。
另外解釋一下穩(wěn)定的意思：相等的鍵值，如果排過序后與原來未排序的次序相同龙誊，則稱此排序算法為穩(wěn)定抚垃。舉個(gè)例子：
// 原數(shù)組
[[2, 1], [1,3], [1,4]]
// 排序算法一
[[1,3], [1,4], [2, 1]]
// 排序算法二
[[1,4], [1,3], [2, 1]]
我們注意到排序算法一和二的區(qū)別就在于對(duì)[1, 3], [1, 4]這兩個(gè)元素的處理。排序算法一中，這兩個(gè)元素位置與原數(shù)組相同鹤树，故稱其為穩(wěn)定算法铣焊。而排序算法二則是不穩(wěn)定算法。
Swift中罕伯，排序的使用如下：
// 以升序排列為例曲伊，原數(shù)組可改變
array.sort
// 以降序排列為例，原數(shù)組不可改變
newArray = array.sorted(by: >)
// 字典鍵值排序示例
let keys = Array(map.keys)
let sortedKeys = keys.sorted() {
return map[$0]! > map[$1]!
}
在其他語言比如Java中追他，其自帶的sort函數(shù)是用歸并排序?qū)崿F(xiàn)的坟募。而在Swift源代碼中，sort函數(shù)采用的是一種內(nèi)審算法(IntroSort)邑狸。它由堆排序懈糯、插入排序、快速排序三種算法構(gòu)成单雾，依據(jù)輸入的深度相應(yīng)選擇最佳的算法來完成昂利。本文關(guān)注的重點(diǎn)是實(shí)戰(zhàn)，所以不做展開铁坎。對(duì)源代碼感興趣的朋友可以去Github讀蘋果的Swift的開源庫蜂奸。
排序?qū)崙?zhàn)
直接來看一道Facebook, Google, Linkedin都考過的面試題。
已知有很多會(huì)議硬萍，如果有這些會(huì)議時(shí)間有重疊扩所，則將它們合并。
比如有一個(gè)會(huì)議的時(shí)間為3點(diǎn)到5點(diǎn)朴乖，另一個(gè)會(huì)議時(shí)間為4點(diǎn)到6點(diǎn)祖屏，那么合并之后的會(huì)議時(shí)間為3點(diǎn)到6點(diǎn)
解決算法題目第一步永遠(yuǎn)是把具體問題抽象化。這里每一個(gè)會(huì)議我們已知開始時(shí)間和結(jié)束時(shí)間买羞，就可以寫一個(gè)類來定義它：
public class MeetingTime {
public var start: Int
public var end: Int
public init(_ start: Int, _ end: Int) {
self.start = start
self.end = end
}
}
然后題目說已知有很多會(huì)議袁勺，就是說我們已知有一個(gè)MeetingTime的數(shù)組、所以題目就轉(zhuǎn)化為寫一個(gè)函數(shù)畜普，輸入為一個(gè)MeetingTime的數(shù)組期丰，輸出為一個(gè)將原數(shù)組中所有重疊時(shí)間都處理過的新數(shù)組。
func merge(meetingTimes: [MeetingTime]) -> [MeetingTime] {}
下面來分析一下題目怎么解吃挑。最基本的思路是遍歷一次數(shù)組钝荡，然后歸并所有重疊時(shí)間。舉個(gè)例子：[[1, 3], [5, 6], [4, 7], [2, 3]]舶衬。這里我們可以發(fā)現(xiàn)[1, 3]和[2, 3]可以歸并為[1, 3]埠通，[5, 6]和[4, 7]可以歸并為[5, 7]。所以這里就提出一個(gè)要求：要將所有可能重疊的時(shí)間盡量放在一起逛犹，這樣遍歷的時(shí)候可以就可以從前往后一個(gè)接著一個(gè)的歸并端辱。于是很自然的想到 -- 按照會(huì)議開始的時(shí)間排序梁剔。
這里我們要對(duì)一個(gè)class進(jìn)行排序，而且要自定義排序方法舞蔽，在Swift中可以這樣寫：
meetingTimes.sortInPlace() {
if $0.start != $1.start {
return $0.start < $1.start
} else {
return $0.end < $1.end
}
}
意思就是首先對(duì)開始時(shí)間進(jìn)行升序排列荣病，如果它們相同，就比較結(jié)束時(shí)間喷鸽。
有了排好順序的數(shù)組众雷，要得到新的歸并后的結(jié)果數(shù)組灸拍，我們只需要在遍歷的時(shí)候做祝，每次比較原數(shù)組（排序后）當(dāng)前會(huì)議時(shí)間與結(jié)果數(shù)組中當(dāng)前的會(huì)議時(shí)間，假如它們有重疊鸡岗，則歸并混槐；如果沒有，則直接添加進(jìn)結(jié)果數(shù)組之中轩性。所有代碼如下：
func merge(meetingTimes: [MeetingTime]) -> [MeetingTime] {
// 處理特殊情況
guard meetingTimes.count > 1 else {
return meetingTimes
}
// 排序
var meetingTimes = meetingTimes.sort() {
if $0.start != $1.start {
return $0.start < $1.start
} else {
return $0.end < $1.end
}
}
// 新建結(jié)果數(shù)組
var res = [MeetingTime]()
res.append(meetingTimes[0])
// 遍歷排序后的原數(shù)組声登，并與結(jié)果數(shù)組歸并
for i in 1..<meetingTimes.count {
let last = res[res.count - 1]
let current = meetingTimes[i]
if current.start > last.end {
res.append(current)
} else {
last.end = max(last.end, current.end)
}
}
return res
}
展望
排序在Swift中的應(yīng)用場景很多，比如tableView中對(duì)于dataSource的處理揣苏。當(dāng)然很多時(shí)候悯嗓，排序都是和搜索，尤其是二分搜索配合使用卸察。下期探討搜索的時(shí)候脯厨，會(huì)對(duì)排序進(jìn)行進(jìn)一步拓展。
