快速排序 - 非递归

arr = [4, 3, 2, 1, -1, 99, 12, 33, 99, 10]

print(arr)


def partition(arr: list, low: int, high: int, pivot: int):
    while low <= high:
        while arr[low] < pivot:
            low = low + 1

        while arr[high] > pivot:
            high = high - 1

        if low <= high:
            arr[low], arr[high] = arr[high], arr[low]
            low = low + 1
            high = high - 1

    return low


def quicksort(arr: list, low: int, high: int):
    stack = []

    stack.append(low)
    stack.append(high)

    while len(stack) > 0:
        h = stack.pop()
        l = stack.pop()

        if l >= h:
            continue

        pivot = arr[l]  # use first value as pivot

        p = partition(arr, l, h, pivot)

        if l < p:
            stack.append(l)
            stack.append(p - 1)

        if h > p:
            stack.append(p)
            stack.append(h)


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


print(arr)