§06 排序算法
堆排序
先建大根堆（父节点不小于孩子），再反复把堆顶与堆末尾交换，每轮确定一个最大值就位。 就地排序，时间复杂度稳定 O(n log n)。观察 partition 堆范围如何从右向左收缩。
堆排序
伪代码
1
procedure siftDown(a, i, n)
2
while 2*i + 1 < n do
3
j = 2*i + 1 // 左孩子
4
if j + 1 < n and a[j+1] > a[j] then
5
j = j + 1 // 取较大的孩子
6
end if
7
if a[i] >= a[j] then break
8
swap(a[i], a[j]) // 下滤
9
i = j
10
end while
11
end procedure
12
13
procedure heapSort(a, n)
14
for i = n/2 - 1 downto 0 do // 建堆
15
siftDown(a, i, n)
16
end for
17
for end = n - 1 downto 1 do // 排序
18
swap(a[0], a[end]) // 堆顶就位
19
siftDown(a, 0, end)
20
end for
21
end procedure