快排

算法思路

快排的算法思想是分治：

分：将整个序列分为左右两个子序列，左边的子序列小于等于x，右边的子序列大于x，这个x我们称为主元（pivot），用它来分割序列
治：子序列递归执行
合：左右两个子序列均已排序，中间的主元满足要求，因此得到的就是最终结果

算法正确性

因为主元所在的位置与最终已排序序列的位置是一致的，那么依次分割，将序列切短至长度为1，那么自然就得到了最终的排序序列

实现

QUICKSORT(A,p,r)
if p < r
 then q ← PARTITION(A,p,r)
  	  QUICKSORT(A,p,q-1)
  	  QUICKSORT(A,q+1,r)

我们用PARTITION来获取主元：

PARTITION(A,p,r)
x ← A[r]
i ← p-1

for j ← p to r-1 do
 if A[j] ≤ x
  i ← i+1
  swapped with A[i] and A[j]
end for

swapped with A[i+1] and A[r]
return i+1

用循环不变式可以证明PARTITION的正确性：

$p \le k \le i ,A[k] \le pivot$
$i+1 \le k \le j-1 ,A[k]>pivot$
$k=r,A[k]=pivot$

$Proof:$

初始：$i=p-1,j=p,[p,i]$和$[i+1,j-1]$没有元素存在
维持：只有当$A[j] \le x$时$i$才会前进，而$j$是无条件递增的，交换$A[i]$和$A[j]$，使得$A[i] \le x$，$A[j]$获得了原来的$A[i+1]>x$，下一次循环前我们还要自增一次，因此$k \le j-1$依然满足循环不变式
终止：当循环终止时，$j=r$，那么$p \le k \le i ,A[k]\le x ,i+1 \le k \le r-1, A[k]>x$

在终止之后，我们将$A[i+1]$和$A[r]$交换（不是和$A[i]$），就得到了主元在序列中的位置

快排的关键才做在于partition()，而partition()的关键在于循环不变式的理解，主要是指其中i，j的理解，它究竟是如何维护循环不变式的。

先说结论，