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

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)。要测试这两种算法的一般行为，请确保您的输入列表是随机排序的。您还可以尝试使用边缘情况列表(即已经排序的)来观察快速排序的最坏情况性能和冒泡排序的最佳情况性能。