Skynet

---------- ---------- 我的新 blog : liukaiyi.cublog.cn ---------- ----------

  BlogJava :: 首页 :: 联系 :: 聚合  :: 管理
  112 Posts :: 1 Stories :: 49 Comments :: 0 Trackbacks

# 快排 和 分治 很像 都是分而治之 ,但他们却是 相反的 方式排序 :
分治 是想拆分完成后,合并以有序的小段进行 排序 ,而快排是直接由原始的“拆分”来排序


#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 的右




整理 www.blogjava.net/Good-Game
posted on 2009-12-03 17:11 刘凯毅 阅读(1639) 评论(0)  编辑  收藏 所属分类: python算法/函数

只有注册用户登录后才能发表评论。


网站导航: