Qui中递归的平坦化

Question

因此，我尝试在Python2.7中实现快速排序，并且我使用递归函数成功地实现了这一点，但是当我调用快速排序（范围（1000）[：：-1]）时，它会感到不安，这是可以理解的。也就是说，它最大化了Python中允许的递归深度。你知道吗

所以现在我想“展平”这个函数，也就是说，使用尽可能少（或不）的递归调用。我一直在尝试通过一个分区函数来实现这一点，分区函数不返回列表，而只在将所有内容向左和向右排序后返回轴心的位置。我已经写了这个，并测试了它，它似乎是完美的工作。如果有人感兴趣，代码如下。你知道吗

现在的诀窍似乎是让这个东西反复分区，直到整个列表被排序，我正在努力看看如何实现这一部分。我的一个想法是创建一个索引的有序列表，这些索引是一个轴所使用的所有索引。然后我可以运行while循环，当索引列表与range（n）相同时，该循环将中断。不过，我不确定这个想法有多聪明或优雅，因为我会生成一个与输入列表长度相同的第二个列表——看起来像是一个可以避免的内存消耗。另一方面，似乎您需要一种方法来跟踪您已经排序的列表的哪些部分，为此，我只能想到递归或这个列表的想法。你知道吗

所以问题是，这个列表是好是坏，如果不好，什么是更好的主意？你知道吗

def partition(x, start, end, pivotIndex):
    '''
    x is a list, start to end is the portion of the list to sort, and 
    pivotIndex is the index at which pull a value and sort everything above
    and below this.
    '''
    low = start # Low will track the lower bound of the position in the list
                # where "small" elements get switched into.  It starts at 
                # start.
    high = end-1
    p = x[pivotIndex] # Pivot value
    x[pivotIndex] = x[end] # We basically move the pivot entry out of the way
                           # and we'll put it back in at the end.
    while True:
        while low <= high and x[low] < p: # We cycle up the bottom of the list
                          # until we've looked at everything or until we hit
                          # a pice that's out of place.
            low += 1
        while low <= high and x[high] >= p: # And do likewise from the top of 
                         # the list.
            high -= 1
        if low > high: # If we've covered the whole list, the partition is 
                       # done.  Otherwise, there must be pieces out of place
                       # so swap them.
            break
        x[low], x[high] = x[high], x[low]
    x[end] = x[low] # The value at end stores a duplicate of some value,
                    # since we copied it in, so now we want to over-ride that.
                    # We choose to put the element now at low there, and put
                    # since the pivot value was taken out of the list, we now
                    # put it in the low position.
    x[low] = p
    return low