Part_1 : 基本原理
快速排序是基于分治思想排序算法。以数组A[p .. r]为例,分治过程分为三个步骤:
分解：将数组分为两个子数组A[p .. q-1]和A[q+1 .. r],使得A[p .. q-1]中的每一个元素都不大于A(q); A[q+1 .. r]中的元素都不小于A(q)。
排序：通过递归调用快速排序,分别对两个子数组进行排序。
合并：因为是原址排序，所以合并并不需要操作。
QUICKSORT(A,p,r)过程如下所示：
if p < r then q = PARTITION(A,p,r) QUICKSORT(A,p,q-1) QUICKSORT(A,q+1,r)
Part_2 : PARTITION过程
排序算法的关键就是对数组的划分为"大小"两组，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],A[j]) exchange(A[r],A[i+1]) return i+1