你可以在O（n）攤銷複雜性中排序n個整數嗎？

Question

從理論上講，是否可以在一個分期複雜的O（n）中對n個整數數組進行排序？

如何嘗試創建O（n）複雜度的最壞情況？目前大多數算法都是建立在O（nlogn）平均值+ O（n^2）最壞的情況下。 有些使用更多內存時O（nlogn）最差。

你可以沒有限制內存使用創建這樣的算法？ 如果你的記憶力有限，該怎麼辦？這將如何傷害你的算法？

Answer 1

任何網頁上的基於比較的排序will tell you交易的intertubes你不能排序比O(n lg n)更快地比較排序。也就是說，如果你的排序算法通過比較兩個元素來決定順序，你不能做得比這更好。例子包括quicksort，bubblesort，mergesort。

一些算法，如計數排序或桶排序或基數排序不使用比較。相反，它們依賴於數據本身的屬性，如數據中值的範圍或數據值的大小。

那些算法可能有更快的複雜性。下面是一個示例場景：

要排序10^6整數，每個整數是0和10之間。然後你可以計算零，一，二等的數量，並按排序順序將它們吐出。這是如何countort工作，在O(n + m)其中m是您的數據可以採取的值的數量（在這種情況下，m=11）。

另：

要排序10^6二進制字符串的長度均在最5字符。您可以使用基數排序：首先根據它們的第一個字符將它們拆分成2個桶，然後將它們排序爲第二個字符，第三個，第四個和第五個。只要每一步都是穩定的排序，您應該在O(nm)中得到一個完美的排序列表，其中m是您的數據中的位數或位數（在這種情況下爲m=5）。

但在一般情況下，您不能比O(n lg n)可靠排序（使用比較排序）。

Answer 2

我相信你在尋找radix sort。

Answer 3

如果整數在有限的範圍內，那麼對它們進行O（n）「排序」將涉及具有「n」位的位向量......循環所討論的整數並將n％8位該字節數組中的offset n // 8的值爲true。這是一個「O（n）」操作。通過該位陣列的另一個循環來列出/枚舉/返回/打印所有的設置位，同樣是O（n）操作。 （自然O（2n）減少到O（n））。

這是一個特殊情況，其中n足夠小以適應內存或文件（使用seek（））操作）。這不是一個通用的解決方案;但它在Bentley的「程序珍珠」中有所描述---據稱這是解決現實世界問題的一種實際解決方案（涉及諸如電話號碼的「freelist」之類的東西......例如：找到第一個可用的電話號碼發給一個新的用戶）。 （注意：log（10 * 10）是〜24位來表示長度最多爲10位數的每個可能的整數......所以在典型的Unix/Linux最大值中，有大量的空間位於2個 * 31位中大小的內存映射）。

Answer 4

到目前爲止，我對接受的答案並不滿意。所以我正在重試一個答案：

理論上可以在分期複雜的O（n）中對n個整數數組進行排序嗎？

這個問題的答案取決於將執行排序算法的機器。如果你有一個隨機存取機器，它可以正好在1位上運行，你可以對最多k位的整數進行radix sort，這已經被建議了。所以你最終的複雜性爲O(kn)。
但是，如果您使用的字大小至少爲k位（所有消費者計算機都是）的固定大小的字機，則您可以實現的最佳效果是O(n log n)。這是因爲要麼是log n < k，要麼是先執行count sort，然後再用O (n log n)算法進行排序，這也會產生第一種情況。

如何嘗試創建O（n）複雜度的最壞情況？

這是不可能的。已經有一個鏈接。證明的思想是，爲了能夠排序，如果任何要排序的元素大於或小於其他元素，則必須決定要排序的每個元素。通過使用傳遞性，這可以表示爲決策樹，其最多具有n節點和log n深度。所以如果你想要比Ω(n log n)更好的性能，這意味着從決策樹中刪除邊緣。但是，如果決策樹不完整，那麼您如何確保您對某些元素a和b做出了正確的決定？

你可以不限制內存使用量創建這樣的算法嗎？

因此，從上面這是不可能的。因此，其餘問題與此無關。