"""空间复杂度平均 O(log n)"""
import random
def quick_sort(nums, low, high):
    if low >= high:
        return
    # pivot = random.randint(low, high)
    # nums[low], nums[pivot] = nums[pivot], nums[low]
    tmp = nums[low]
    i, j = low, high
    while i < j:
        while i < j and nums[j] >= tmp:
            j -= 1
        nums[i] = nums[j]
        while i < j and nums[i] <= tmp:
            i += 1
        nums[j] = nums[i]
    nums[i] = tmp
    quick_sort(nums, low, i-1)
    quick_sort(nums, i+1, high)

x = [1, 2, 34, -1, -9, 0, 2, 13]
quick_sort(x, 0, len(x)-1)
print(x)
    

"""空间复杂度平均 O(n log n)"""
def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[len(arr) // 2]  # 选择中间元素作为基准
    left = [x for x in arr if x < pivot]
    middle = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]
    return quick_sort(left) + middle + quick_sort(right)