排序中「少數獨特」的含義是什麼？

Question

全部。

http://www.sorting-algorithms.com/quick-sort-3-way

在上述網站，快速排序3路分區算法，我發現4不同的情況。 我明白隨機，幾乎排序，顛倒的情況。 但是，「少數獨特」是什麼？它意味着大整數鍵？ 您能否詳細說明一下？ 謝謝。

Answer 1

在這種情況下，我想一些獨特的手段：即使你有一個巨大的數組，可能的值的集合是非常小的。這也意味着有很多重複。

例如：3,10,50,10,10,3,10,3,50,3,50,50，3,10,10,50,3,3,10,50,50,35。 ..

即使數據收集很大，一組不同的/唯一的值是{3, 10, 50}，非常小。

如果要排序的數組，你可以簡單地做一個掃描，你算值的出現次數：

3 : 8 occurences 
10: 7 occurences 
50: 7 occurences 

然後排序很簡單：只是把3次「8」，7倍'10 '和7次'50'。如果你有其他的專欄，僅僅統計出現次數還不夠，你必須建立一個索引，但這個想法是一樣的。