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

我尝试使用两种算法排序我的列表：冒泡和快速。
为此，我分别使用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

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

来源

2017-10-17 Vladyslav

您的测试数据对于'n^2'来说太小而不重要 – jonatan

，并且以尚未排序的列表开始。 –

因为列表已经排序。快速排序可能会在这种情况下根据如何选择主元素来执行较差的操作。 –

复杂性告诉你哪一个将会是最快的n。我猜n=9太小了，所以在这种情况下，隐藏在O（）中的常量的影响比n^2和n log(n)之间的差异更重要。我建议你用my_list=range(1000)重试。

此外，你必须从随机排序的列表开始。否则（使用标准实现），在已经排序的情况下，气泡排序是O(n)（它最终只验证列表已被排序）

来源

2017-10-17 09:06:29 gdelab

快速排序的最坏情况运行时间是O(n^2)。最糟糕的情况取决于枢轴选择策略，通常它发生在已经排序的数组（您的数组）上。另外，对于小数据集，冒泡排序或其他简单排序算法通常比更复杂的算法运行得更快。原因在于，对于每次迭代，简单算法都比复杂算法少计算。

例如，气泡排序每次迭代需要3ms，而快速排序需要20ms。因此对于具有10项目的阵列。

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

并且快速排序需要10*log2(10)*20 = 664ms。

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

来源

2017-10-17 09:13:35 shawon191

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

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

记住，最坏的情况并非总是真实世界中的性能的良好指标。在一般情况下，

快速排序：nlog(n)

冒泡：n^2

所以在此基础上，快速排序比冒泡快。

但是，Quicksort很难处理退化病例。当列表已经几乎排序时，Quicksort将继续递归。Bubblesort会在完成后立即停止，使Bubblesort在这种情况下更快。

来源

2017-10-17 09:14:13

首先，尝试对更大阵列进行排序，以便二次复杂度优先于对数复杂度。
注：关于对数的复杂性，要注意的是，的log（n）尽可能快速排序来讲，是不是日志，这是日志 - >Ø （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)

来源

2017-10-17 09:53:13 CermakM

数学N^2比n日志（N）越大所有n > = 1.

因此，对于n = 9（来自示例），冒泡排序{O（n^2）}应该比快速排序{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^2-n，用于N = 9是7.2

N（log n）的对于n = 9是8.5 这是相同的问题提。

来源

2017-10-17 10:29:34

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

回答

相关问题