是std ::排序的最佳選擇，就地排序一個有限整數值的巨大數組？

Question

我想排序一個巨大（數百萬甚至數十億）元素的數組，而值是小範圍內的整數（1到100或1到1000），在這種情況下，是std::sort和並行版本__gnu_parallel::sort對我最好的選擇？

實際上我想用一個代表處理器索引的整數成員對我自己類的vecotor進行排序。

由於類內部還有其他成員，因此，即使兩個數據具有相同的整數成員用於比較，它們也可能不會被視爲相同的數據。

Answer 1

如果您知道您的範圍如此有限，則計數排序將是正確的選擇。如果範圍是[0,m)這是最有效的方法，那麼它有一個vector，其中索引代表元素，值代表計數。例如：

vector<int> to_sort; 
vector<int> counts; 
for (int i : to_sort) { 
    if (counts.size() < i) { 
    counts.resize(i+1, 0); 
    } 
    counts[i]++; 
} 

注意，在i計數延遲初始化，但如果你知道m你可以調整一次。

如果要排序有些外地的對象，他們都是不同的，你可以修改上面：

vector<T> to_sort; 
vector<vector<const T*>> count_sorted; 
for (const T& t : to_sort) { 
    const int i = t.sort_field() 
    if (count_sorted.size() < i) { 
    count_sorted.resize(i+1, {}); 
    } 
    count_sorted[i].push_back(&t); 
} 

現在主要的區別是，你的空間需求的增長顯着，因爲你需要存儲的矢量的指針。空間複雜度從O(m)變爲O(n)。時間複雜度是相同的。請注意，該算法是穩定的。上面的代碼假設在count_sorted的生命週期中to_sort處於範圍內。如果您的T實現移動語義，您可以自己存儲對象並將它們移入。如果您需要count_sorted以超過to_sort，則需要這樣做或進行復制。

如果您有一系列[-l, m)型的，實質並沒有太大變化，但你的指數目前代表的價值i + l，你需要知道l提前。

最後，通過迭代遍歷counts數組考慮計數值來模擬迭代排序數組應該是微不足道的。如果你想像stl這樣的迭代器，你可能需要一個封裝了這種行爲的自定義數據結構。

注：在此答案的前一版本中我提到multiset作爲一種使用數據結構來計數排序的方法。這在一些java實現中是有效的（我相信Guava實現會很有效），但是在C++中不是這樣，其中RB樹中的密鑰只是重複了很多次。

Answer 2

Giovanni Botta給出的答案非常完美，Counting Sort絕對是您的選擇。不過，我個人不喜歡去逐步調整的載體，但我寧願做這樣（假設你的取值範圍爲[0-1000]）：

vector<int> to_sort; 
vector<int> counts(1001); 
int maxvalue=0; 
for (int i : to_sort) { 
    if(i > maxvalue) maxvalue = i; 
    counts[i]++; 
} 
counts.resize(maxvalue+1); 

它在本質上是相同的，但沒必要要不斷管理counts矢量的大小。根據您的內存限制，您可以使用一種解決方案或其他解決方案。

Answer 3

你說「in-place」，因此我假設你不想使用O（n）額外的內存。

首先，計算每個值的對象數量（如在Gionvanni和羅納爾多的答案中）。您仍然需要將對象原位置入正確的位置。我認爲以下工作，但我沒有實施或測試它：

從您的計數中創建一個累計總和，以便您知道每個對象需要去哪個索引。例如，如果計數爲1: 3, 2: 5, 3: 7，則累計和爲1: 0, 2: 3, 3: 8, 4: 15，這意味着最終數組中的值爲1的第一個對象將位於索引0處，具有值2的第一個對象位於索引3處，依此類推。

現在的基本想法是從頭開始通過矢量。獲取元素的處理器索引，並查找相應的累計和。這是你想要的地方。如果它已經在該位置，則移動到矢量的下一個元素並遞增累加和（以便具有該值的下一個對象沿着下一個位置移動）。如果它尚未位於正確的位置，請將其與正確的位置交換，然後遞增累計總和，然後繼續對換入該位置的元素進行處理。

當您到達已移動到位的元素塊的開始處時，存在潛在的問題。您可以通過記住原始累積金額來解決這個問題，當您到達某個金額時「注意到」，並跳到當前累計金額，以便您不會重新訪問已換入的任何元素。可能有一個更聰明的方法來處理這個問題，但我不知道。

最後，將代碼的性能（和正確性！）與std::sort進行比較。這比std::sort的時間複雜度更好，但這並不意味着它對於實際數據的速度必然更快。

Answer 4

對於品種，map方便進行實際的排序，但它不會是最有效的：

std::map counts<int, int>; 
for(auto x : bigcontainer) { 
    counts[x] += 1; 
}