"""
快速排序
第一步
先去找一个基准数， 再设2个指针i,j， i从左到右遍历， 找到大于基准数的数时停止，
j从右到左遍历， 找到小于基准数的数时停止， 然后交换i,j的位置， 
i和j再分别向两边扩展， 直到i和j相遇， 再把基准数插入到这个相遇的位置
第二步
第一步产生了两个子数组， 再分别运用第一步。
"""

def partion(left, right):
    pivot = lst[left]
    while left < right:
        while left < right and lst[right] >= pivot:
            right -= 1
        while left < right and lst[left] <= pivot:
            left += 1
        lst[left], lst[right] = lst[right], lst[left]
    lst[left] = pivot
    return left

def quick(left, right):
    if left >= right:
        return
    pivot = partion(left, right)
    quick(left, pivot - 1)
    quick(pivot + 1, right)
    return lst
    
lst = [4, 1, 8,3, 1, 5, 2, 7, 6,1]
print(quick(0, len(lst) - 1))