QuickSort对于低范围数据运行缓慢

Question

最近我在python中比较了不同类型的排序算法。我注意到我的快速排序不能处理重复值的输入。

def compare_asc(a, b):
    return a <= b


def partition(a, p, r, compare):
    pivot = a[r]
    i = p-1
    for j in range(p, r):
        if compare(a[j], pivot):
            i += 1
            a[i], a[j] = a[j], a[i]
    a[i+1], a[r] = a[r], a[i+1]
    return i + 1


def part_quick_sort(a, p, r, compare):
    if p < r:
        q = partition(a, p, r, compare)
        part_quick_sort(a, p, q-1, compare)
        part_quick_sort(a, q+1, r, compare)


def quick_sort(a, compare):
    part_quick_sort(a, 0, len(a)-1, compare)
    return a

然后我测试一下

import numpy as np
from timeit import default_timer as timer
import sys

test_list1 = np.random.randint(-10000, 10000, size=10000).tolist()
start = timer()
test_list1 = quick_sort(test_list1, compare_asc)
elapsed = timer() - start
print(elapsed)

test_list2 = np.random.randint(0, 2, size=10000).tolist()
start = timer()
test_list2 = quick_sort(test_list2, compare_asc)
elapsed = timer() - start
print(elapsed)

在这个例子中我得到RecursionError: maximum recursion depth exceeded in comparison，所以我添加了sys.setrecursionlimit(1000000)，之后我得到了这个输出：

0.030029324000224733
5.489867554000284

任何人都可以解释为什么它只在排序第二个列表时抛出这个递归深度错误？为什么会有如此大的时差呢？

Answer 1

这是一个提示：传递一个列表，其中所有元素都相同，并逐行观察它的作用。元素数量需要时间二次，并递归到大约等于元素数量的水平。

通常的快速分区实现从两端开始，因此在完全相同的情况下，列表切片大约被切成两半。在这种情况下，您可以通过“仅从左到右”的方法获得不错的表现，但最明确的方法是分为三个区域：“小于”，“相等”和“大于”。

这可以在一个从左到右的通道中完成，通常称为“Dutch national flag problem”。正如链接页面上的文字所示，

该问题的解决方案对于设计排序算法感兴趣;特别是，必须对重复元素具有鲁棒性的快速排序算法的变体需要三向分区功能......

码

具体来说，这是一个完整的实现，执行一次通过“从左到右”的单枢轴三向分区。它还包含了其他众所周知的变化，这些变化使得quicksort能够稳健地用于生产。注意：

• 您无法创建一个避免最坏情况二次时间的纯快速排序。你可以做的最好的是平均情况O(N*log(N))时间，并且（如下所示，一种方式）使最坏情况O(N**2)时间不太可能。
• 您可以（如下所示）保证最坏情况下的对数递归深度。
• 在这种方法中，所有相等元素的列表并不是一个坏的情况，但是一个非常好的情况：分区例程只调用一次。

代码：

from random import randrange

def partition(a, lo, hi, pivot):
    i = L = lo
    R = hi
    # invariants:
    # a[lo:L]  < pivot
    # a[L:i]  == pivot
    # a[i:R]     unknown
    # a[R:hi]  > pivot
    while i < R:
        elt = a[i]
        if elt < pivot:
            a[L], a[i] = elt, a[L]
            L += 1
            i += 1
        elif elt > pivot:
            R -= 1
            a[R], a[i] = elt, a[R]
        else:
            i += 1
    return L, R

def qsort(a, lo=0, hi=None):
    if hi is None:
        hi = len(a)

    while True:   # sort a[lo:hi] in place
        if hi - lo <= 1:
            return

        # select pivot ar random; else it's easy to construct
        # inputs that systematically require quadratic time
        L, R = partition(a, lo, hi, a[randrange(lo, hi)])

        # must recur on only the shorter chunk to guarantee
        # worst-case recursion depth is logarithmic in hi-lo
        if L - lo <= hi - R:
            qsort(a, lo, L)
            # loop to do qsort(a, R, hi)
            lo = R
        else:
            qsort(a, R, hi)
            # loop to do qsort(a, lo, L)
            hi = L