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