Python 非递归快速排序算法实现

以下是一个非递归的快速排序程序，使用栈来实现递归过程：

def quicksort(arr):
    stack = [(0, len(arr) - 1)]
    while stack:
        start, end = stack.pop()
        if start >= end:
            continue
        pivot = arr[end]
        i = start - 1
        for j in range(start, end):
            if arr[j] < pivot:
                i += 1
                arr[i], arr[j] = arr[j], arr[i]
        i += 1
        arr[i], arr[end] = arr[end], arr[i]
        stack.append((start, i - 1))
        stack.append((i + 1, end))
    return arr

该程序使用一个栈来存储待处理的子数组的起始和结束索引。在每次循环中，弹出栈顶的子数组，并使用快速排序算法对其进行排序。如果子数组长度为1或0，则不需要进行排序。否则，以子数组的最后一个元素为枢轴，将子数组划分为小于枢轴值和大于枢轴值的两部分。然后将左右两个子数组的起始和结束索引压入栈中，以便进行后续的排序。最终返回已经排序好的原始数组。