def quick_sort(alist, first, last):
    if first >= last:
        # 如果开始等于结尾，即就一个元素
        return
    mid_value = alist[first]
    low = first
    high = last
    # 对于相等的情况都放到low的位置，所以第一个条件是>=.数据尽量放在一边。
    while low < high:
        # hight开始移动,左移所以-1
        while low < high and alist[high] >= mid_value:
            high -= 1  # high游标左走
        alist[low] = alist[high]  # 把大于mid的值放到low的位置
        # low开始移动
        while low < high and alist[low] < mid_value:
            low += 1
        alist[high] = alist[low]
        # high -= 1  # high游标左走
        # 当low=high时从循环退出
        alist[low] = mid_value
        # 或者 
        # alist[high] = mid_value

        # 对low左边的列表排序
        quick_sort(alist, first, low - 1)
        # 对low右边的列表排序
        quick_sort(alist, low + 1, last)


if __name__ == '__main__':
    arr = [1, 2, 3, 94, 5, 6, 6, 6, 6]
    quick_sort(arr, 0, len(arr) - 1)
    print(arr)