Python中快速排序性能对比：随机枢轴vs固定枢轴

我基于CLR实现了一个简单的快速排序，采用随机选择枢轴的方式：

def qsr(l, s, e):
    def qsrpartition(l, s, e):
        pivotindex=random.randrange(s,e+1)
        l[e], l[pivotindex] = l[pivotindex], l[e]
        p = l[e]
        i = s - 1
        for j in range(s, e):
            if l[j] <= p:
                i = i+1
                l[i], l[j] = l[j], l[i]
        l[i+1], l[e] = l[e], l[i+1]
        return i+1
        
    if s < e:
        q = qsrpartition(l, s, e)
        qsr(l, s, q-1)
        qsr(l, q+1, e)    

我还有一个采用固定枢轴选择的版本（注释掉qsrpartition的前两行）。如果在随机数组上运行这两个版本，上述随机版本比总是选择最后一个元素作为枢轴的版本快100倍（1秒vs10秒）。

测试代码及结果：

li = random.choices(range(5000), k=5000)
li2 = random.choices(range(5000), k=5000)
r1 = timeit.timeit(lambda:qs(li, 0, len(li)-1),number=10)
r2 = timeit.timeit(lambda:qsr(li2, 0, len(li2)-1),number=10)
print(r1, r2)

11.10 0.08

上述结果在多次运行、不同数组长度、有无放回采样、函数运行顺序等场景下均具有统计显著性。按道理，对于随机数组而言，枢轴的选择应该无关紧要，因为最后一个元素应该和其他元素一样合适。我实在搞不懂这是为什么，求技术解答。

核心问题出在你测试固定枢轴版本时，数组已经被排序过一次了！

看你的测试代码：timeit会重复执行lambda:qs(li, 0, len(li)-1)共10次。第一次执行后，li已经被完全排序了，剩下的9次都是在对已排序数组进行固定最后元素作为枢轴的快排——这会触发快排的最坏情况，时间复杂度退化为O(n²)。

而随机枢轴版本的li2呢？每次执行qsr(li2, ...)时，虽然第一次也会排序数组，但随机枢轴的快排在已排序数组上依然能保持O(n log n)的时间复杂度，因为随机选枢轴会打破已排序数组的最坏情况结构。

验证这个结论很简单：把测试代码改成每次执行前都重新生成随机数组，比如：

r1 = timeit.timeit(lambda: qs(random.choices(range(5000), k=5000), 0, 4999), number=10)
r2 = timeit.timeit(lambda: qsr(random.choices(range(5000), k=5000), 0, 4999), number=10)

这样两个版本的执行时间就会基本一致，因为每次都是对全新的随机数组排序，固定最后元素作为枢轴的快排也能达到O(n log n)的平均复杂度，和随机枢轴版本性能接近。

总结一下：你之前的测试用例犯了一个常见错误——复用了已经被排序的数组，导致固定枢轴版本连续执行最坏情况，而随机枢轴版本不受影响，所以出现了100倍的性能差距。

内容的提问来源于stack exchange，提问作者kdl_kdl