在O（n）時間和O（1）額外內存中排序1000萬個對象

Question

我試圖找到最近得到的面試問題的答案，但無法解決。我被要求使用O（1）空間和O（n）時間按10位整數排序1000萬個對象（每個對象包含一個10位整數和一個唯一的字符串值）。對於所有密集的目的，字符串值只會讓問題變得更加困難，但是您不會通過它對對象進行排序。

但是，我想使用計數排序，只有當我正在對10位整數進行排序時纔有效。對對象排序使事情變得更復雜一些，因爲我需要跟蹤它們唯一的字符串值。我看着基數排序，但它似乎使用O（n）作爲最壞的情況。

是否有某種我缺少的種類？

Answer 1

There's an in-place (MSB) radix sort。

它是這樣的：

• 開始與第一位。

• 將該位爲0的所有元素移動到左側
  以及所有那些位等於1的元素向右移動。

  您可以通過從兩側移動到中間來執行類似於快速排序的操作，將左側的1與右側的0交換。

• 考慮下一個位，在左側和右側遞進。

的過程是這樣的：

 ↓    ↓ 
     0...    1... 
--------------- --------------- 
    ↓  ↓  ↓  ↓ 
00... 01... 10... 11... 
------- ------- ------- ------- 
↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ 
000 001 010 011 101 110 110 111 
--- --- --- --- --- --- --- --- 
... 

時間複雜度爲O(bits*n)和空間複雜度爲O(bits)。

因此，對於恆定的比特數，時間複雜度爲O(n)，空間複雜度爲O(1)。

---

---

它也可以做到這一點使用計數排序（具有相同的時間和空間複雜度）。

• 計算每個元素有多少個。
• 使用這個，你可以確定這些元素應該出現在數組中的什麼位置。

• 創建一個包含所有上述起點的查找表（映射索引到偏移量，可以是一個數組），它將用於確定下一個元素應該到哪裏。

• 現在您遍歷數組並將每個不合適的元素交換到它可以到達的第一個位置，然後對每個我們交換的元素執行相同操作，直到當前元素屬於它的位置。

  在每個步驟中增加查找表中相關元素的偏移量。

  請注意，不可能將相同元素交換兩次，因此這將是線性時間。

這聽起來都非常混亂，所以這裏有一個例子：

4 5 3 1 2 3 4 4 1 5 4 3 2 3 

// counts: 
1: 2, 2: 2, 3: 4, 4: 4, 5: 2 

// the starting points (offsets) based on the counts: 
1 at position 0 
2 at position (offset of 1)+(count of 1) = 0+2 = 2 
3 at position (offset of 2)+(count of 2) = 2+2 = 4 
4 at position (offset of 3)+(count of 3) = 4+4 = 8 
5 at position (offset of 4)+(count of 4) = 8+4 = 12 

// sorting: 
4 5 3 1 2 3 4 4 1 5 4 3 2 3 // out of place, swap with offsets[4] = 8 (offsets[4]++) 
^ 

1 5 3 1 2 3 4 4 4 5 4 3 2 3 // in correct position, moving on   (offsets[1]++) 
^ 

1 5 3 1 2 3 4 4 4 5 4 3 2 3 // swap with offsets[5] = 12    (offsets[5]++) 
^

1 2 3 1 2 3 4 4 4 5 4 3 5 3 // swap with offsets[2] = 2    (offsets[2]++) 
^

1 3 2 1 2 3 4 4 4 5 4 3 5 3 // swap with offsets[3] = 4    (offsets[3]++) 
^

1 2 2 1 3 3 4 4 4 5 4 3 5 3 // swap with offsets[2] = 3    (offsets[2]++) 
^

1 1 2 2 3 3 4 4 4 5 4 3 5 3 // in correct position, moving on   (offsets[1]++) 
^

1 1 2 2 3 3 4 4 4 5 4 3 5 3 // in correct position, moving on   (offsets[2]++) 
    ^

你的想法...

需要注意的是伯爵表的大小和查詢表是O(max value)如果每個數字包含固定數量的比特，則這是O(1)。

而且你爲每個元素做了一個恆定的工作量，所以這是O(n)時間。

Answer 2

可以使用標準快速排序數據透視代碼將所有具有整數0的項目移動到數組的開頭。在剩下的元素上繼續1,2,3，等等，一旦你在1023上旋轉，就停下來。

這遍歷數組1024次，每個主軸都需要O（n）個時間，所以是上）。

在實踐中更加高效的一種非常相似的方法就是使用標準的三路快速排序算法。通常人們會認爲這需要O（n log n）時間，並且在最壞的情況下使用O（log n）空間。但是在這裏，整數域被限制爲1024個值，所以保證在O（n）時間內完成並使用O（1）空間，因爲在每次遞歸調用快速排序時，樞軸值永遠不會被使用兩次。

[這個答案做了一個假設 - 在問題中「1000萬」是n，而「10位」保持不變]。