0. 快速排序

由Tony Hoare在1962年发明，这是一个分治算法，它就在原地完成排序，类似与插入排序。
优点：节约内存资源，非常实用，线性复杂度

1. 分治策略

1.1 分

快速排序通过选取一个关键数据，再根据它的大小，把原数组分为两个子数组，第一个数组里面的元数据都比第二个数组里的元素大或者相等。

1.2 治

对两个子数组进行递归排序。

1.3 合

最后得到的数组便是排好序的数组。

快速排序关键的一步就是 分 ，即递归地划分数组，而归并排序就可以说是递归地合并数组。

2. 分析

伪代码如下所示:

/* 划分 */
Partition(A, p, q)  // A[p...q]
x <- A[p]           // 需要作比较的数，哨兵
i <- p
for j <- p+1 to q
    do if A[j] <= x
        then i <- i+1
           exch A[i] <-> A[j]
exch A[p] <-> A[i]
return i

/* 快速排序 */
QuitSort(A, p, q)
if(p<q)
    then r <- Partition(A, p, q)
        QuickSort(A, p, r)
        QuickSort(A, r, q)
        
        
/* 初始调用 */
Init call:
QuickSort(A, 1, n)