爲什麼冒泡排序比快速排序快

我嘗試使用兩種算法排序我的列表：冒泡和快速。
爲此，我分別使用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

爲什麼冒泡排序比快速排序快

回答

相關問題