快速排序非递归 python

快速排序是一种常用的排序算法，它的递归实现已经在上一期中介绍过了。而非递归实现快速排序的方法也是存在的，可以通过使用堆栈来模拟递归的过程。下面是Python的非递归快排实现代码：

def QuickSort_No_Stack(nums:list,left:int,right:int) -> list:
    temp = [left,right]
    while temp:
        j = temp.pop() # j = right
        i = temp.pop() # i = left
        index = getIndex(nums,i,j)
        if i < index-1: # 压入堆栈 注意左右边界的顺序
            temp.append(i)
            temp.append(index-1)
        if j > index+1:
            temp.append(index+1)
            temp.append(j)
    return nums

其中，getIndex函数是快速排序中的一个关键步骤，用于获取基准值的位置。具体实现可以参考上一期的递归实现。