排序就是將一組對(duì)象按照某種邏輯順序重新排列的過程的烁，所有計(jì)算機(jī)系統(tǒng)都實(shí)現(xiàn)了各種排序算法以供系統(tǒng)和用戶使用。學(xué)習(xí)排序算法有三大實(shí)際意義：
- 對(duì)排序算法的分析將有助于你全面理解比較算法性能的方法；
- 類似的技術(shù)也能有效解決其他類型的問題耸弄；
- 排序算法常常是我們解決其他問題的第一步砰诵。
本文中我們學(xué)習(xí)幾種經(jīng)典的排序算法，并高效的實(shí)現(xiàn)了“優(yōu)先隊(duì)列”這種基礎(chǔ)數(shù)據(jù)類型理肺。我們將討論比較排序算法的理論基礎(chǔ)并在結(jié)尾總結(jié)若干排序算法和優(yōu)先隊(duì)列的應(yīng)用。
一、初級(jí)排序算法
我們先學(xué)習(xí)兩種初級(jí)排序算法及其中一種的一個(gè)變體囱怕。深入學(xué)習(xí)這些相對(duì)簡(jiǎn)單算法的原因在于：
- 熟悉一些術(shù)語和簡(jiǎn)單技巧；
- 這些簡(jiǎn)單算法在某些情況下比之后學(xué)習(xí)的復(fù)雜算法更有效；
- 它們有助于我們改進(jìn)復(fù)雜算法的效率挽霉。
1. 游戲規(guī)則
我們關(guān)注的主要對(duì)象是重新排列數(shù)組元素的算法（通常按照大小或者字母順序）。從小到大排列
下面的 Sort 類展示了我們的習(xí)慣約定：我們使用子類來繼承 Sort 來實(shí)現(xiàn)不同的排序?qū)崿F(xiàn)实胸，例如 Insertion、Merge、Quick 等讶凉。
例如輸入：["S", "O", "R", "T", "E", "X", "A", "M", "P", "L", "E"]
輸出：["A", "E", "E", "L", "M", "O", "P", "R", "S", "T", "X"]
class Sort<Sortable> where Sortable: Comparable {
init(args: [Sortable]) {
var a = args
sort(a: &a)
assert(isSorted(a: a))
show(a: a)
}
func sort(a: inout [Sortable]) {
/* 請(qǐng)見算法1.1慕匠、算法1.2蓉媳、算法1.3减宣、算法1.4、算法1.5闷尿、算法1.7 */
}
func exch(a: inout [Sortable], i: Int, j: Int) {
let t = a[I]
a[i] = a[j]
a[j] = t
}
func less(v: Sortable, w: Sortable) -> Bool {
return v < w
}
private func show (a: [Sortable]) {
print(a)
}
func isSorted(a: [Sortable]) -> Bool {
// 測(cè)試數(shù)組元素是否有序
for i in 1..<a.count {
if less(v: a[i], w: a[i-1]) {
return false
}
}
return true
}
}
驗(yàn)證：無論數(shù)組初始狀態(tài)是什么匆骗，排序算法都能成功嗎盟广？謹(jǐn)慎起見使用 assert(isSorted(a: a)) 來確認(rèn)排序的正確性。
運(yùn)行時(shí)間：我們要評(píng)估算法性能毛甲。首先要計(jì)算各個(gè)排序算法在不同的隨機(jī)輸入下的基本操作的次數(shù)（包括比較和交換，或者是讀寫數(shù)組的次數(shù)）跃惫。然后我們用這些數(shù)據(jù)來估計(jì)算法的性能并介紹在實(shí)驗(yàn)中驗(yàn)證這些猜想所使用的工具。
排序成本模型先较。在研究排序算法時(shí)，我們需要計(jì)算比較和交換的數(shù)量。對(duì)于不交換元素的算法，我們會(huì)計(jì)算訪問數(shù)組的次數(shù)
額外內(nèi)存使用：排序算法的額外內(nèi)存開銷和運(yùn)行時(shí)間同樣重要勺远。排序算法可以分為兩類：除了函數(shù)調(diào)用所需的棧和固定數(shù)目的實(shí)例變量之外無須額外內(nèi)存的原地排序算法，以及需要額外內(nèi)存空間來存儲(chǔ)另外一份數(shù)組副本的其他排序算法。
數(shù)據(jù)類型：我們的排序算法模板適用于任何實(shí)現(xiàn)了 Comparable 協(xié)議的數(shù)據(jù)類型某筐。好處是系統(tǒng)實(shí)現(xiàn)了 Camparable 數(shù)組的排序方法蜜托，因此你可以直接用這些類型數(shù)組作為參數(shù)調(diào)用我們的排序方法幔托。
2. 選擇排序
一種最簡(jiǎn)單的排序算法是：找到數(shù)組中最小的那個(gè)元素嗓化，將它和數(shù)組的第一個(gè)元素交換位置，然后剩下的元素中找最小元素谦屑，與第二個(gè)元素交換位置很洋。如此往復(fù)，直到排完整個(gè)數(shù)組协怒，這種方法叫做選擇排序赤兴。
算法1.1
class Selection<Sortable>: Sort<Sortable> where Sortable: Comparable {
override func sort(a: inout [Sortable]) {
let N = a.count
for i in 0..<N {
var min = I;
for j in i..<N {
if less(v:a[j], w:a[min]) {
min = j
}
}
exch(a: &a, i: i, j: min);
}
}
}
![]()
算法1.1：選擇排序的軌跡
如算法 1.1 所示，交換元素的代碼寫在內(nèi)循環(huán)之外曲秉，每次交換都能排定一個(gè)元素纲爸，因此交換的總次數(shù)是 N读虏。所以算法的時(shí)間效率取決于比較的次數(shù)灾螃。
命題 A：對(duì)于長度為 N 的數(shù)組，選擇排序需要大約 N2/2次比較和 N 次交換
證明：通過查看代碼我們可以精確的得到，0 到 N-1 的任意 i 都會(huì)進(jìn)行一次交換和 N-1-i 次比較彼硫，因此總共有 N 次交換以及 (N-1)+(N-2)+...+2+1 = N(N-1)/2 ≈ N2/2
選擇排序有兩個(gè)鮮明特點(diǎn)：
- 運(yùn)行時(shí)間和輸入無關(guān)
- 移動(dòng)數(shù)據(jù)最少：每次交換改變兩個(gè)數(shù)組元素的值牵舱。共 N 次交換——交換次數(shù)和數(shù)組大小是線性關(guān)系礁凡。我們研究的其他任何算法都不具備這個(gè)特征（大部分的增長數(shù)量級(jí)都是線性對(duì)數(shù)或者平方級(jí)別）
3. 插入排序
通常人們整理橋牌的方法是一張一張的來，將每一張牌插入到其他已經(jīng)有序的牌中的適當(dāng)位置。
算法 1.2
class Insertion<Sortable>: Sort<Sortable> where Sortable: Comparable {
override func sort(a: inout [Sortable]) {
for i in 1..<a.count {
for j in stride(from: i, to: 0, by: -1) {
if less(v: a[j], w: a[j-1]) {
exch(a: &a, i: j, j: j-1)
} else { break }
}
}
}
}
命題B：對(duì)于隨機(jī)排列的長度為 N 且主鍵不重復(fù)的數(shù)組，平均情況下插入排序需要 ≈ N2/4 次比較以及 ≈ N2/4 次交換。最壞情況下需要 ≈ N2/2 次比較和 ≈ N2/2 次交換，最好情況下需要 N-1 次比較和 0 次交換关划。
證明：和命題 A 一樣，通過一個(gè) NxN 的軌跡表可以很容易就得到交換和比較次數(shù)。最壞情況下對(duì)角線之下的所有元素都需要移動(dòng)位置筐带，最好情況下都不需要腮出。對(duì)于隨機(jī)排列的數(shù)組，在平均情況下每個(gè)元素都可能向后移動(dòng)半個(gè)數(shù)組的長度，因此交換總數(shù)是對(duì)角線之下的元素總數(shù)的1/2侣滩。
所有 (1+2+...+N-2+N-1)/2 = N(N-1)/4≈ N2/4
插入排序?qū)τ趯?shí)際應(yīng)用中常見的某些類型的非隨機(jī)數(shù)組很有效娇斑。例如唯竹，對(duì)有序或者接近有序的數(shù)組進(jìn)行進(jìn)行排序時(shí)，插入排序能夠立即發(fā)現(xiàn)每個(gè)元素已經(jīng)在合適位置了棵磷，這是它的運(yùn)行時(shí)間也是線性的姻僧。
下面是幾種典型的部分有序的數(shù)組：
- 數(shù)組中每個(gè)元素距離它的最終位置都不遠(yuǎn)
- 一個(gè)有序的大數(shù)組接一個(gè)小數(shù)組
- 數(shù)組中只有幾個(gè)元素的位置不正確
插入排序?qū)@樣的數(shù)組很有效，而選擇排序則不然艘狭，事實(shí)上尽超，當(dāng)?shù)怪脭?shù)量很少時(shí)官撼，插入排序很可能比本文其他任何算法都要快
要大幅提高插入排序的速度并不難，只需要在內(nèi)循環(huán)中將較大元素都向右移而不總是交換兩個(gè)元素（這樣訪問數(shù)組的次數(shù)就能減半）
總的來說似谁，插入排序?qū)τ诓糠钟行虻臄?shù)組十分高效傲绣，也很適合小規(guī)模數(shù)組巩踏，而且它們也是高級(jí)排序算法的中間過程秃诵，在學(xué)習(xí)高級(jí)排序算法時(shí)會(huì)再次接觸插入排序。
4. 希爾排序
為展示初級(jí)排序算法的價(jià)值塞琼，我們學(xué)習(xí)一種基于插入排序的快速排序算法——希爾排序菠净。因?yàn)椴迦肱判蛑唤粨Q相鄰元素，因此元素只能一點(diǎn)一點(diǎn)從一端移到另一端彪杉。希爾排序?yàn)榱思涌炜焖俸?jiǎn)單地改進(jìn)了插入排序毅往，交換不相鄰的元素以對(duì)數(shù)組局部進(jìn)行排序，并最終用插入排序?qū)⒕植坑行驍?shù)組排序派近。
希爾排序的思想是使數(shù)組中任意間隔為 h 的元素都是有序的煞抬。這樣的數(shù)組被稱為 h 有序數(shù)組。換句話說构哺，一個(gè) h 有序數(shù)組就是 h 個(gè)互相獨(dú)立的有序數(shù)組編織在一起組成的一個(gè)數(shù)組（見圖 1.4.1）革答。在進(jìn)行排序時(shí)战坤，如果 h 很大，我們就能將元素移動(dòng)到很遠(yuǎn)的地方残拐，為了實(shí)現(xiàn)更小的 h 有序創(chuàng)造方便途茫。用這種方式，對(duì)任意以 1 結(jié)尾的 h 序列溪食，我們都能夠?qū)?shù)組排序囊卜。算法 1.3 的實(shí)現(xiàn)使用了序列 1/2(3k-1)，從 N/3 開始遞減至 1错沃。我們把這個(gè)序列成為遞增序列栅组。算法 1.3 實(shí)時(shí)計(jì)算了它的遞增序列，另一種方式是將遞增序列存儲(chǔ)在一個(gè)數(shù)組中枢析。
算法 1.3
class Shell<Sortable>: Sort<Sortable> where Sortable: Comparable {
override func sort(a: inout [Sortable]) {
var h = 1
let N = a.count
while h < N/3 {
h = 3*h+1
}
while h >= 1 {
for i in h..<N {
// 將a[i]插入到a[i-h], a[i-2*h], a[i-3*h]...
for j in stride(from: i, to: h-1, by: -h) {
if less(v: a[j], w: a[j-h]) {
exch(a: &a, i: j, j: j-h)
} else {
break
}
}
}
h = h/3
}
}
}
![]()
希爾排序的軌跡
實(shí)現(xiàn)希爾排序的一種方法是對(duì)于每個(gè) h玉掸，用插入排序?qū)?h 個(gè) 子數(shù)組獨(dú)立地排序。但因?yàn)樽訑?shù)組是相互獨(dú)立的醒叁，一個(gè)更簡(jiǎn)單的方法是在 h 子數(shù)組中將每個(gè)元素交換到比它大的元素之前去（將比它大的元素向右移一格）司浪。只需要在插入排序的代碼中將移動(dòng)元素的距離由 1 改為 h 即可。這樣希爾排序的實(shí)現(xiàn)就轉(zhuǎn)化為了一個(gè)類似插入排序但使用不同增量的過程把沼，這個(gè)改進(jìn)如下：
override func sort(a: inout [Sortable]) {
var h = 1
let N = a.count
while h < N/3 {
h = 3*h+1
}
while h >= 1 {
for i in h..<N {
let t = a[I]
var j = I
while j >= h && less(v: t, w: a[j-h]) {
a[j] = a[j-h]
j -= h
}
a[j] = t
}
h = h/3
}
}
我用一個(gè) Int 類型 10000 個(gè)元素的隨機(jī)數(shù)組進(jìn)行排序測(cè)試啊易，算法 1.3 的時(shí)間大概是 0.11s，改進(jìn)后的運(yùn)行時(shí)間大約為 0.8s饮睬，提高了大約 25%
如何選擇遞增序列呢（算法 1.3 使用 3 倍遞增）租谈？算法的性能不僅取決于 h，還取決于 h 之間的數(shù)學(xué)性質(zhì)捆愁，比如它們的公因子等垦垂。很多論文研究了各種不同遞增序列，但都無法證明某個(gè)序列是 “最好的”牙瓢。算法 1.3 中的遞增序列很簡(jiǎn)單，和復(fù)雜遞增序列性能接近间校。但復(fù)雜遞增序列在最壞的情況下由于算法 1.3矾克。
和選擇排序及插入排序相比，希爾排序可用于大型數(shù)組憔足。它對(duì)任意排序（不一定隨機(jī)）的數(shù)組表現(xiàn)都不錯(cuò)胁附。下面是希爾排序可視軌跡圖
研究希爾排序性能需要的數(shù)學(xué)論證超出本文的范圍。如果你不相信滓彰，可以從證明當(dāng)一個(gè) “h有序”的數(shù)組按照增幅k排序之后控妻，它任然是“h有序”的。算法 1.3 的運(yùn)行時(shí)間達(dá)不到平方級(jí)別揭绑，例如它在最壞的情況下比較次數(shù)和 N3/2成正比弓候。
性質(zhì) E：使用遞增序列1夸研，4贱迟，13蒸播，40，121宿崭，364 ... 的希爾排序所需要的比較次數(shù)不會(huì)超出 N 的若干倍 乘以遞增序列的長度
5. 總結(jié)
我對(duì)一個(gè) Int 類型 10000 個(gè)元素的數(shù)組分別使用選擇排序、插入排序、希爾排序洲守、和 swift 系統(tǒng)自帶的排序比較如下：
let array = getArray()
Thread.sleep(forTimeInterval: 1)
let t1 = CFAbsoluteTimeGetCurrent()
Selection<Int>(args: array)
let t2 = CFAbsoluteTimeGetCurrent()
Insertion<Int>(args: array)
let t3 = CFAbsoluteTimeGetCurrent()
Shell<Int>(args: array)
let t4 = CFAbsoluteTimeGetCurrent()
array.sorted()
let tx = CFAbsoluteTimeGetCurrent()
print(t2-t1)
print(t3-t2)
print(t4-t3)
print(tx-t4)
打印結(jié)果
// 選擇排序的運(yùn)行時(shí)間
24.563407063484192
// 插入排序的運(yùn)行時(shí)間
8.074509978294373
// 希爾排序的運(yùn)行時(shí)間
0.07093596458435059
// swift 系統(tǒng)排序的運(yùn)行時(shí)間
0.0352710485458374
系統(tǒng)排序的時(shí)間是最短的，但是我們可以發(fā)現(xiàn)希爾排序的時(shí)間確實(shí)要比選擇排序和插入排序快太多涤垫。
二吱雏、歸并排序
歸并即將兩個(gè)游戲數(shù)組歸并為一個(gè)更大的有序數(shù)組歧杏。要將一個(gè)數(shù)組排序，可以先（遞歸地）將它分成兩半分別排序囤捻，然后將結(jié)果歸并起來孩擂。你將會(huì)看到，歸并排序最吸引人的性質(zhì)是保證將任意長度為 N 的數(shù)組排序所需要的時(shí)間和 NlogN 成正比；它的主要缺點(diǎn)是需要額外空間和 N 成正比
![]()
歸并排序示意圖
1. 原地歸并的抽象方法
實(shí)現(xiàn)歸并的一種直接方法是將兩個(gè)不同有序數(shù)組歸并到第三個(gè)數(shù)組中圣絮，但是當(dāng)用歸并對(duì)大數(shù)組進(jìn)行排序時(shí)，需要進(jìn)行多次歸并力麸，如果每次都創(chuàng)建一個(gè)新數(shù)組可款，會(huì)帶來性能問題，我們更希望有一種能夠原地歸并的方法末盔，在數(shù)組中移動(dòng)元素不需要額外空間
func merge(_ a: inout [Sortable], _ low: Int, _ mid: Int, _ high: Int) {
// 將 a[low...mid] 和 a[mid+1...high] 歸并
var i = low
var j = mid+1
for k in low...high {
aux[k] = a[k]
}
for k in low...high {
if i > mid {
a[k] = aux[j]
j += 1
} else if j > high {
a[k] = aux[i]
i += 1
} else if (less(v: aux[j], w: aux[i])) {
a[k] = aux[j]
j += 1
} else {
a[k] = aux[i]
i += 1
}
}
}
上面的代碼是 Merge 類的用來歸并數(shù)組的方法，aux 是 Merge 的一個(gè)屬性座慰，用來保證每次歸并只使用 aux 的空間陨舱，放在每次歸并開辟新的數(shù)組空間。
方法在歸并時(shí)進(jìn)行了四個(gè)條件判斷（上面代碼第二個(gè)循環(huán)中的 4 個(gè) if else）這四個(gè)判斷分別代表的意思
-
if i > mid表示左邊的元素用盡開始取右邊 -
if i > high表示右邊的元素用盡開始取左邊 -
if (less(v: aux[j], w: aux[i]))表示右半邊當(dāng)前元素小于左半邊取右邊元素 -
else表示右半邊當(dāng)前元素大于左半邊取左邊元素
下面情況數(shù)組 [E, E, G, M, R, A, C, E, R, T] 調(diào)用 merge 方法的軌跡 其中 low = 0; high = 9; mid = 4; i = 0; j = 5
| 步驟(k值) | i,j | 進(jìn)入分支 | 變換后的數(shù)組 |
|---|---|---|---|
| 0 | 0, 5 | A < E 進(jìn)入分支3 a[0]=A; j+1=6 |
[A,E,G,M,R,A,C,E,R,T] |
| 1 | 0, 6 | C < E 進(jìn)入分支3 a[1]=C; j+1=7 |
[A,C,G,M,R,A,C,E,R,T] |
| 2 | 0, 7 | E == E 進(jìn)入分支4 a[2]=E; i+1=1 |
[A,C,E,M,R,A,C,E,R,T] |
| 3 | 1, 7 | E == E 進(jìn)入分支4 a[3]=E; i+1=2 |
[A,C,E,E,R,A,C,E,R,T] |
| 4 | 2, 7 | E < G 進(jìn)入分支3 a[4]=E; j+1=8 |
[A,C,E,E,E,A,C,E,R,T] |
| 5 | 2, 8 | R > G 進(jìn)入分支4 a[5]=G; i+1=3 |
[A,C,E,E,E,G,C,E,R,T] |
| 6 | 3,8 | R > M 進(jìn)入分支4 a[6]=M; i+1=4 |
[A,C,E,E,E,G,M,E,R,T] |
| 7 | 4,8 | R == R 進(jìn)入分支4 a[7]=R; i+1=5 |
[A,C,E,E,E,G,M,R,R,T] |
| 8 | 5,8 | i(5) > mid(4) 進(jìn)入分支1 a[8]=R; j+1=9 |
[A,C,E,E,E,G,M,R,R,T] |
| 9 | 5, 9 | i(5) > mid(4) 進(jìn)入分支1 a[9]=T; j+1=10 |
[A,C,E,E,E,G,M,R,R,T] |
通過上面的軌跡我們可以看出函數(shù) merge 的功能是將兩個(gè)有序數(shù)組歸并為一個(gè)有序的大數(shù)組版仔，只有當(dāng)我們給定的數(shù)組 a 將其子數(shù)組 a[low...high] 分割為 a[low...mid] 和 a[mid+1...high] 后游盲，只有當(dāng) a[low...mid] 和 a[mid+1...high] 都為有序數(shù)組時(shí)误墓，歸并后的數(shù)組 a[low...high] 也為有序。
2. 自頂向下的并歸排序
算法 1.4 基于原地歸并的方法實(shí)現(xiàn)了另一種遞歸歸并益缎，這也是應(yīng)用高效算法設(shè)計(jì)中分治思想的最典型的一個(gè)例子谜慌。這段遞歸代碼是歸納證明算法能夠正確地將數(shù)組排序的基礎(chǔ)：如果它能將兩個(gè)子數(shù)組排序，它就能通過歸并兩個(gè)子數(shù)組來將整個(gè)數(shù)組排序莺奔。
算法 1.4
class Merge<Sortable>: Sort<Sortable> where Sortable: Comparable {
var aux: [Sortable] = []
func merge(_ a: inout [Sortable], _ low: Int, _ mid: Int, _ high: Int) {
// 將 a[low...mid] 和 a[mid+1...high] 歸并
var i = low
var j = mid+1
for k in low...high {
aux[k] = a[k]
}
for k in low...high {
if i > mid {
a[k] = aux[j]
j += 1
} else if j > high {
a[k] = aux[i]
i += 1
} else if (less(v: aux[j], w: aux[i])) {
a[k] = aux[j]
j += 1
} else {
a[k] = aux[i]
i += 1
}
}
}
override func sort(a: inout [Sortable]) {
aux = a
sort(a: &a, low: 0, high: a.count-1)
}
func sort(a: inout [Sortable], low: Int, high: Int) {
if high<=low {
return
}
let mid = (low+high)/2
sort(a: &a, low: low, high: mid)
sort(a: &a, low: mid+1, high: high)
merge(&a, low, mid, high)
}
}
![]()
自頂向下的歸并排序中歸并結(jié)果的軌跡
上圖是自頂向下的歸并排序中歸并結(jié)果的軌跡欣范，如果在計(jì)算機(jī)上打印每次 merge 后的數(shù)組 a，就很容易發(fā)現(xiàn)算法 1.4 的執(zhí)行順序
我們也可以通過下面的樹狀圖來理解 算法 1.4 的執(zhí)行過程
命題F：對(duì)于長度為 N 的任意數(shù)組令哟，自頂向下的歸并排序需要 1/2NlgN 至 NlgN 次比較
證明：另 C(N) 表示將一個(gè)長度為 N 的數(shù)組排序時(shí)所需要的比較次數(shù)恼琼。我們有 C(0)=C(1)=0，對(duì)于 N>0屏富，通過遞歸的 sort() 方法我們可以由相應(yīng)的歸納關(guān)系得到比較次數(shù)的上限：
C(N) <= C(?N/2?) + C(?N/2?) + N ----------(式1)
C(N) >= C(?N/2?) + C(?N/2?) + ?N/2? -----(式2)
當(dāng) N=2n 時(shí)狠半，設(shè) ?N/2?=?N/2?= 2n-1
式1變換： C(2n) = 2C(2n-1) + 2n
兩遍同時(shí)除以2n：
C(2n)/2n = C(2n-1)/2n-1+1 = C(2n-2)/2n-2+1+1 ...
最后可以得到 ：
C(2n)/2n = C(20)/20+n
C(2n) = n2n
C(N) <=lg
同理式2變換后為 C(N) >= 1/2
命題G：對(duì)于長度為 N 的任意數(shù)組噩死，自頂向下的歸并排序最多需要訪問數(shù)組 6NlgN 次
證明：每次歸并最多需要訪問數(shù)組 6N 次（2次用來復(fù)制，2N次用來將排好的元素移動(dòng)回去神年，另外最多比較 2N 次）已维，根據(jù)命題 F 即可得到這個(gè)命題結(jié)果。
命題 F 和 G 告訴我們歸并排序所需時(shí)間和 NlgN 成正比瘤袖。它的主要缺點(diǎn)是輔助數(shù)組所使用的額外空間和 N 的大小成正比衣摩。我們可以通過一些細(xì)致的思考大幅縮短歸并排序的運(yùn)行時(shí)間。
2.1 對(duì)小規(guī)模數(shù)組使用插入排序
因?yàn)檫f歸會(huì)使小規(guī)模問題中方法的調(diào)用過于頻繁捂敌，所以我們?cè)谛∫?guī)模數(shù)組時(shí)使用插入排序艾扮，會(huì)更快一些，將多么長的數(shù)組視為小規(guī)模的子數(shù)組對(duì)性能有較大影響這里我們選擇 lgN 長度的數(shù)組占婉。一般這種改進(jìn)會(huì)將運(yùn)行時(shí)間縮短 10% ~ 15%左右
class Merge<Sortable>: Sort<Sortable> where Sortable: Comparable {
var aux: [Sortable] = []
func merge(_ a: inout [Sortable], _ low: Int, _ mid: Int, _ high: Int) {
// 實(shí)現(xiàn)請(qǐng)看算法 1.4
}
override func sort(a: inout [Sortable]) {
aux = a
let k = Int(log2(Double(a.count)))+2
sort(a: &a, low: 0, high: a.count-1, k: k)
}
func sort(a: inout [Sortable], low: Int, high: Int, k: Int) {
if high<=low {
return
}
let mid = (low+high)/2
if high-low+1 < k {
insert(a: &a, low: low, high: high)
return
}
sort(a: &a, low: low, high: mid, k: k)
sort(a: &a, low: mid+1, high: high, k: k)
merge(&a, low, mid, high)
}
func insert(a: inout [Sortable], low: Int, high: Int) {
for i in (low+1)...high {
let t = a[I]
var j = I
while j > low && less(v: t, w: a[j-1]) {
a[j] = a[j-1]
j-=1
}
a[j]=t
}
}
}
我使用 50 個(gè)元素的 Int 隨機(jī)數(shù)組使用普通自頂向下的歸并排序和本節(jié)的改進(jìn)型運(yùn)行時(shí)間分別為 15.57s泡嘴、12.78s
2.2 測(cè)試數(shù)組是否已經(jīng)有序
我們可以添加一個(gè)判斷條件，如果 a[mid] 小于等于 a[mid+1]逆济，我們就認(rèn)為數(shù)組已經(jīng)是有序的并跳過 merge 方法酌予。這個(gè)改動(dòng)不影響排序的遞歸調(diào)用，但是任意有序的子數(shù)組算法的運(yùn)行時(shí)間就變?yōu)榫€性的了奖慌。
func sort(a: inout [Sortable], low: Int, high: Int, k: Int) {
if high<=low {
return
}
let mid = (low+high)/2
if high-low+1 < k {
insert(a: &a, low: low, high: high)
return
}
sort(a: &a, low: low, high: mid, k: k)
sort(a: &a, low: mid+1, high: high, k: k)
if a[mid] <= a[mid+1] {
return
}
merge(&a, low, mid, high)
}
加了判斷后對(duì)于隨機(jī)的大數(shù)組排序時(shí)間并不會(huì)有所縮短抛虫，但是如果數(shù)組本身接近有序，會(huì)大大縮短排序時(shí)間
2.3 不將元素復(fù)制到輔助數(shù)組
我們可以節(jié)省將數(shù)組元素復(fù)制到用于歸并的輔助數(shù)組所用的時(shí)間（但空間不行）简僧。要做到這一點(diǎn)我們要調(diào)用兩種排序方法建椰，一種將數(shù)據(jù)從輸入數(shù)組排序到輔助數(shù)組，一種將數(shù)據(jù)從輔助數(shù)組排序到輸入數(shù)組岛马。這種方法需要一些技巧棉姐，我們要在遞歸調(diào)用的每個(gè)層次交換輸入數(shù)組和輔助數(shù)組的角色屠列。
3. 自底向上的歸并排序
override func sort(a: inout [Sortable]) {
aux = a
let N = a.count
var sz = 1
while sz < N {
var lo = 0
while lo < N-sz {
merge(&a, &aux, lo, lo+sz-1, min(lo+2*sz-1, N-1))
lo += 2*sz
}
sz *= 2
}
}
三、快速排序
快速排序引人注目的特點(diǎn)包括它是原地排序（只需要一個(gè)很小的輔助棧）伞矩，且將長度為 N 的數(shù)組排序所需要的時(shí)間和 NlgN 成正比笛洛。另外快速排序的內(nèi)循環(huán)幣大多數(shù)排序算法都要小，這意味著它無論是理論上還是在實(shí)際中都要更快乃坤。它的主要缺點(diǎn)是非常脆弱苛让，在實(shí)現(xiàn)時(shí)要非常小心才能避免低劣的性能。已經(jīng)有無數(shù)例子顯示許多錯(cuò)誤都能致使它在實(shí)際中的性能只能有平方級(jí)侥袜。
1. 基本算法
快速排序是一種分治的排序算法蝌诡。它將一個(gè)數(shù)組分成兩個(gè)子數(shù)組，將兩部分獨(dú)立排序枫吧∑趾担快速排序和歸并排序是互補(bǔ)的：快速排序?qū)?shù)組排序的方式則是當(dāng)兩個(gè)子數(shù)組都有序時(shí)整個(gè)數(shù)組頁就自然有序了。在快速排序中切分的位置取決于數(shù)組的內(nèi)容九杂。大致過程如下：
![]()
快速排序示意圖
算法 1.5
class Quick<Sortable>: Sort<Sortable> where Sortable: Comparable {
override func sort(a: inout [Sortable]) {
a.shuffle()
sort(a: &a, low: 0, high: a.count-1)
}
func sort(a: inout [Sortable], low: Int, high: Int) {
if high <= low {
return
}
let j = partition(a: &a, low: low, high: high)
sort(a: &a, low: low, high: j-1)
sort(a: &a, low: j+1, high: high)
}
func partition(a: inout [Sortable], low: Int, high: Int) -> Int {
var i = low
var j = high+1
let v = a[low]
while true {
repeat {
i += 1
if i == high {
break
}
} while less(v: a[i], w: v)
repeat {
j -= 1
if j == low {
break
}
} while less(v: v, w: a[j])
if i >= j {
break
}
exch(a: &a, i: i, j: j)
}
exch(a: &a, i: low, j: j)
return j
}
}
快速排序遞歸地將子數(shù)組 a[low...high] 排序颁湖，先用 partition() 方法將 a[j] 放到一個(gè)合適的位置，然后遞歸調(diào)用將其他位置的元素排序例隆。
partition() 的作用：從左到右找到一個(gè)大于 a[low] 的元素和從右往左找到的一個(gè)小于 a[low] 的元素交換甥捺，直到左邊大于等于右邊，然后將第 low 個(gè)元素放到適當(dāng)位置镀层，并返回這個(gè)位置
- 對(duì)于某個(gè) j镰禾，a[j] 已經(jīng)排定；
- a[low] 到 a[j-1] 中所有元素都不大于 a[j]唱逢；
- a[j+1] 到 a[high] 中所有元素都不小于 a[j]吴侦。
它是一個(gè)隨機(jī)化的算法，因?yàn)樗趯?shù)組排序之前將其隨機(jī)打亂坞古。我們這么做的原因是希望能夠預(yù)測(cè)（并依賴）該算法的性能特性备韧。
![]()
快速排序的切分示意圖
![]()
切分軌跡
下面是幾個(gè)細(xì)節(jié)問題，它們都可能導(dǎo)致實(shí)現(xiàn)錯(cuò)誤或者影響性能
1痪枫、原地切分：如果使用一個(gè)輔助數(shù)組织堂，很容易實(shí)現(xiàn)切分，但將切分后的數(shù)組復(fù)制回去的開銷也許會(huì)使我們得不償失奶陈。
2易阳、別越界：如果切分元素是數(shù)組中最小或者最大的那個(gè)元素，我們就要小心別讓掃描指針跑出數(shù)組邊界
3吃粒、保持隨機(jī)性：數(shù)組元素的順序是被打亂過的潦俺。因?yàn)樗惴?1.5 對(duì)所有的子數(shù)組都一視同仁，它的所有子數(shù)組頁都是隨機(jī)排序的。這對(duì)于預(yù)測(cè)算法的運(yùn)行時(shí)間很重要黑竞。保持隨機(jī)性的另一種方法是在 partition() 中隨機(jī)選擇一個(gè)切分元素。
4疏旨、終止循環(huán)：正確的檢測(cè)指針是否越界需要一點(diǎn)技巧很魂。一個(gè)最常見的錯(cuò)誤是沒有考慮到數(shù)組中可能包含和切分元素值相同的其他元素。
5檐涝、處理切分元素值有重復(fù)的情況：如算法 1.5 所示遏匆，左側(cè)掃描最好是在遇到大于等于切分元素時(shí)停下，右側(cè)則是在小于等于切分元素時(shí)停下谁榜。盡管這樣可能會(huì)不必要的將一些等值進(jìn)行交換幅聘，但在某些典型應(yīng)用中，它能夠避免算法的運(yùn)行時(shí)間變?yōu)槠椒郊?jí)窃植。
6帝蒿、終止遞歸：實(shí)現(xiàn)快速排序時(shí)一個(gè)常見的錯(cuò)誤就是不能保證切分元素放入正確的位置，從而導(dǎo)致程序在切分元素正好是子數(shù)組的最大或者最小元素時(shí)陷入無限循環(huán)之中巷怜。
2. 性能特點(diǎn)
快速排序切分方法的內(nèi)循環(huán)會(huì)用一個(gè)遞增的索引將數(shù)組元素和一個(gè)定值比較葛超。這種簡(jiǎn)潔性也是快速排序的一個(gè)優(yōu)點(diǎn)，很難想象排序算法還能有比這更短小的內(nèi)循環(huán)了延塑。例如绣张，歸并排序和希爾排序一般都比快速排序慢，其原因就是它們?cè)趦?nèi)循環(huán)中移動(dòng)數(shù)據(jù)关带。
快速排序另一個(gè)優(yōu)勢(shì)在于它的比較次數(shù)很少侥涵。排序效率最終還是依賴切分?jǐn)?shù)組的效果，而這依賴于切分元素的值宋雏。切分將一個(gè)較大的隨機(jī)數(shù)組分成兩個(gè)隨機(jī)子數(shù)組芜飘，而實(shí)際上這種分割可能發(fā)生在數(shù)組的任意位置(對(duì)于元素不重復(fù)的數(shù)組而言)。下面我們分享這個(gè)算法和理想方法之間的差距
快速排序的最好情況是每次都正好將數(shù)組對(duì)半分
命題K：將長度為 N 的無重復(fù)數(shù)組排序好芭，快速排序平均需要 ≈ 2NlnN ≈ 1.39NlgN次比較（以及 1/6 的交換）燃箭。
也就是說平均比較次數(shù)只比最好情況多 39%
命題L：快速排序最多需要 N2/2 次比較，但隨機(jī)打亂數(shù)組能夠預(yù)防這種情況舍败。
3. 算法改進(jìn)
幾乎從 Hoare 第一次發(fā)表這個(gè)算法開始招狸，人們就不斷提出各種改進(jìn)方法。并不是所有的想法都可行邻薯，因?yàn)榭焖倥判虻钠胶庑砸呀?jīng)非常好裙戏，改進(jìn)所帶來的提高可能會(huì)被意外的副作用所抵消。但其中一些厕诡，非常有效累榜。
你需要通過實(shí)驗(yàn)來確定改進(jìn)的效果并為實(shí)現(xiàn)選擇最佳參數(shù)。一般來說性能能提升 20% ~ 30%
3.1 切換到插入排序
和大多數(shù)遞歸排序算法一樣，對(duì)于小數(shù)組壹罚，快速排序比插入排序慢葛作。因?yàn)檫f歸，快速排序的 sort() 方法在小數(shù)組中也會(huì)調(diào)用自己猖凛。
3.2 三取樣切分
改進(jìn)快速排序性能的第二個(gè)辦法是使用子數(shù)組的一小部分元素的中位數(shù)來切分?jǐn)?shù)組赂蠢。這樣做得到的切分更好，但代價(jià)需要計(jì)算中位數(shù)辨泳。人們發(fā)現(xiàn)取樣大小設(shè)為 3 并用大小居中的元素切分的效果最好虱岂。
3.3 熵最優(yōu)的排序
實(shí)際應(yīng)用中經(jīng)常會(huì)出現(xiàn)含有大量重復(fù)元素的數(shù)組，例如將大量人員資料按照生日或者性別排序菠红，在這些情況下第岖，我們實(shí)現(xiàn)的快速排序的性能尚可，但還有巨大的改進(jìn)空間试溯。例如蔑滓，在有大量重復(fù)元素的情況下，快速排序的遞歸性能會(huì)使元素全部重復(fù)的子數(shù)組經(jīng)常出現(xiàn)遇绞，這就有很大改進(jìn)潛力烫饼。
一個(gè)簡(jiǎn)單的想法是將數(shù)組切分為三個(gè)部分，分別對(duì)應(yīng)小于试读，等于和大于切分元素的數(shù)組元素杠纵。這種切分實(shí)現(xiàn)起來比我們目前使用的二分法更復(fù)雜。
四钩骇、優(yōu)先隊(duì)列
許多應(yīng)用程序都需要處理有序元素比藻，但不一定要求它們?nèi)坑行颍蚴遣灰欢ㄒ淮尉蛯⑺鼈兣判蛱纫佟：芏嗲闆r下我們會(huì)手機(jī)一些元素银亲，處理當(dāng)前鍵值最大的元素，然后再收集更多的元素纽匙，再處理當(dāng)前鍵值最大的元素务蝠，如此這般。例如烛缔，你有可能有一臺(tái)能夠同時(shí)運(yùn)行多個(gè)應(yīng)用程序的電腦（或者手機(jī)）。這是通過為每個(gè)應(yīng)用程序的事件分配一個(gè)優(yōu)先級(jí)践瓷，并總是處理下一個(gè)優(yōu)先級(jí)最高的事件來實(shí)現(xiàn)的院喜。例如，絕大多數(shù)手機(jī)分配給來點(diǎn)的優(yōu)先級(jí)都會(huì)比游戲程序的高晕翠。
在這種情況下喷舀，一個(gè)合適的數(shù)據(jù)結(jié)構(gòu)應(yīng)該支持兩種操作：刪除最大元素和插入元素。這種數(shù)據(jù)類型叫做優(yōu)先隊(duì)列。優(yōu)先隊(duì)列的使用和隊(duì)列（刪除最老的元素）以及棧（刪除最新的的元素）類似硫麻，但高校的實(shí)現(xiàn)它則更具挑戰(zhàn)性爸邢。
這里簡(jiǎn)單討論優(yōu)先隊(duì)列的基本表現(xiàn)形式（其一或者兩種操作都能在線性時(shí)間內(nèi)完成）之后，我們會(huì)學(xué)習(xí)基于二叉堆數(shù)據(jù)結(jié)構(gòu)的一種優(yōu)先隊(duì)列的經(jīng)典實(shí)現(xiàn)方法拿愧，用數(shù)組保存元素并按照一定條件排序甲棍，以實(shí)現(xiàn)高效的（對(duì)數(shù)級(jí)別的）刪除最大元素和插入元素操作。
優(yōu)先隊(duì)列的一些重要的應(yīng)用場(chǎng)景包括模擬系統(tǒng)赶掖，其中事件的鍵即為發(fā)生的時(shí)間，而系統(tǒng)需要按照時(shí)間順序處理所有事件七扰；任務(wù)調(diào)度奢赂，其中鍵值對(duì)應(yīng)的優(yōu)先級(jí)決定了應(yīng)該首先執(zhí)行哪些任務(wù)；數(shù)值計(jì)算颈走，鍵值代表計(jì)算錯(cuò)誤膳灶，而我們需要按照鍵值指定的順序來修正它們。
通過插入一列元素然后一個(gè)個(gè)地刪掉其中最小的元素立由，我們可以用優(yōu)先隊(duì)列實(shí)現(xiàn)排序算法轧钓。一種名為堆排序的重要排序算法也來自于基于堆的優(yōu)先隊(duì)列的實(shí)現(xiàn)。
1. API
優(yōu)先隊(duì)列是一種抽象數(shù)據(jù)類型锐膜，它表示一組值和對(duì)這些值的操作毕箍，它的抽象層使我們能夠方便地將應(yīng)用程序和我們將學(xué)習(xí)的各種具體實(shí)現(xiàn)隔離開來。我們會(huì)詳細(xì)定義一組應(yīng)用程序編程接口（API）來為數(shù)據(jù)結(jié)構(gòu)的用例提供足夠的信息道盏。優(yōu)先隊(duì)列最重要的操作就是刪除最大元素和插入元素而柑，所有我們會(huì)把精力集中在它們身上。和排序算法一樣荷逞。如果允許重復(fù)元素媒咳，最大表示的是所有最大元素之一。為了將 API 定義完整种远，我們還需要加入構(gòu)造函數(shù)（和我們?cè)跅Ｒ约瓣?duì)列中使用的類似）和一個(gè)空隊(duì)列測(cè)試方法涩澡。
1.1、優(yōu)先隊(duì)列的調(diào)用示例
為了展示優(yōu)先隊(duì)列的抽象模型的價(jià)值坠敷，考慮以下問題：輸入 N 個(gè)字符串妙同，每個(gè)字符串都對(duì)應(yīng)著一個(gè)整數(shù)，你的任務(wù)就是從中找出最大的（或是最小的）M 個(gè)整數(shù)（及其關(guān)聯(lián)的字符串）膝迎。這些輸入可能是金融事務(wù)渐溶，你需要從中找出最大的那些；或是農(nóng)產(chǎn)品殺蟲劑含量弄抬，這時(shí)你需要從中找到最小的那些茎辐；或是服務(wù)請(qǐng)求、科學(xué)實(shí)驗(yàn)的結(jié)果，或是其他應(yīng)用拖陆。在某些應(yīng)用場(chǎng)景中弛槐，輸入量可能非常巨大，甚至可以認(rèn)為輸入是無限的依啰。解決這個(gè)問題的一種方法是將輸入排序然后從中找出 M 個(gè)最大的元素乎串，但我們已經(jīng)說明輸入將會(huì)非常龐大。另一種方法是將每個(gè)新的輸入和已知的 M 個(gè)最大元素比較速警，但除非 M 較小叹誉，否則這種比較的代價(jià)會(huì)非常高昂。
| 示例 | 時(shí)間 | 空間 |
|---|---|---|
| 排序算法的用例 | NlogN | N |
| 初級(jí)實(shí)現(xiàn)的優(yōu)先隊(duì)列 | NM | M |
| 基于堆實(shí)現(xiàn)的優(yōu)先隊(duì)列 | NlogM | M |
2. 初級(jí)實(shí)現(xiàn)
2.1 數(shù)組實(shí)現(xiàn)（無序）
或許實(shí)現(xiàn)優(yōu)先隊(duì)列的最簡(jiǎn)單方法就是基于 (一) 中的下壓棧代碼闷旧。insert() 方法的代碼和棧的 push() 方法完全一樣长豁。要實(shí)現(xiàn)刪除最大元素，我們可以添加一段類似于選擇排序的內(nèi)循環(huán)的代碼忙灼，將最大元素和邊界元素交換然后刪除它匠襟，和我們對(duì)棧的 pop() 方法的實(shí)現(xiàn)一樣。和棧類似该园，我們也可以加入調(diào)整數(shù)組大小的代碼來保證數(shù)據(jù)結(jié)構(gòu)至少含有四分之一的元素而又永遠(yuǎn)不會(huì)溢出酸舍。
2.2 數(shù)組實(shí)現(xiàn) （有序）
另一種方法就是在 insert() 方法中添加代碼，將所有較大的元素向右移動(dòng)一格以使數(shù)組保持有序（和插入排序一樣）里初。這樣最大的元素總會(huì)在數(shù)組的一邊啃勉，優(yōu)先隊(duì)列刪除最大元素操作就和棧的 pop() 操作一樣了。
2.3 鏈表表示法
和剛才類似双妨，我們可以基于鏈表的下壓棧的代碼作為基礎(chǔ)璧亮，然后可以選擇修改 pop() 來找到并返回最大元素，或是修改 push() 來保證所有元素為逆序并用 pop() 來刪除并返回鏈表的首元素（也就是最大的元素）
使用無序序列是解決這個(gè)問題的惰性方法斥难，我們僅在必要的時(shí)候才會(huì)采取行動(dòng)枝嘶；使用有序序列則是解決問題的積極方法，因?yàn)槲覀儠?huì)盡可能未雨綢繆（在插入元素時(shí)就保持列表有序）哑诊，使后續(xù)操作更高效群扶。
實(shí)現(xiàn)棧或者是隊(duì)列與實(shí)現(xiàn)優(yōu)先隊(duì)列的最大不同在于對(duì)性能的要求镀裤。對(duì)于棧和隊(duì)列竞阐，我們的實(shí)現(xiàn)能夠在常數(shù)時(shí)間內(nèi)完成所有操作；而對(duì)于優(yōu)先隊(duì)列暑劝，我們剛才討論的所有初級(jí)實(shí)現(xiàn)中骆莹，插入元素和刪除最大元素這兩個(gè)操作之一在最壞情況下需要線性時(shí)間來完成。我們接下來要討論的基于數(shù)據(jù)結(jié)構(gòu)堆的實(shí)現(xiàn)能夠保證這種操作都能更快的執(zhí)行担猛。
| 數(shù)據(jù)結(jié)構(gòu) | 插入元素 | 刪除最大元素 |
|---|---|---|
| 有序數(shù)組 | N | 1 |
| 無序數(shù)組 | 1 | N |
| 堆 | logN | logN |
| 理想情況 | 1 | 1 |
3. 堆的定義
數(shù)據(jù)結(jié)構(gòu)二叉堆能夠很好的實(shí)現(xiàn)優(yōu)先隊(duì)列的基本操作幕垦。在二叉堆的數(shù)組中丢氢，每個(gè)元素都要保證大于等于另兩個(gè)特定位置的元素。相應(yīng)的先改，這些位置的元素又至少要大于等于數(shù)組中的另兩個(gè)元素疚察，以此類推。如果我們將所有元素畫成一棵二叉樹仇奶，將每個(gè)較大元素和兩個(gè)較小元素用邊連接就可以很容易看出這種結(jié)構(gòu)
定義：當(dāng)一棵二叉樹的每個(gè)結(jié)點(diǎn)都大于等于它的兩個(gè)子節(jié)點(diǎn)時(shí)貌嫡，它被稱為堆有序。
相應(yīng)地该溯，在堆有序的二叉樹中岛抄，每個(gè)結(jié)點(diǎn)都小于等于它的父結(jié)點(diǎn)（如果有的話）。從任意結(jié)點(diǎn)向上狈茉，我們都能夠得到一列非遞減的元素夫椭；從任意結(jié)點(diǎn)向下。我們都能得到一列非遞增的元素论皆。特別的：
命題O：根節(jié)點(diǎn)是堆有序二叉樹的最大結(jié)點(diǎn)。
3.1 二叉堆表示法
![]()
一棵堆有序的完全二叉樹
如果我們用指針來表示堆有序的二叉樹猾漫，那么每個(gè)元素都需要三個(gè)指針來找到它的上下結(jié)點(diǎn)（父結(jié)點(diǎn)和兩個(gè)子結(jié)點(diǎn)各需要一個(gè)）点晴。但如上圖所示，如果我們使用完全二叉樹悯周，表達(dá)就會(huì)變得特別方便粒督。要畫出這樣一顆完全二叉樹，可以先定下根節(jié)點(diǎn)禽翼，然后一層一層的由上向下屠橄、從左至右，在每個(gè)結(jié)點(diǎn)的下方連接兩個(gè)更小的結(jié)點(diǎn)闰挡，直至將 N 個(gè)結(jié)點(diǎn)全部連接完畢锐墙。完全二叉樹只用數(shù)組而不需要指針就可以表示。具體方法就是將二叉樹的結(jié)點(diǎn)按照層級(jí)順序放入數(shù)組中长酗，根結(jié)點(diǎn)的位置 1溪北，它的子節(jié)點(diǎn)的位置 2 和 3，而子結(jié)點(diǎn)的子結(jié)點(diǎn)則分別在 4夺脾、5之拨、6 和 7，以此類推咧叭。
定義：二叉堆是一組能夠用堆有序的完全二叉樹排序的元素蚀乔，并在數(shù)組中按照層級(jí)存儲(chǔ)（不使用數(shù)組的第一個(gè)位置）。
（在下文中我們將二叉堆簡(jiǎn)稱為堆）在一個(gè)堆中菲茬，位置 k 的結(jié)點(diǎn)的父結(jié)點(diǎn)的位置為?k/2?吉挣，而它的兩個(gè)子結(jié)點(diǎn)的位置則分別為 2k 和 2k+1派撕。
用數(shù)組（堆）實(shí)現(xiàn)的完全二叉樹的結(jié)構(gòu)是很嚴(yán)格的，但它的靈活性已經(jīng)足以讓我們高效的實(shí)現(xiàn)優(yōu)先隊(duì)列听想。用它們將能實(shí)現(xiàn)對(duì)數(shù)級(jí)別的插入元素和刪除元素操作腥刹。利用在數(shù)組中無需指針即可沿樹上下移動(dòng)的便利和以下性質(zhì)，算法保證了對(duì)數(shù)復(fù)雜度的性能汉买。
命題P：一棵大小為 N 的完全二叉樹的高度為 ?lgN?
![]()
堆的表示
4. 堆的算法
我們會(huì)使用更加緊湊的實(shí)現(xiàn)方式衔峰，不再將數(shù)組作為參數(shù)傳遞壹甥。堆的操作會(huì)首先進(jìn)行一些簡(jiǎn)單的改動(dòng)笛钝，打破堆的狀態(tài)，然后再遍歷堆并按照要求將堆的狀態(tài)恢復(fù)肝谭。我們稱這個(gè)過程叫做堆的有序化出牧。
在有序化的過程中會(huì)有兩種情況穴肘。當(dāng)某個(gè)結(jié)點(diǎn)的優(yōu)先級(jí)上升（或是在堆底加入一個(gè)新的元素）時(shí)，需要由下至上恢復(fù)堆的順序舔痕。當(dāng)某個(gè)結(jié)點(diǎn)的優(yōu)先級(jí)下降（例如评抚，將根節(jié)點(diǎn)替換為一個(gè)較小的元素）時(shí)，我們需要由上至下恢復(fù)堆的順序伯复。首先慨代，我們會(huì)學(xué)習(xí)如何實(shí)現(xiàn)這兩種輔助操作，然后再用它們實(shí)現(xiàn)插入元素和刪除最大元素的操作啸如。
4.1 由下至上的堆有序化（上甘坛住）
private func swim(_ k: Int) {
var i = k
while i > 1 && less(i/2, i) {
exch(i/2, i)
i = I/2
}
}
如果堆有序的狀態(tài)因?yàn)槟硞€(gè)結(jié)點(diǎn)變得比它的父結(jié)點(diǎn)更大而被打破，就是原本的堆數(shù)組是堆有序的叮雳，但是 k 點(diǎn)的值變得比父結(jié)點(diǎn)大了想暗，那么就用上面的方法進(jìn)行上浮操作后，堆就會(huì)再次變得有序帘不，上浮過程如下圖
![]()
由下至上的堆有序化（上杆的）
4.2 由上至下的堆有序化（下沉）
private func sink(_ k: Int) {
var i = k
while i*2 <= N {
var j = 2*I
if j < N && less(j, j+1) {
j = j+1
}
if !less(i, j) {
break
}
exch(i, j)
i = j
}
}
如果堆的有序狀態(tài)因?yàn)槟硞€(gè)結(jié)點(diǎn)變得比它的兩個(gè)子節(jié)點(diǎn)或者是其中之一更小了而被打破，那么可以通過將它的兩個(gè)子結(jié)點(diǎn)中的較大者交換來恢復(fù)堆寞焙。就是原本的堆數(shù)組是堆有序的唬滑，但是 k 點(diǎn)的值變得比子結(jié)點(diǎn)小了，那么就用上面的方法進(jìn)行下沉操作后棺弊，堆就會(huì)再次變得有序晶密，下沉過程如下圖：
![]()
由上至下的堆有序化（下沉）
sink() 和 swim() 方法是高效實(shí)現(xiàn)優(yōu)先隊(duì)列 API 的基礎(chǔ)，原因如下
插入元素：我們將新元素加到數(shù)組末尾模她，增加堆的大小并讓這個(gè)新元素上浮到合適的位置
刪除最大元素：我們從數(shù)組頂端刪去最大的元素并將數(shù)組的最后一個(gè)元素放到頂端稻艰，減小堆的大小并讓這個(gè)元素下沉到合適的位置。
算法 1.6 解決了我們?cè)诒竟?jié)開始時(shí)提出的一個(gè)基本問題：它對(duì)優(yōu)先隊(duì)列 API 的實(shí)現(xiàn)能夠保證插入元素和刪除最大元素這兩個(gè)操作的用時(shí)和隊(duì)列的大小僅成對(duì)數(shù)關(guān)系侈净。
算法 1.6
class MaxPQ<Element> where Element: Comparable {
private var pq: [Element?] = [nil];
private var N: Int {
return pq.count-1;
}
private var maxN: Int = 0
init(_ maxN: Int) {
self.maxN = maxN
}
func insert(_ v: Element) {
if N == maxN {
return
}
pq.append(v)
swim(N)
}
func max() -> Element? {
if isEmpty {
return nil
}
return pq[1]
}
func delMax() -> Element? {
if isEmpty {
return nil
}
let max = pq[1]
exch(1, N);
pq.removeLast()
sink(1)
return max
}
var isEmpty: Bool {
return N == 0
}
var size: Int {
return N
}
private func swim(_ k: Int) {
var i = k
while i > 1 && less(i/2, i) {
exch(i/2, i)
i = I/2
}
}
private func sink(_ k: Int) {
var i = k
while i*2 <= N {
var j = 2*I
if j < N && less(j, j+1) {
j = j+1
}
if !less(i, j) {
break
}
exch(i, j)
i = j
}
}
private func exch(_ i: Int, _ j: Int) {
let t = pq[i]
pq[i] = pq[j]
pq[j] = t
}
private func less(_ i: Int, _ j: Int) -> Bool {
return pq[i]! < pq[j]!
}
}
![]()
堆的操作
命題Q：對(duì)于一個(gè)含有 N 個(gè)元素的基于堆的優(yōu)先隊(duì)列尊勿，插入元素操作只需要不超過 lgN+1 次比較僧凤，刪除最大元素的操作需要不超過 2lgN 次比較
使用有序或是無序數(shù)組的優(yōu)先隊(duì)列的初級(jí)實(shí)現(xiàn)總是需要線性時(shí)間來完成其中一種操作，但基于堆的實(shí)現(xiàn)能夠保證在對(duì)數(shù)時(shí)間內(nèi)完成它們元扔。這種差別使得我們能夠解決以前無法解決的問題
4.3 多叉堆
基于用數(shù)組表示的完全三叉數(shù)結(jié)構(gòu)堆并修改相應(yīng)的代碼并不困難躯保。對(duì)于數(shù)組中 1 至 N 的 N 個(gè)元素，位置 k 的結(jié)點(diǎn)大于等于位于 3k-1澎语、3k 和 3k+1 的結(jié)點(diǎn)途事，小于等于位于?(k+1)/3? 的結(jié)點(diǎn)。甚至對(duì)于給定的 d擅羞，將其修改為任意的 d 叉樹也不困難尸变。我們需要在樹高（logdN）和在每個(gè)結(jié)點(diǎn)的 d 個(gè)子結(jié)點(diǎn)找到最大者的代價(jià)之間找到折中，這取決于實(shí)現(xiàn)的細(xì)節(jié)以及不同操作的預(yù)期相對(duì)頻繁程度减俏。
4.4 調(diào)整數(shù)組大小
我們可以添加一個(gè)沒有參數(shù)的構(gòu)造函數(shù)召烂，在 insert() 中添加將數(shù)組長度加倍的代碼，在 delMax() 中添加將數(shù)組長度減半的代碼娃承，這樣奏夫，算法的用例就無須關(guān)注各種隊(duì)列大小的限制。當(dāng)優(yōu)先隊(duì)列的數(shù)組大小可以調(diào)整历筝、隊(duì)列長度可以是任意值時(shí)酗昼，命題 Q 指出的對(duì)數(shù)時(shí)間復(fù)雜度上限就是針對(duì)一般性的隊(duì)列長度 N 而言了
4.5 元素的不可變性
優(yōu)先隊(duì)列存儲(chǔ)了用例創(chuàng)建的對(duì)象，但同時(shí)假設(shè)用例代碼不會(huì)改變它們（改變它們就可能打破堆的有序性）漫谷。我們可以將這個(gè)假設(shè)轉(zhuǎn)化為強(qiáng)制條件仔雷，但程序員通常不會(huì)這么做蹂析，因?yàn)樵黾哟a的復(fù)雜性會(huì)降低性能舔示。
4.6 索引優(yōu)先隊(duì)列
在很多應(yīng)用中，允許用例引用已經(jīng)進(jìn)入優(yōu)先隊(duì)列中的元素是必要的电抚。做到這一點(diǎn)的一種簡(jiǎn)單方法是給每個(gè)元素一個(gè)索引惕稻。另外，一種常見的情況是用例已經(jīng)有了總量為 N 的多個(gè)元素蝙叛，而且可能還同時(shí)使用了多個(gè)（平行）數(shù)組來存儲(chǔ)這些元素的信息俺祠。此時(shí)，其他無關(guān)的用例代碼可能已經(jīng)在使用一個(gè)整數(shù)索引來引用這些元素了借帘。
| IndexMinPQ 的屬性和方法 | 意義 |
|---|---|
| init(maxN: Int) | 創(chuàng)建一個(gè)最大容量為 maxN 的優(yōu)先隊(duì)列蜘渣， 索引取值范圍為 0 至 maxN-1 |
| insert(k: Int, item: Item) | 插入一個(gè)元素，將它和索引 k 相關(guān)聯(lián) |
| change(k: Int, item: Item) | 將索引為 k 的元素設(shè)為 item |
| contains(k: Int)->Bool | 是否存在索引為 k 的元素 |
| delete(k: Int) | 刪去索引 k 及其相關(guān)聯(lián)的元素 |
| min()->Item? | 返回最小元素 |
| minIndex()->Int? | 返回最小元素的索引 |
| delMin()->Int? | 刪除最小元素肺然，并返回它的索引 |
| isEmpty()->Bool | 優(yōu)先隊(duì)列是否為空 |
| size()->Int | 優(yōu)先隊(duì)列中的元素?cái)?shù)量 |
理解這種數(shù)據(jù)結(jié)構(gòu)的一個(gè)較好方法是將它看成一個(gè)能夠快速訪問其中最小元素的數(shù)組蔫缸。事實(shí)上它還要更好——它能夠快速訪問數(shù)組的一個(gè)特定子集中的最小元素（指所有被插入的元素）。換句話說际起，可以將名為 pq 的 IndexMinPQ 類優(yōu)先隊(duì)列看做數(shù)組 pq[0...N-1] 中的一部分元素的代表拾碌。將qp.insert(k, item) 看做將 k 加入這個(gè)子集并使 pq[k] = item吐葱，qp.change(k, item) 則代表令 pq[k] = item。這兩種操作沒有改變其他操作所依賴的數(shù)據(jù)結(jié)構(gòu)校翔，其中最重要的就是 delMin() 和 change() 這些操作在許多應(yīng)用中都很重要并且依賴于元素的引用弟跑。
命題Q（續(xù)）：在一個(gè)大小為 N 的索引優(yōu)先隊(duì)列中，插入元素防症、改變優(yōu)先級(jí)孟辑、刪除和刪除最小元素操作所需的比較次數(shù)和 logN 成正比
| 操作 | 比較次數(shù)的增長數(shù)量級(jí) |
|---|---|
| insert() | logN |
| change() | logN |
| contains() | 1 |
| delete() | logN |
| min() | 1 |
| minIndex() | 1 |
| delMin() | logN |
4.7 索引優(yōu)先隊(duì)列的用例
下面的用例調(diào)用了 IndexMinPQ 的代碼 Multiway 解決了多項(xiàng)歸并問題：它將多個(gè)有序的輸入流歸并成一個(gè)有序的輸出流。許多應(yīng)用中都會(huì)遇到這個(gè)問題告希。輸入可能來自于多種科學(xué)儀器的輸出扑浸，或是來自多個(gè)音樂或電影網(wǎng)站的信息列表，或是商業(yè)交易等燕偶。如果有足夠的空間喝噪，你可以把它們簡(jiǎn)單地讀入一個(gè)數(shù)組并排序，但如果用了優(yōu)先隊(duì)列指么，無論輸入有多長你都可以把它們?nèi)孔x入并排序
5. 堆排序
我們可以把任意優(yōu)先隊(duì)列變成一種排序方法酝惧。將所有元素插入一個(gè)查找最小元素的優(yōu)先隊(duì)列，然后再重復(fù)調(diào)用刪除最小元素的操作用來將它們按順序刪去伯诬。用無序數(shù)組實(shí)現(xiàn)的優(yōu)先隊(duì)列這么做相當(dāng)于進(jìn)行一次插入排序晚唇。用基于堆的優(yōu)先隊(duì)列這樣做等同于那種排序？一種全新的排序方法盗似！下面我們用堆實(shí)現(xiàn)一種經(jīng)典而優(yōu)雅的排序算法——堆排序
堆排序可以分為兩個(gè)階段哩陕。在堆的構(gòu)造階段，我們將原始數(shù)組重新組織安排進(jìn)一個(gè)堆中赫舒；然后在下沉排序階段悍及，我們從堆中按遞減順序取出所有元素并得到排序結(jié)果。
lass PQSort<Sortable>: Sort<Sortable> where Sortable: Comparable {
override func sort(a: inout [Sortable]) {
let pq = MinPQ<Sortable>(a.count)
for v in a {
pq.insert(v)
}
var i = 0
while pq.N > 0 {
a[i] = pq.delMin()!
i += 1
}
}
}
class MinPQ<Element> where Element: Comparable {
private var pq: [Element?] = [nil];
var N: Int {
return pq.count-1;
}
private var maxN: Int = 0
init(_ maxN: Int) {
self.maxN = maxN
}
func insert(_ v: Element) {
pq.append(v)
swim(N)
}
func delMin() -> Element? {
let min = pq[1]
exch(1, N);
pq.remove(at: N)
sink(1)
return min
}
private func swim(_ k: Int) {
var i = k
while i > 1 && less(i, i/2) {
exch(i/2, i)
i = i/2
}
}
private func sink(_ k: Int) {
var i = k
while i*2 <= N {
var j = 2*i
if j < N && less(j+1, j) {
j = j+1
}
if less(i, j) {
break
}
exch(i, j)
i = j
}
}
private func exch(_ i: Int, _ j: Int) {
let t = pq[i]
pq[i] = pq[j]
pq[j] = t
}
private func less(_ i: Int, _ j: Int) -> Bool {
return pq[i]! < pq[j]!
}
}
命題S：將 N 個(gè)元素排序接癌，堆排序只需要少于（2NlgN + 2N）次比較（以及一半次數(shù)的交換）
