# 快排 和 分治 很像 都是
分而治之
，但他们却是 相反的 方式排序 ：
分治 是想拆分完成后，合并以有序的小段进行 排序 ，而快排是直接由原始的“拆分”来 排序 。
一次迭代过程描述 （从小到大）：
1. 以 A[0] 为切分点 用临时变量 记录 这里是 切分点 = [5]
2. 分别起 2枚指针 [切分起左,右]
3. 分别向中间 靠拢 ， 当左指针指向值大于 切分点 停止 左 ， 右指针指向值 小于 切分点 停止 右 。
4. 判断 是否是 停止点 上 左值 小于 右值 是：交换两指针值 ！
第一次迭代后 :
分治 是想拆分完成后，合并以有序的小段进行 排序 ，而快排是直接由原始的“拆分”来 排序 。
#
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]
图解：
# 从 大 到 小
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 的右
本文转自博客园刘凯毅的博客，原文链接：跟我一起学 - 算法导论 - 快速排序，如需转载请自行联系原博主。
