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

Question

我尝试使用两种排序算法和quick sort来对我的列表进行排序。
为此，我分别使用了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

---

您的测试数据太少，n^2 的影响不明显。 - jonatan

开始一个未排序的列表。 - Ma0

因为列表已经排序。快速排序在这种情况下可能表现不佳，取决于如何选择枢轴元素。 - Nandu Kalidindi

此外，您的数据已经排序。我不知道algorithms模块（你也没有说它来自哪里），但它看起来足够智能，可以在内部循环未执行任何交换时终止。因此，在这种情况下，它对列表进行了一次单独的遍历，其时间复杂度为O(n)。 - PM 2Ring

Answer 1

算法的时间复杂度并不能保证程序的运行时间，而是给出了该算法渐进行为的一个估计。在你的情况下，当n=9时，算法中隐藏的常数因子将变得比时间复杂度本身更重要。

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

- gdelab

---

我使用了100,000个元素运行BubbleSort，与在相同条件下使用java.utils.Array.sort相比，它快了几倍。虽然这不是最好的实现，因为我从GeeksForGeeks页面上抄袭了它（如果你去那里看第二个代码片段，就会明白）。我对每个排序算法进行了100次排序，并计算了它们的平均值，每个排序都有一个随机生成的整数数组。我知道java.utils.Array.sort并不是快速排序。所以我采用了我的快速排序实现（以最后一个元素作为枢轴，效果不佳）。它给出了与java.utils.Array.sort相同的结果。 - user11655900

@user11655900 快速排序的最坏情况运行时间为O(n^2)，这取决于数据集和枢轴选择。您可能需要通过代码进行调试，以查看算法为何表现不佳。 - shawon191

Answer 2

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

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

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

在这种情况下，冒泡排序需要10*10*3 = 300毫秒。

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

因此，在这里冒泡排序更快。但是随着数据集变大，由于运行时复杂度较低，快速排序变得越来越高效。

- shawon191

Answer 3

在某些情况下，冒泡排序比快速排序表现更好，这一点对许多计算机科学家来说是不明显的。当然，与快速排序相比，冒泡排序会导致更多的“元素交换”。但性能不仅仅取决于消除交换。冒泡排序通常是一个“内联”例程（而不是一个“强制”函数调用）。即使它被编码为函数，一个优化良好的编译器也会将其编译成内联代码。如果没有内联，每个排序仍然只有一个函数调用。 然而，快速排序依赖递归，这迫使使用函数调用机制。每次递归循环发生时（从快速排序中调用快速排序），整个环境需要保存在堆栈上。然后执行控制转移。在递归结束时，整个环境需要恢复，并执行另一个控制转移（返回到调用函数）。频繁递归可能会导致非常严重的性能惩罚。我认为，许多人看待快速排序和递归的“优雅”，但忽略了它们的开销。 并不是毫无根据地说这些话，我写了一些基准测试，发现冒泡排序交换更多，但仍然击败了快速排序。 在这些基准测试中，我发现即使是已经“有序”的数据，快速排序也会递归N-1次，其中N是要排序的元素数。

- Robert Casas

---

快速排序不使用递归会更快，对吧？ - John Glen

不确定快速排序的变体是否可以在没有递归的情况下实现 - 我猜它不能，如果可以的话，它将不再是快速排序。 - Robert Casas

更新我的上面的评论：我的基准测试结果表明，当对小数据集进行排序时，冒泡排序胜过快速排序；当对大数据集进行排序时，快速排序胜过冒泡排序（我使用了随机生成的10,000个元素），而qsort（C库）则胜过两者。我猜测qsort C库版本经过高度优化，比自己编译快速排序的默认优化更加优化。 - Robert Casas

Answer 4

那么这里的最坏运行时间是什么？

快速排序：n^2和冒泡排序：n^2

请记住，最坏情况并不总是实际性能的良好指标。 在平均情况下，

快速排序：nlog(n)

冒泡排序：n^2

因此，根据这个结果，快速排序比冒泡排序更快。

然而，在处理退化情况时，快速排序表现较差。 当列表已经接近排序顺序时，快速排序将继续递归。 而冒泡排序完成后会立即停止，使其在这种情况下更快。

- Chanda Korat

Answer 5

数学上，对于所有n>=1，n^2都大于nlog(n)。

因此，冒泡排序{O(n^2)}在n = 9时应该比快速排序{O(nlog n)}慢（来自示例）。

但实际复杂度是：

冒泡排序的大O表示法：n(n-1)等同于O(n^2)

快速排序的大O表示法：O(n(log n))

但由于n=9太小了，n^2和n是可比较的，假设n^2-n等同于n就不正确了。

关于证明：

当n=9时，n^2-n为7.2

当n=9时，n(log n)为8.5，与问题中提到的相同。

- Arpit Sharma

---

当n等于9时，n²-n的值为72，而不是7.2。 - Lew Winczynski

这是错误的。当输入已经完全排序时，快速排序在最坏情况下的时间复杂度为O(n^2)。 - Gabriel

Answer 6

大O符号并不提供一个具体的运行时间，而是对其进行估计。然而，估计可能会根据数组的当前顺序而有所变化。

比较冒泡排序和Arrays.sort算法时，我们需要考虑以下内容:

• Arrays.sort()以最佳、平均或性能的方式运行，时间复杂度为O(n log (n)).
• 冒泡排序的运行时间如下:
• O(n ^ 2)是最坏和平均情况，在最好情况下可达到 O(n)

因此，正在进行排序的数组可能在冒泡排序的最佳性能下工作，从而更快。

- bellotas

Answer 7

首先，尝试在一个更大的数组上进行排序，以便二次复杂度优于对数复杂度。
注意：关于对数复杂度，请注意在快速排序中，log(n)不是log₁₀，而是log₂，因此O(n)应表示为n * lg(n)

其次，没有理由对已排序的数组进行排序...可以尝试这样做：

import numpy as np
arr = np.linspace(-1e3, 1e3, 1e5)
np.random.shuffle(arr)  # Shuffling array preserving the content

如果您的算法不接受numpy数组，请将其转换为列表：
arr_l = list(arr)

- CermakM