好吧，这让我抓狂了。我创建了一个简单的Quicksort实现（从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)我还有一个静态选择pivot的版本（注解掉qsrpartition的前两行），如果我在一个随机数组上运行这两个版本，上面的随机版本比总是选择最后一个元素作为pivot的版本快100倍（1s对10s）。
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上面的结果在运行、数组长度、有或没有替换的样本使用、运行函数的顺序等方面都具有概率性。对于一个随机选择的数组，枢轴的选择应该不重要，因为最后一个元素应该和任何中间元素一样好。我觉得有一个明显的解释，我在这里遗漏了。
2条答案
按热度按时间tjrkku2a1#
您的基准测试代码没有度量您想要的内容。
如前所述，列表
li和li2在10次运行中的第一次中排序，而其他9次运行是对已经排序的列表排序。当分区已经排序时，选择最后一个条目作为主元代表最坏的情况，这使得随机主元变体在10次运行中的9次中具有优势。我也会做更多的运行，以获得更好的估计。
以下是更正：
这样的输出稍微偏向于非随机透视版本，原因很简单，它不需要执行这两个额外的语句，在www.example.com上repl.it我得到了这样的输出：
dwthyt8l2#
除了静态与随机选取之外，您还可以测量绘制随机数和交换与不交换。
要衡量随机与非随机透视，不要只注解掉前两行：
无条件地抽取该随机数，使用静态交换（
l[0], l[-1] = l[-1], l[0]）与随机交换。但是吉恩指出了主要的错误：快速排序有序数组。
目前，您正在测量最坏情况与“平均”/“随机”。