線性時間排序？

Question

給定一個在[0..n^3-1]範圍內的n個整數的輸入集合，提供一個線性時間排序算法。

這是我在星期四對測試的評論，我不知道如何解決這個問題。

Answer 1

也看看相關的排序：pigeonhole sort或counting sort，以及Pukku提到的radix sort。

Answer 2

看一看radix sort。

Answer 3

一組有限範圍的數字可以用RANGE位的位圖表示。 在這種情況下，一個500MB的位圖，所以對於除了巨大列表之外的任何東西，使用基數排序會更好。當你遇到數字k時，設置位圖[k] = 1。單遍歷列表O（N）。

Answer 4

這是非常簡單的，如果n = 2和編號是唯一的：

• 構建比特的陣列（2^31-1位=>〜256MB）。將它們初始化爲零。
• 讀取輸入，對於您看到的每個值，將陣列中的相應位設置爲1.
• 掃描陣列，爲每個位設置，輸出相應的值。

複雜性=> O（2N）

否則，使用基數排序：

複雜性=> O（KN）（希望）

Answer 5

wikipedia示出了相當多的不同的排序算法及其複雜性。你可能想要檢查它們

Answer 6

當人們說「排序算法」時，他們經常指的是「比較排序算法」，這是任何算法，只能依賴於能夠問「這個東西是大於還是小於」。所以如果你僅限於詢問關於數據的這個問題，那麼你永遠不會得到超過n * log（n）（這是對數據集的n個階乘可能排序進行log（n）搜索的結果） 。

如果您可以擺脫「比較排序」的限制並詢問關於某個數據的更復雜問題，例如「這個數據的基數是多少」，那麼您可以使用任意數量的線性時間排序算法，他們只需要更多的內存。

這是一個時間空間的折衷。 Comparason排序很少或沒有ram，並在N * log（n）時間運行。基數排序（例如）在O（n）時間和O（log（基數））內存中運行。

Answer 7

一樣ALGO是可能的：

M;// unsorted array 
lngth; //number items of M 
for(int i=0; i < lngth; i++)sorted[M[i]]; 

它單獨用於線性複雜性可能算法中，但它具有複雜度O（K * N）由RAM（N - 數的數組元素中，k - 元素的LEN）

Answer 8

將數字看作三位數字，其中每個數字的範圍從0到n-1。用基數排序將這些數字排序。對於每一位數字都有一個調用計數排序的函數，這個函數需要Theta（n + n）時間，所以總運行時間對應於Theta（n）。