跟我一起学 - 算法导论 - 快速排序

# 快排 和 分治 很像 都是分而治之 ,但他们却是 相反的 方式排序 :
分治 是想拆分完成后,合并以有序的小段进行 排序 ,而快排是直接由原始的“拆分”来排序 。
#encoding=utf-8
#
从 大 到 小
def partition(A,p,r):
    tmp
=A[p]
    
while True :
        
while p+1<and A[p] > tmp : p+=1
        
while r-1>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 的右

本文转自博客园刘凯毅的博客,原文链接:跟我一起学 - 算法导论 - 快速排序,如需转载请自行联系原博主。

上一篇:html5/CSS3鼠标滑过图片特效插件


下一篇:iOS使用lua语言的使用步骤与实现插件的动态更新