堆排序
A.length 是数组的长度，也就是上界
A.heap-size 是有效的对元素的最后一个元素的位置，MAX-HEAPIFY要判断左孩子和右孩子是否越界

维护堆的性质
维护堆的性质，数组A和下标i
MAX-HEAPIFY(A, i)
l=LEFT(i) 左孩子
r=RIGHT(i) 右孩子
if l < A.heap-size && A[l] > A[i]
largest = l
else
largest = i
if r < A.heap-size && A[r] > A[i]
largest = r
else
largest = i
if largest != i
exchange A[largest] and A[i]
MAX-HEAPIFY(A, largest)

建堆
BUILD-MAX-HEAP(A)
A.heap-size = A.length

for i = [A.length/2]取下界 downto 1
MAX-HEAPIFY(A, i)

时间复杂度nlg(n), 紧确界为O(n)

时间复杂度推导公式
预备知识

对于任何包含n个元素的堆，高度为h的节点至多有[n/2^(h+1)]（取上界）个
堆排序
HEAPSORT(A)
BUILD-MAX-HEAP(A)
for i=A.length downto 2
exchange A[1] with A[i]
A.heap-size = A.heap-size - 1
MAX-HEAPIFY(A,1)

ps. 以上1为第一个元素，下标从1开始
时间复杂度为O(n lg(n))

优先队列
分为最大优先队列和最小优先队列
下面以最大优先队列为例
支持四种操作操作如下
四种操作

HEAP-MAXIMUM(A)
return A[1]
时间复杂度是O(1)

HEAP-INCREASE-KEY(A, i, key)
if key < A[i]
error "new key is smaller than current key"
a[i] = key
while i > 1 && A[PARENT(i)] < A[i]
exchange A[PARENT(i)] with A[i]
i = PARENT(i)

时间复杂度O(lg (n))

MAX-HEAP-INSERT(A, key)
A.heap-size = A.heap-size + 1
A[A.heap-size] = -∞
HEAP-INCREASE-KEY(A, A.heap-size, key)

时间复杂度O(lg (n))

四个操作的时间复杂度均不大于O(lg (n))

快速排序
期望时间复杂度O(n lg(n))，且隐藏的常数因子很小。最坏情况O(n^2)
快速排序是原址排序
QUICKSORT(A, p, r)
if p < r
q = PARTITION(A, p, r)
QUICKSORT(A, p, q-1)
QUICKSORT(A, q+1, r)

比较难懂，加个注释。

i只有有比x小的元素增加，并且增加同时会和j换位

j一直增加直到 r-1

最终结果下标p到i是小于x的，下标i+1到r-1大于x，最后换位i+1和r完成一轮快速排序

真是巧妙

PARTITION(A, p, r)
x = A[r]
i = p-1
for j = p to r-1
if A[j] <= x
i = i + 1
exchange A[i] with A[j]
exchange A[i+1] with A[r]
return i + 1

快速排序的性能
最坏情况
被划分的两个自问题为0和n-1
递归式为：
递归式
ps.由于对一个大小为0的数组进行排序，直接返回，所以T(0) =𝛩(1)常量级别可看作余项
结果
O(n^2)

平均情况
9:1划分举例

任何一种常数比例的划分都是O(n lg(n)) 只是余项的参数c不一样。
根据算法（升序）q=r，则产生0，n-1划分，为最坏情况
q=p, 同样产生0，n-1划分，同为最坏情况
插入排序基本为O(n)

快速排序为 q趋近于r，时间复杂度接近O(n^2)

快速排序随机化版本
RANDOMIZED-PARTITION(A,p,r)
i = RANDOM(p,r)
exchange A[r] with A[i]
return PARTITION(A,p,r)

RANDOMIZED-QUICKSORT(A,p,r)
if p < r
q = RANDOMIZED-PARTITION(A,p,r)
RANDOMIZED-QUICKSORT(A,p,q-1)
RANDOMIZED-QUICKSORT(A,q+1,r)

计数排序
CONUTING-SORT(A, B, k)
let C[0...k] be a new array
for i = 0 to k
C[i] = 0
for j = 1 to A.length
C[A[j]] = C[A[j]] + 1
for i = 1 to k
C[i] = C[i] + C[i - 1]
// C[i]表示，当前元素应该在的位置
for j = A.length downto 1
B[C[A[j]]] = A[j]
C[A[j]] = C[A[j]] - 1