"""
核心：将小于基准的数移到左边，将大于基准的数移到右边，再对左右分区继续执行快速排序
1. 选择列表中的一个数作为基准，一般是第一个元素
2. 设置左右两个指针，分别指向第一个元素和最后一个元素
3. 向左移动右指针，若发现比基准值小的值，则将其与基准值交换
4. 接着向右移动左指针，若发现比基准值大的值，则将其与基准值交换
5. 重复 3, 4，直到 左右指针相遇
6. 最后基准值所在的位置，左边都比其小，右边都比其大
7. 再对左右区域指向快排

复杂度为 O(n^2)
"""


def quick_sort(nums: list[int], low: int, high: int):
    i = low
    j = high
    # 一开始的基准值为 nums[i]
    if low >= high:
        return
    while i < j:
        while i < j and nums[j] >= nums[i]:
            j -= 1

        if i < j:
            # 交换后基准值移到右边
            nums[i], nums[j] = nums[j], nums[i]
            i += 1

        while i < j and nums[i] < nums[j]:
            i += 1

        if i < j:
            # 交换后基准值移到左边
            nums[j], nums[i] = nums[i], nums[j]
            j -= 1

    # 基准值位置是i，所以 low 到 i-1 是小区基准值的区域
    quick_sort(nums, low, i - 1)
    #
    quick_sort(nums, j + 1, high)


nums = [47, 29, 71, 99, 78, 19, 24, 47]
quick_sort(nums, 0, len(nums)-1)
print(nums)