殼牌排序比泡泡排序快3倍？

我已經在C中實現了Shell排序，並且它比Bubble排序快了約3倍。這裏是我整理的持續時間（秒）：殼牌排序比泡泡排序快3倍？

For list of 100 integers: 
BubbleSort: 0.000333 
ShakeSort: 0.000282 
QuickSort: 0.000048 
QuickSort_Iter: 0.000063 
InsertionSort: 0.000188 
ShellSort: 0.000150 

For list of 1000 integers: 
BubbleSort: 0.028191 
ShakeSort: 0.019354 
QuickSort: 0.000435 
QuickSort_Iter: 0.000528 
InsertionSort: 0.011917 
ShellSort: 0.003664 

For list of 5000 integers: 
BubbleSort: 0.241116 
ShakeSort: 0.222127 
QuickSort: 0.001306 
QuickSort_Iter: 0.001592 
InsertionSort: 0.151656 
ShellSort: 0.091002 

For list of 10000 integers: 
BubbleSort: 0.959580 
ShakeSort: 0.872648 
QuickSort: 0.002877 
QuickSort_Iter: 0.003379 
InsertionSort: 0.601329 
ShellSort: 0.350866

這是正常的或者是有可能與我的執行出了問題？

來源

2016-07-23 LynnXe

它巨大取決於你的數據集 – Jcl

它是基於陣列的矢量僞隨機整數0-999。我只是想知道，在任何情況下它是否在所有合理性能的情況下適用於殼牌排序 – LynnXe

沒有任何「任何」條件。條件真的很重要......想象一下，除了第一個和最後一個被交換的數字之外，還有一個完全排序的數組數組：在這種情況下，shell排序可能比冒泡排序更快（因爲它可以進行一次交換，而冒泡排序將不得不交換所有數字）......但這只是一個邊緣情況：它並不意味着冒泡排序比shell排序更慢或更快，它只意味着針對特定數據集。大O中的'n'很重要，很多:-) – Jcl

我有一個排序基準測試程序，內置4個shell排序和冒泡排序。四個變體中的三個具有類似的計時屬性;第四個比其他三個要糟得多。然而，當排序大小爲1000時，3個shell的排序小於100μs，而慢速的排序小於600μs，並且氣泡排序小於900μs，但是在10,000的大小，時間在1-2ms與70ms與142ms之間變化，大小爲10萬，時間在14-30ms之間變化，而8.6s和18s之間變化。因此，其中一種貝殼類型的速度大約是氣泡類速度的一半，但其他類型則更好。 - 喬納森·萊弗勒

好吧，我改的實施，使用插入排序邏輯期間希爾排序，所以現在性能達到子向量進行排序 - LynnXe

來源

2016-08-05 06:32:15 Armali

殼牌排序比泡泡排序快3倍？

回答

相關問題