数据结构快速排序非递归代码

快速排序是一种高效的排序算法，其基本思想是通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，然后分别对这两部分记录继续进行排序，直到整个序列有序。非递归版本的快速排序通常采用栈来模拟递归过程。

以下是快速排序的非递归实现的一个伪代码例子：

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

    stack = [(0, len(arr) - 1)]  # 初始化栈，包含起始索引和结束索引
    while stack:  # 当栈不为空时
        left, right = stack.pop()  # 弹出栈顶元素，获取左右边界

        pivot_index = partition(arr, left, right)  # 分区操作，找到基准元素的正确位置
        if pivot_index - 1 > left:  # 如果分区后有剩余元素
            stack.append((left, pivot_index - 1))  # 将左半部分入栈
        if pivot_index + 1 < right:  # 同理，如果右半部分有剩余元素
            stack.append((pivot_index + 1, right))  # 将右半部分入栈

    return arr  # 返回已排序的数组

def partition(arr, low, high):  # 分区函数
    pivot = arr[high]  # 选择最后一个元素作为基准
    i = low - 1  # 指针i从左边开始

    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  # 返回基准元素的新位置

# 示例使用
arr = [9, 7, 5, 11, 12, 2, 14, 3]
sorted_arr = quicksort(arr)
print("Sorted array:", sorted_arr)