快速排序

QUICKSORT(A, p, r)

if p < r

    q = PARTITION(A,p,r)

    QUICKSORT(A, p, q-1)

    QUICKSORT(A, q+1, r)

    

PARTITION(A, p, r)

x = A[r]

i = p-1

for j = p to r-1

    if A[j] <= r

    i = i + 1

    exchange A[i] with A[j]

exchange A[i+1] with A[r]

return i+ 1

随着程序的执行，数组被划分为4个（可能有空的）区域，for循环没一轮迭代的开始，每一个区域都满足一定

的性质，我们将这些性质作为循环不变量

1，若 p <= k <= i , 则 A[k] <= x

2, 若 i+1 <= k <= j-1, 则 A[k] > x

3, 若 k = r , 则 A[k] = x