为什么冒泡排序比快速排序快

Question

我尝试使用两种排序算法对我的列表进行排序：bubble 和 quick。

为此，我分别使用 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

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

原文由 Vladyslav 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 1

算法的时间复杂度并 不能 保证运行时间；相反，它给出了对该算法的渐近行为的 _估计_。在你的例子中， n = 9 非常小，所以算法中隐藏常量的影响将变得比时间复杂度本身的差异更重要。

尝试重新运行您的程序，但这次使用更大的值 n （比如 n=10000）。要测试这两种算法的一般行为，请确保您的输入列表是随机排序的。您还可以尝试使用边缘情况列表（即已经排序）来观察快速排序的最坏情况性能和冒泡排序的最佳情况性能。

原文由 gdelab 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 2

快速排序的最坏情况运行时间是 O(n^2) 。最坏的情况取决于枢轴选择策略，通常它发生在一个已经排序的数组（你的数组就是）。

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

例如，假设冒泡排序需要 3ms 每次迭代，而快速排序需要 20ms 。因此，对于具有 10 项的数组。

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

快速排序需要 10*log2(10)*20 = 664ms 。 （考虑平均情况）

所以冒泡排序在这里更快。但是随着我们采用更大的数据集，由于运行时复杂性降低，快速排序变得越来越高效。

原文由 shawon191 发布，翻译遵循 CC BY-SA 4.0 许可协议