我正在探索下面的算法：這些非比較排序在什麼條件下以線性時間運行？
我知道所有這三個能夠在最好的情況下以線性時間運行的，但我除了計數排序的情況之外，在發生這些情況時，我很難理解。
這是我計算的體悟，以及如何我想對於其他兩種算法，如果可能的答案：
計數排序運行線性時間時，有你想成爲信息之間沒有很大的差距排序。例如1,10^5和545等會創建一個大數組，並且使用內存和遍歷效率不高，所以這將是使用計數排序的「更壞的情況」，因此最好的情況是當差距很小。
如果任何人都可以幫助我理解線性時間發生時radix和bucket排序最佳情況的條件，我將不勝感激。
讓我們先獨立分析每個算法，看看我們能否確定它們在什麼情況下會以線性時間運行。
首先，讓我們看看計數排序。該算法的工作原理如下：
第一步可以通過遍歷主數組在O（n）時間完成。我們假設數組中的最大值是U.在這種情況下，第二步需要花費時間O（U），因爲我們必須將數組元素歸零。第三步需要時間O（n）。最後一步需要花費時間O（n + U），因爲我們只訪問一次頻率數組中的每個元素（O（U）），並且對輸出數組O（n）進行總共n次寫入。這意味着總運行時間爲O（n + U）。請注意，這取決於需要排序的元素總數（較大的數組需要較長的排序時間）以及數組中元素的大小（更大的數字將需要相應更多的運行時間）。
如果我們希望這個運行時間是O（n），我們需要U = O（n）。那樣的話，我們會有O（n + U）= O（n + n）= O（n）。這意味着您需要使陣列中最大元素的大小與陣列長度增加時的大小相同。例如，如果確保數組中的所有元素都在1 .. n範圍內，則計數排序將花費時間O（n）完成。這些元素如何在該範圍內分佈並不重要。
基數排序基本工作原理是反覆做計數排序一遍又一遍，一旦陣列中的號碼中的各個數字進行排序。基數排序的關鍵思想是儘可能降低先前算法的U值。通過選擇一些固定基地，U的價值被限制在一定的水平。例如，如果您使用二進制基數排序並每次執行一位，則要排序的數組中的每個元素基本上都被視爲0或1。這意味着每一輪基數排序都需要O（ n）完成。對整個數組進行排序所需的回合數然後由數組中最大數字的位數給出，即Θ（log U）。這意味着算法的總運行時間結束爲O（n日誌U）。再次注意，運行時間取決於元素的數量和數組中最大元素的大小。
優點這個時間被用來記錄ü生長多少，比慢得多U.例如，2 爲約原子在宇宙中的總數，但LG（2 ）= 300，這是相當小的。
有些人會說任何固定電腦上的日誌U都是一個常數。在32位計算機上，所有整數都是32位（除非您使用的是任意精度整數庫，現在我們將忽略），而在64位系統上，所有整數都是64位。在第一種情況下，記錄U = 32，在第二個記錄U = 64中。您可以聲稱對於固定系統，基數排序總是需要線性時間，因爲運行時間將是O（n）。不過，這個常數在系統中各不相同。如果你更理論上想要更精確，那麼只要log U = O（1），就可以說基數排序以線性時間運行，因爲O（n log U）= O（n）。這意味着如果數字中的位數有任何常數的上限，則保證基數排序將以線性時間運行。
的桶排序算法類似於排序沙蔘，不同之處在於它採用了最顯著位而不是至少顯著位分配元件。這意味着分析結果與以前幾乎相同 - 只要log U = O（1），該算法在線性時間內運行。
希望這有助於！
精彩的答案！非常感謝！ – ZAX
基數IIRC始終是線性的，但常數因子是最大整數中的位數。所以32位基數排序在數據上以32個直線傳遞運行。對於N <2^32，類似mergesort的N lg N排序會更快。 –
當你說「線性時間」時，你想要線性化的參數是什麼？元素的數量？最大值中的位數？總位數？ – templatetypedef
@templatetypedef我正在談論算法的運行時間。正如法官所說，是的，他們都是線性時間，但我想知道什麼時候最優情況下，運行時間明智的 – ZAX