# _*_coding:utf-8_*_
import random
def partition(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:
            left += 1
        li[right] = li[left] # 把左边的值写到右边空位
    li[left] = tmp # 把 tmp 归位
    return left


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

li = list(range(10000))
random.shuffle(li)
print(li)
quick_sort(li, 0, len(li) - 1)
# print(li)