def partation(li,left,right):
    tmp = li[left]
    while left < right:
        while left < right and li[right] >= tmp:  # 右边找比tmp小的数
            right -= 1
        li[left] = li[right]
        while left < right and li[left] <= tmp:   # 左边找比tmp大的数
            left += 1
        li[right] = li[left]
    li[left] = tmp
    return left

def quick_sort(li,left,right):
    if left < right:
        mid = partation(li,left,right)
        quick_sort(li,left,mid-1)
        quick_sort(li,mid+1,right)


def main():
    li = [3,2,7,4,8,9,6,5,1]
    quick_sort(li,0,len(li)-1)
    print(li)

if __name__ == '__main__':
    main()