python快速排序

jopen 10年前

import random    def rand(n):        for i in range(n):            yield random.randint(0,1000)    #创建一个随机数列表    def createList(n):        lists=[]        for i in rand(n):            lists.append(i)        return lists    #挖坑法快速排序    def quick_sort(lists,l,r):        if(l<r):            #x是选取的pivot基准值,然后把数据大于基准值的排到右边,小于基准值的排到左边            i,j,x=l,r,lists[l]            while(i<j):                #j从右边开始遍历,找到j<x的地方,并跟lists[i]交换,                while(i<j and lists[j]>=x):                    j-=1                if(i<j):                    lists[i]=lists[j]                    i+=1                #i从左边开始遍历,找到j>x的地方,并跟lists[j]交换                while(i<j and lists[i]<=x):                    i+=1                if(i<j):                    lists[j]=lists[i]                    j-=1            #此时,i已经大于等于j了,也就是说i左边的都小于x,右边都大于x,所以现在把i填入x,接下来就递归排序            lists[i]=x            quick_sort(lists,l,i-1)            quick_sort(lists,i+1,r)                lists=createList(1000)    print lists    quick_sort(lists,0,len(lists)-1)    print lists