快速排序不获取qui

Question

我最近了解到人们如何努力使快速排序更快。从随机选择一个枢轴元素到切换到较小数组的插入排序，甚至用3路分区处理相等的键。我很好奇随机生成的数据是如何工作的，于是想到了分析一些python代码。我附上下面的脚本。问题是脚本最终花费的时间是相同的！当我使用%prun时，看起来调用快速排序的次数也非常相似。因此，我们所做的所有改进只有在数据遇到最坏情况时才有用（很大程度上是按错误的方向排序的？）你知道吗

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)

这是我们选择第一个元素本身作为轴心的普通实现。然后，我改为选择中点。你知道吗

所以，有一行变了

mid = lo + (hi - lo)//2

a[lo], a[mid] = a[mid], a[lo]
pivot = a[lo]

然后我也随机选择轴心点，像这样：

pos = random.randint(lo, hi + 1)


a[lo], a[pos] = a[pos], a[lo]
pivot = a[lo]

现在，我用

%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)

所有这些都需要几乎相同的时间（5.22、5.27、5.61毫秒）。当我使用%prun调用它们并查看调用quicksort的次数时，我再次得到非常相似的号码。那么，怎么了？你知道吗

Answer 1

So, all the improvements we make are only useful when our data meets the worst case (very much sorted in the wrong direction?)

它不一定是最坏的情况，但是数据中任何一种预先存在的顺序都会对运行时造成不好的影响。预先存在的顺序是非常常见的，我们需要一种利用这种顺序运行得更快的排序，而不是一种看着它就会呕吐的排序。你知道吗

您已经在随机数据上测试了您的快速排序。这几乎是快速排序的最佳情况。如果数据来自dict的键，而使用的散列会导致它们以大致排序的顺序出现呢？你知道吗

>>> 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

好吧，我们得到一个堆栈溢出，这是可怕的。即使我们不这么做，也要花上一辈子的时间。你知道吗

（如果您想重现这个结果，请注意您的代码中有一些bug。if p应该是if p is not None，random.randint(lo, hi + 1)应该是random.randint(lo, hi)或random.randrange(lo, hi + 1)。为了得到正确的测试结果，我必须修正这些问题。）

Answer 2

你的基准被打破了。你知道吗

1. 您正在对random.randint的1000次迭代进行基准测试，而不是您的排序。你知道吗
2. 每种排序只运行一次，因此您要对操作系统中的线程和进程切换延迟进行基准测试。你知道吗

尝试预先创建源数组，并运行每种排序，甚至数百万次。你知道吗

Answer 3

随机化轴心点选择并不能使快速排序更快：它只是用来避免我们的算法执行最坏的情况。假设我们对一个已经排序的向量进行排序，并决定选择pivot作为每个子数组最右边的元素：它包含这个子数组的最大值，因此快速排序以最不平衡的方式将子数组分成两部分。这可以通过随机化来防止。如果我们一定要避免最坏情况，我们可以说算法需要相似的时间，直到每个递归级别生成近似恒定平衡的分区，这样我们就可以证明递归树的深度是恒定的