声明：参考B站视频，自学成长记录
https://www.bilibili.com/video/BV1mp4y1D7UP?p=16

'''
快速排序
    1. 取一个值归位
    2. 根据归位值分 左(比归位数小) / 右(比归位数大) 两部分
    3. 递归 1、2 步

'''
def kuaipai(lst, left, right):
    '''
    快速排序
    :param lst:  无序列表
    :param left: 最左下标
    :param right: 最右下标
    :return:
    '''
    # 将最左元素拿出来 存放到临时变量中
    tmp = lst[left]
    while left < right:
        # 右向左跳（从最右边开始找比列表left位置大的数）
        while left < right and lst[right] >= tmp:
            # 从右边往左挪一个位置
            right -= 1
        # 从右边起 将比tmp小的数 写到 列表的left位置
        lst[left] = lst[right]

        # 左向右跳（从次左边开始找比列表left位置大的数）
        while left < right and lst[left] <= tmp:
            # 从最左边往右挪一个位置
            left += 1
        # 从左边起 将比tmp大的数 写到 列表的right位置
        lst[right] = lst[left]

    # 将值归位
    lst[left] = tmp
    # 返回归位值得下标
    return left


def quick_sort(lst, left, right):
    if left < right:
        # 获取lst[left]归为后的下标
        mid = kuaipai(lst, left, right)
        # 递归处理左半部分
        quick_sort(lst, left, mid - 1)
        # 递归处理右半部分
        quick_sort(lst, mid + 1, right)


lst = [5, 6, 9, 4, 2, 7, 1, 8]
print(lst)
quick_sort(lst, 0, len(lst) - 1)
print(lst)

'''
运行结果
    [5, 6, 9, 4, 2, 7, 1, 8]
    [1, 2, 4, 5, 6, 7, 8, 9]
'''