快速排序：无位置实现工作。就地实现超过了最大递归深度。为什么？

Question

def quicksort_stable(l):
    if not l:
        return l
    else:
        pivot = l[0]
        return quicksort_stable([x for x in l if x < pivot]) \
                + [x for x in l if x == pivot] \
                + quicksort_stable([x for x in l if x > pivot])    

def quicksort_inplace(l):
    def partition(start_idx, end_idx):
        left_idx = start_idx + 1
        right_idx = end_idx
        while True:
            while left_idx <= right_idx and l[left_idx] <= l[start_idx]:
                left_idx += 1
            while right_idx >= left_idx and l[right_idx] >= l[start_idx]:
                right_idx -= 1

            if right_idx < left_idx:
                break
            else:
                l[left_idx], l[right_idx] = l[right_idx], l[left_idx]

        l[start_idx], l[right_idx] = l[right_idx], l[start_idx]     

        return right_idx

    def qs(start_idx, end_idx):
        if start_idx < end_idx:
            split_idx = partition(start_idx, end_idx)
            qs(start_idx, split_idx - 1)
            qs(split_idx + 1, end_idx)

    qs(0, len(l) - 1)
    return l

if __name__ == '__main__':

    import random

    l1 = [random.randint(0, 9) for x in range(10000)]
    l2 = [x for x in l1]

    l1 = quicksort_stable(l1)
    quicksort_inplace(l2)

我特意选择了第一个元素作为轴心，而不是随机化，以确保两个实现的行为方式相同。你知道吗

这两种实现都是递归实现的。在调用堆栈中，似乎quicksort\u inplace应该占用O（lgn）空间，而quicksort\u stable应该占用O（n）空间，因为它每次递归时都会创建一个新列表。你知道吗

然而，quicksort\u inplace会导致“超过最大递归深度”，而quicksort\u stable工作正常。你知道吗

为什么会这样？你知道吗

Answer 1

我相信这个行为的原因是你的列表包含很多重复（每一个元素出现1000次），你“欺骗”了通过收集所有与枢轴相同的元素而不返回到它们的元素（当然太好了！）来实现稳定eEM>版本。你知道吗

所以要真正比较这两个过程，应该是这样的：

    def quicksort_stable(l):
        if not l or len(l)==1:
            return l
        else:
            pivot = l[0]
            rst = l[1:]
            return quicksort_stable([x for x in rst if x < pivot]) \
                    + [pivot] \
                    + quicksort_stable([x for x in rst if x >= pivot])    

另外，为了得到上述的破坏性（原地）版本，你应该在你的第二个条件中改变一个大于的条件（这样在右边的idx有不小于枢轴的元素），即

        while right_idx >= left_idx and l[right_idx] > l[start_idx]:

如果这样做，您会发现这两个过程都会导致数组上的堆栈溢出，数组中的10000个元素来自范围（0,9）（还要注意，对于范围（0,99），情况并非如此，因为它们需要较少的“剪切”）。你知道吗