非递归的python快速排序实现

非递归的 Python 快速排序实现通常采用“分而治之”的策略，但不依赖于函数调用栈。这种实现通常使用栈或循环控制来代替递归调用。以下是一个简单的非递归快速排序算法的示例：

def quicksort(arr):
    if len(arr) <= 1:
        return arr  # 基线条件：数组只有一个元素或为空

    stack = [(0, len(arr) - 1)]  # 使用栈保存分区边界
    while stack:
        low, high = stack.pop()  # 弹出栈顶元素作为当前分区范围

        pivot_index = partition(arr, low, high)  # 找到基准元素的正确位置
        if pivot_index - low > 1:  # 如果左子区域还有元素
            stack.append((low, pivot_index - 1))  # 子区域入栈
        if high - pivot_index > 1:  # 如果右子区域还有元素
            stack.append((pivot_index + 1, high))  # 子区域入栈

    return arr  # 返回已排序的数组


def partition(arr, low, high):
    pivot = arr[high]  # 基准元素
    i = low - 1  # 指针，用于记录小于基准的元素

    for j in range(low, high):
        if arr[j] < pivot:
            i += 1  # 将较小元素移到左边
            arr[i], arr[j] = arr[j], arr[i]

    arr[i + 1], arr[high] = arr[high], arr[i + 1]  # 将基准元素放到正确的位置
    return i + 1  # 返回基准元素的新索引


# 示例
unsorted_array = [9, 7, 5, 11, 12, 2, 14, 3]
sorted_array = quicksort(unsorted_array)
print("Sorted array:", sorted_array)