def quick_sort(a):
    if len(a) < 2:
        return a
    prv = a[0]
    left = [x for x in a[1:] if x <= prv]
    right = [x for x in a[1:] if x > prv]
    return quick_sort(left)+[prv]+quick_sort(right)
#第一種代碼簡單，但是需要額外占用空間，空間復(fù)雜度高！
def quicksort(a,begin,end):
    if begin<end:#遞歸的時候quicksort(a,right+1,end)可能會導(dǎo)致數(shù)組index溢出
        prv = a[begin]
        left = begin+1
        right = end
        while left <= right:#當left>right時停止循環(huán)，此時將prv與right的位置交換
            while left <= right and a[right] > prv:
                right-=1
            while left <= right and a[left] <= prv:
                left+=1
            if left > right:
                break
            else:
                a[left],a[right] = a[right],a[left]
        a[right],a[begin] = a[begin],a[right]
        quicksort(a,begin,right-1)
        quicksort(a,right+1,end)

if __name__ == "__main__":
    a = [1,8,8,0,5,1,9,3,7,6,6]
    print(quick_sort(a))
    b = [1,5,0,6,5,2,5,3,2,3]
    quicksort(b,0,len(b)-1)
    print(b)
    c = [1232,43,13,4,124,54,7678,87,674,522,23]
    quicksort(c,0,len(c)-1)
    print(c)
    d = [124,13,234,436,565,3466,5673,54,46]
    quicksort(d,0,len(d)-1)
    print(d)
    e = [1321,435,12,3534,6,5768,7,789,7456,3]
    quicksort(e,0,len(e)-1)
    print(e)