为什么气泡排序比快速排序更快？

Question

我尝试使用两种排序算法对我的列表进行排序:冒泡算法和快速算法。

为此，我分别使用了algorithms模块和bubble_sort、quick_sort。据我所知，第一种算法的复杂性是n^2，第二种是n*log(n)。但是我从这段代码中得到了意想不到的输出：

from algorithms.sorting import bubble_sort, quick_sort
import time

my_list = [1, 12, 33, 14, 52, 16, 71, 18, 94]
start1 = time.time()
for i in range(1000000):
    bubble_sort.sort(my_list)

end1 = time.time()
start2 = time.time()
for i in range(1000000):
    quick_sort.sort(my_list)

end2 = time.time()

print('Bubble sort:', end1 - start1)
print('Quick sort:',end2 - start2)

输出：

>>> Bubble sort: 7.04760217666626
>>> Quick sort: 8.181402921676636

为什么在这种情况下，气泡排序比快速排序更快？

Answer 1

算法的时间复杂度并不能保证运行时，而是给出了该算法的渐近行为的估计。在您的例子中，n = 9非常小，因此隐藏常数在算法中的影响将比时间复杂性本身的差异更重要。

尝试重新运行您的程序，但这次的n值要大得多(比如n=10000)。要测试这两种算法的一般行为，请确保输入列表是随机排序的。您还可以试验边缘案例列表(即已排序)，以观察快速排序的最差情况性能和气泡排序的最佳情况性能。

Answer 2

最坏的情况是快速排序的运行时间是O(n^2)。最坏的情况取决于枢轴选择策略，通常发生在已经排序的数组中(您的数组是这样的)。

此外，对于小数据集，气泡排序或其他简单排序算法通常比更复杂的算法工作得更快。原因是，对于每一次迭代，简单算法的计算量都比复杂算法少。

例如，假设冒泡排序每次迭代都采用3ms，而快速排序则采用20ms。因此，对于包含10项的数组。

在这种情况下，冒泡排序采用10*10*3 = 300ms。

然后快速排序取10*log2(10)*20 = 664ms。(考虑平均情况)

所以泡泡分类在这里更快。但是当我们使用更大的数据集时，由于运行时复杂度降低，快速排序变得越来越高效。

Answer 3

泡沫在某些情况下比快速排序更好的原因是许多计算机科学家失去了:的确，气泡排序将导致比快速排序更多的“元素交换”。但除了消除掉期交易之外，业绩还有更多的意义。Bubblesort通常是“内联”例程(而不是“强制”函数调用)。即使它被编码为一个函数，一个好的优化编译器也会将它编译成一行。如果不是，那么每种类型仍然只有一个函数调用。然而，快速排序依赖于递归，这强制函数调用机制。每次发生递归循环(从内调用quicksort)时，整个环境都需要保存在堆栈上。然后执行控制的转移。在递归结束时，需要恢复整个环境，并执行另一次控制传输(返回到调用函数)。在频繁的递归中，可能会有非常严重的性能损失。在我看来，很多人看快速排序和递归的“优雅”，但忽略了它的开销。我并不是在真空中这么说，而是写了一些基准和短期互换，但仍然比快速更好。在这些基准测试中，我发现即使对于已经“有序”的数据，快速排序也会递归N-1次，N是要排序的元素数。