# quick_sort 代码实现
# TODO：原地修改
def partition(arr, left, right):

    pivot = arr[left]  # 定义一个基准，取当前列表的第一个元素为基准，将这个pivot和其他元素比较
    idx = left  # idx 其实是在记录当前列表下，有（idx - left）个元素小于pivot，
    for i in range(left+1, right+1):  # 遍历当前列表
        if arr[i] <= pivot:  # 一旦发现元素小于pivot， idx+=1， 并且将二者位置互换
            idx += 1
            arr[idx], arr[i] = arr[i], arr[idx]
    arr[left], arr[idx] = arr[idx], arr[left]

    return idx

def quick_sort_utils(arr, left, right):

    if right <= left:  # 确认递归函数的终止条件
        return
    sep = partition(arr, left, right)
    quick_sort_utils(arr, left, sep-1)
    quick_sort_utils(arr, sep+1, right)

def quick_sort(arr):

    quick_sort_utils(arr, 0, len(arr)-1)

# 测试数据
if __name__ == '__main__':
    import random
    random.seed(1)
    arr = [random.randint(0, 100) for _ in range(10)]
    print("原始数据：", arr)
    quick_sort(arr)
    print("快速排序结果：", arr)