這是一個線性時間排序算法嗎？

-2

我最近寫了一個排序算法。我已經提供了代碼的鏈接以及這裏的一個指導示例：SortingAlgorithm 這是一個線性時間排序算法嗎？

鑑於我的數學背景很少，我很好奇這個算法的有效性。我進行了幾次測試，發現當元素數量增加時，步數以線性方式增加。任何幫助將不勝感激。

2017-03-07 user2540820

它看起來像我可能已經重新創建了桶類。請參閱此處瞭解更多詳情：https：//en.wikipedia.org/wiki/Bucket_sort。請注意，平均情況下的性能是'O（n + k）'（所以它不是線性時間），最壞的情況是'O（n^2）'。請注意，對於桶排序平均爲'O（n）'，桶'n'的數量必須等於被排序數組的長度，並且輸入數組必須在可能的桶值範圍內均勻分佈。如果這些要求不符合，快速排序或其他'O（n日誌n）'排序將擊敗這一點。 –

您的算法似乎需要 O（N）時間統一隨機分佈數據。這並不難，因爲您可以輕鬆地將隨機數據分配到均勻間隔的桶中，並且它們的大小將保持不變。

對於任意數據，它也與O（N）不同，這對於基於比較的排序是不可能的。但是，有限大小的整數的O（N）時間排序是，但可以使用基數排序。參見：https://en.wikipedia.org/wiki/Radix_sort

在簡要地看了你的算法之後，我相信對手可以系統地選擇一個輸入來強制你的算法花費O（N^2）時間。這會讓你成爲O（N^2）算法。

來源

2017-03-07 05:55:49

這是一個線性時間排序算法嗎？

回答

相關問題