在線性時間對[log n]個不同的值進行排序

Question

我有一個n個整數的數組，它只能假設爲log n可能的值（以及任何值）。例如，在S = [349,12,12,283,349,283,283,12]中，只有3個不同的號碼(log 8 = 3)。我不得不在O(nlogn)以下的時間排序這個數組。我應該使用哪種算法？也許基數排序與計數排序？它的分析呢？

Answer 1

既然是因爲將只有log(n)獨特的元素，你可以使用下面的算法O(n)時間獲得排序列表：

1. 創建列表中存在多少不同項目的映射，並保持每個項目的計數（基本上是密鑰的字典/散列圖，計數）
   • 這是對輸入列表的單次迭代，因此O(n)步驟。
2. 根據它們的關鍵字對上面的大小爲log(n)的元組列表進行排序。
   • 假設我們使用合併排序，那麼合併排序的時間複雜度爲k*log(k)，其中k是輸入的大小。
   • 用log(n)代替k，我們得到這一步的複雜度爲O(log(n)*log(log(n)))。
   • 由於複雜性方面，O(log(n)*log(log(n))) < O(n)，所以到此步驟爲止的整體複雜度爲O(n) + O(log(n)*log(log(n)))，相當於O(n)。
3. 對已排序的鍵進行迭代，並使用單個for循環生成排序列表，其中每個值按其計數重複。這裏會有最多的迭代。

因此，總體而言，上述算法將在O（n）時間內運行。

Answer 2

基數排序複雜度爲O(dn)，其中d爲數字中的位數。

只有在d是恆定的情況下，該算法才能以線性時間運行！在你的情況d = 3log（n）和你的算法將運行在O(nlog(n))。

我真的不知道如何在線性時間解決這個問題。是否有任何其他關於數字性質的信息我想知道是否有任何其他關於數字性質的信息缺失...

那麼，這裏是一個MSD基數排序的簡單實現脫氧核糖核酸。它是用D語言編寫的，因爲這是我使用最多的語言，因此最不可能犯下愚蠢的錯誤，但它很容易被翻譯成其他語言。它在原地，但需要2 * seq.length穿過陣列。

void radixSort(string[] seqs, size_t base = 0) { 
    if(seqs.length == 0) 
     return; 

    size_t TPos = seqs.length, APos = 0; 
    size_t i = 0; 
    while(i < TPos) { 
     if(seqs[i][base] == 'A') { 
      swap(seqs[i], seqs[APos++]); 
      i++; 
     } 
     else if(seqs[i][base] == 'T') { 
      swap(seqs[i], seqs[--TPos]); 
     } else i++; 
    } 

    i = APos; 
    size_t CPos = APos; 
    while(i < TPos) { 
     if(seqs[i][base] == 'C') { 
      swap(seqs[i], seqs[CPos++]); 
     } 
     i++; 
    } 
    if(base < seqs[0].length - 1) { 
     radixSort(seqs[0..APos], base + 1); 
     radixSort(seqs[APos..CPos], base + 1); 
     radixSort(seqs[CPos..TPos], base + 1); 
     radixSort(seqs[TPos..seqs.length], base + 1); 
    } 
} 

很明顯，這是DNA的特定種類，而不是一般的，但它應該是快速的。

編輯：我很好奇這個代碼是否真正起作用，所以我在等待我自己的生物信息學代碼運行時進行了測試/調試。現在上面的版本實際上已經過測試和工作。對於每個1000萬個5鹼基的序列，它比優化的introsort快約3倍。

讓我們看看連接例如與兩位十進制數：

49, 25, 19, 27, 87, 67, 22, 90, 47, 91 

由第一位產量

19, 25, 27, 22, 49, 47, 67, 87, 90, 91 

下一頁排序，你按第二個數字，生成

90, 91, 22, 25, 27, 47, 67, 87, 19, 49 

似乎錯了，不是嗎？或者這不是你在做什麼？如果我弄錯了，也許你可以告訴我們代碼。

如果您對具有相同第一位數字的所有組執行第二種排序，則您的算法將等同於遞歸版本。它也會保持穩定。唯一的區別是你會按照廣度優先而不是深度優先的方式進行排序。

UPDATE

檢查這個答案：sort O(nlogn)

Answer 3

1. 計算列表中每個元素的數量（使用哈希表）（時間：O（n））。
2. 取消複製列表（時間：O（n））。
3. 排序現在被盜用的項目（時間：O（log n * log log n））。
4. 建立一個列表，每個項目的正確份數（時間：O（n））。

總的來說，這是O（n），易於實現。

下面是一些Python實現這一點：

def duplicates_sort(xs): 
    keys = collections.Counter(xs) 
    result = [] 
    for k in sorted(keys): 
     result.extend([k] * keys[k]) 
    return result