#快速排序
def quicksort(lists,i,j):
    while i>j:
        return list
    proivt=lists[i]
    low=i
    high=j
    while i<j:
        while i<j and lists[j]>=proivt:
            j-=1
        lists[i]=lists[j]
        while i<j and lists[i]<=proivt:
            i+=1
        lists[j]=lists[i]
    lists[j]=proivt
    quicksort(lists,low,i-1)
    quicksort(lists,i+1,high)
    return lists

if __name__=="__main__":
    lists=[55,66,22,44,88,33,11,45,12,65]
    print('排序前')
    for i in lists:
        print(i,end=' ')
    print('\n排序后')
    for i in quicksort(lists,0,len(lists)-1):
        print(i,end=' ')
#最好的时间复杂度为：O(nlogn),最坏的时间复杂度为: O(n²)
#平均时间复杂度为：O(nlogn)
#平均空间复杂度为：O(logn)