<blockquote>
<p>So, all the improvements we make are only useful when our data meets
the worst case (very much sorted in the wrong direction?)</p>
</blockquote>
<p>它不一定是<em>最坏的</em>情况,但是数据中任何一种预先存在的顺序都会对运行时造成不好的影响。预先存在的顺序是非常常见的,我们需要一种利用这种顺序运行得更快的排序,而不是一种看着它就会呕吐的排序。你知道吗</p>
<p>您已经在随机数据上测试了您的快速排序。这几乎是快速排序的最佳情况。如果数据来自dict的键,而使用的散列会导致它们以大致排序的顺序出现呢?你知道吗</p>
<pre><code>>>> data = dict.fromkeys(random.sample(xrange(10000), 9000)).keys()
>>> timeit.timeit('rand_quicksort(data[:], 0, len(data)-1)', 'from __main__ impo
rt rand_quicksort, data', number=1)
0.06688880239187256
>>> timeit.timeit('hoare_quicksort(data[:], 0, len(data)-1)', 'from __main__ imp
ort hoare_quicksort, data', number=1)
# about 1000 lines omitted
File "<stdin>", line 9, in hoare_quicksort
File "<stdin>", line 9, in hoare_quicksort
File "<stdin>", line 9, in hoare_quicksort
File "<stdin>", line 9, in hoare_quicksort
File "<stdin>", line 9, in hoare_quicksort
File "<stdin>", line 9, in hoare_quicksort
File "<stdin>", line 9, in hoare_quicksort
File "<stdin>", line 9, in hoare_quicksort
File "<stdin>", line 9, in hoare_quicksort
File "<stdin>", line 4, in hoare_quicksort
RuntimeError: maximum recursion depth exceeded
</code></pre>
<p>好吧,我们得到一个堆栈溢出,这是可怕的。即使我们不这么做,也要花上一辈子的时间。你知道吗</p>
<p>(如果您想重现这个结果,请注意您的代码中有一些bug。<code>if p</code>应该是<code>if p is not None</code>,<code>random.randint(lo, hi + 1)</code>应该是<code>random.randint(lo, hi)</code>或<code>random.randrange(lo, hi + 1)</code>。为了得到正确的测试结果,我必须修正这些问题。)</p>