首页 > 代码库 > python快速排序

python快速排序

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

    
    

python快速排序