回答此问题可获得 20 贡献值,回答如果被采纳可获得 50 分。
<p>我最近了解到人们如何努力使快速排序更快。从随机选择一个枢轴元素到切换到较小数组的插入排序,甚至用3路分区处理相等的键。我很好奇随机生成的数据是如何工作的,于是想到了分析一些python代码。我附上下面的脚本。问题是脚本最终花费的时间是相同的!当我使用%prun时,看起来调用快速排序的次数也非常相似。因此,我们所做的所有改进只有在数据遇到最坏情况时才有用(很大程度上是按错误的方向排序的?)你知道吗</p>
<pre><code>def hoare_partition(a, lo, hi):
if lo >= hi or (lo + 1) == len(a) - 1:
return None
pivot = a[lo]
left = lo + 1
right = hi
while left <= right and right < len(a):
while left < len(a) and a[left] < pivot:
left += 1
while a[right] > pivot:
right -= 1
if left <= right and right < len(a):
a[left], a[right] = a[right], a[left]
left += 1
right -= 1
a[lo], a[right] = a[right], a[lo]
return right
def hoare_quicksort(a, lo, hi):
''' this is a vanilla implementation of quick sort. this will call the partition method that uses first element as pivot '''
if lo < hi:
p = hoare_partition(a, lo, hi)
if p:
#print 'calling for ', lo, p - 1
hoare_quicksort(a, lo, p - 1)
#print 'calling for ', p + 1, hi
hoare_quicksort(a, p + 1, hi)
</code></pre>
<p>这是我们选择第一个元素本身作为轴心的普通实现。然后,我改为选择中点。你知道吗</p>
<p>所以,有一行变了</p>
<pre><code>mid = lo + (hi - lo)//2
a[lo], a[mid] = a[mid], a[lo]
pivot = a[lo]
</code></pre>
<p>然后我也随机选择轴心点,像这样:</p>
<pre><code>pos = random.randint(lo, hi + 1)
a[lo], a[pos] = a[pos], a[lo]
pivot = a[lo]
</code></pre>
<p>现在,我用</p>
<pre><code>%prun hoare_quicksort([random.randint(0, 10000) for i in xrange(1000)], 0, 999)
%prun mid_quicksort([random.randint(0, 10000) for i in xrange(1000)], 0, 999)
%prun random_quicksort([random.randint(0, 10000) for i in xrange(1000)], 0, 999)
</code></pre>
<p>所有这些都需要几乎相同的时间(5.22、5.27、5.61毫秒)。当我使用%prun调用它们并查看调用quicksort的次数时,我再次得到非常相似的号码。那么,怎么了?你知道吗</p>