# 快排 和 分治 很像 都是分而治之 ，但他们却是 相反的 方式排序 ：分治 是想拆分完成后，合并以有序的小段进行 排序 ，而快排是直接由原始的“拆分”来排序 。
#encoding=utf-8
#从 大 到 小
def partition(A,p,r):
tmp=A[p]
while True :
while p+1<r and A[p] > tmp : p+=1
while r-1>p and A[r] <= tmp : r-=1
if A[p]<=A[r]: A[p],A[r]=A[r],A[p]
if r-1<=p : return p
def quickSort(A,p,r):
if p<r:
q=partition(A,p,r)
quickSort(A,p,q)
quickSort(A,q+1,r)
A=[9,61,7,14,-1,7,667,3,6,8]
print A
quickSort(A,0,len(A)-1)
print A
# 结果 [667, 61, 14, 9, 8, 7, 7, 6, 3, -1]
图解：一次迭代过程描述 （从小到大）：1. 以 A[0] 为切分点 用临时变量 记录 这里是 切分点 = [5] 2. 分别起 2枚指针 [切分起左,右]3. 分别向中间 靠拢 ， 当左指针指向值大于 切分点 停止 左 ， 右指针指向值 小于 切分点 停止 右 。4. 判断 是否是 停止点 上 左值 小于 右值 是：交换两指针值 ！ 
第一次迭代后 :
以初始分隔 [5] 就已经切分好了 小于 5 的左 ，大于等于5 的右
本文转自博客园刘凯毅的博客，原文链接：跟我一起学 - 算法导论 - 快速排序，如需转载请自行联系原博主。
