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

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

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

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

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

在这种情况下，冒泡排序需要10*10*3 = 300ms.

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

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

Answer 2

算法的时间复杂度并不能保证运行时间；相反，它给出了该算法的渐近行为的估计。在您的情况下，n = 9非常小，因此算法中隐藏常数的影响将变得比时间复杂度本身的差异更重要。

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