什麼是少數整數最快的排序算法？

Question

我想知道最快的算法是什麼。我有0到3000之間的8個整數，我需要對它們進行排序。雖然只有8個整數，但這個操作將執行數百萬次。

Answer 1

對於只有8個整數，並且由於範圍遠大於8，插入排序可能是最好的。嘗試一開始，如果分析表明它不是瓶頸，那就離開它。 （根據許多因素，快速排序比插入排序更好的截止點通常在5到10個項目之間）。

Answer 2

最快的方法是簡單地編寫大量的if語句來比較它們以確定它們的確切順序。這將消除任何排序算法的開銷。

Answer 3

比較排序算法的一個很好的來源是http://www.sorting-algorithms.com/。 請注意，即使是初始訂單狀態也會影響結果。但無論如何，對於8個整數，即使是普通的泡沫排序也應該完成這項工作。

Answer 4

最快的方法是用硬件實現的sorting network。除此之外，最快的方式只能通過測量來確定。我想嘗試

• std::sort，
• 鴿籠（桶）排序與桶的再利用，
• 一堆if語句和
• 插入排序

的順序，因爲它是最簡單最難的命令（嘗試第一次正確插入排序......），直到找到一個可以維護的東西，一旦常數八的值變爲9。

另外，氣泡排序，選擇應該和shell排序值得注意。我從來沒有實際執行過這些，因爲他們的代表不好，但你可以嘗試。

Answer 5

爲正整數，最快的排序被稱爲算盤排序 - 這是爲O（n）

http://en.wikipedia.org/wiki/Abacus_sort

如果只有極少數的項目，那麼它是不可能的，你會發現任何性能差異從選擇任何特定的算法。

Answer 6

以下引用來自賓利等人。，工程排序功能可能是有趣的位置：

到插入排序各種改進，包括二進制搜索，循環展開，並處理N = 2作爲一個特殊的情況下，是沒有幫助的。 最簡單的代碼是最快的。

（重點煤礦。）

這表明，沒有花哨的修飾平原插入排序確實是一個很好的起點。正如彼得所指出的那樣，八個項目確實有點棘手，因爲它正好在通常標記插入排序和快速排序之間的切斷範圍內。

Answer 7

對於非常少量的整數，冒泡排序可以非常快。使用數值比較的泡泡排序可以用非常低的開銷寫入，對於小的n，O（n log n）和O（n^2）之間的實際速度差異被清除。

Answer 8

下面是一個奇偶合並排序網絡的C99實現（抱歉「錯誤」的語言）：

#define CMP_SWAP(i, j) if (a[i] > a[j])    \ 
    { int tmp = a[i]; a[i] = a[j]; a[j] = tmp; } 

void sort8_network(int *a) 
{ 
    CMP_SWAP(0, 1); CMP_SWAP(2, 3); CMP_SWAP(4, 5); CMP_SWAP(6, 7); 
    CMP_SWAP(0, 2); CMP_SWAP(1, 3); CMP_SWAP(4, 6); CMP_SWAP(5, 7); 
    CMP_SWAP(1, 2); CMP_SWAP(5, 6); CMP_SWAP(0, 4); CMP_SWAP(1, 5); 
    CMP_SWAP(2, 6); CMP_SWAP(3, 7); CMP_SWAP(2, 4); CMP_SWAP(3, 5); 
    CMP_SWAP(1, 2); CMP_SWAP(3, 4); CMP_SWAP(5, 6); 
} 

我計時它在我的機器上對插入排序

void sort8_insertion(int *a) 
{ 
    for (int i = 1; i < 8; i++) 
    { 
     int tmp = a[i]; 
     int j = i; 
     for (; j && tmp < a[j - 1]; --j) 
      a[j] = a[j - 1]; 
     a[j] = tmp; 
    } 
} 

對於大約1000萬種（正好是所有40320個可能排列的250倍），排序網絡花費了0.39秒，而插入排序花費了0.88秒。對我來說似乎足夠快。 （這些數字約爲0.04秒，用於生成置換。）

Answer 9

您是否已經對您的代碼進行了分析以顯示排序是瓶頸？如果它不是瓶頸，那麼加速它不會給你帶來太多的收益。排序八個短整數非常快。

一般來說，除非你是一個真正的排序專家，否則std :: sort（）會比你寫的任何東西都快。

Answer 10

我對{0,429,857,1286,1714,2143,2571,3000}的所有排列運行了排序算法庫。

最快的分別爲：

name        time stable in-place 
AddressSort       0.537 No  No 
CenteredLinearInsertionSort   0.621 Yes  No 
CenteredBinaryInsertionSort   0.634 Yes  No 
BinaryInsertionSort     0.639 Yes  Yes 
... 
QuickSort       0.650 No  Yes 
... 
BubbleSort       0.802 Yes  Yes 

更多關於AddressSort看到http://portal.acm.org/citation.cfm?id=320834

Answer 11

對於整數，你可以嘗試基數排序。這是O（N）。

Answer 12

年以後）最多32個輸入， 請參閱Sorting network generator。 對於8路輸入，它使19個互換，像斯文Marnach的回答是：

o--^--^--------^--------------------------o 
    | |  | 
o--v--|--^--^--|--^--^--------------------o 
     | | | | | | 
o--^--v--|--v--|--|--|--^--------^--------o 
    |  |  | | | |  | 
o--v-----v-----|--|--|--|--^--^--|--^--^--o 
       | | | | | | | | | 
o--^--^--------v--|--v--|--|--|--v--|--v--o 
    | |   |  | | |  | 
o--v--|--^--^-----v-----|--|--|-----v-----o 
     | | |   | | | 
o--^--v--|--v-----------v--|--v-----------o 
    |  |     | 
o--v-----v-----------------v--------------o 


There are 19 comparators in this network, 
grouped into 7 parallel operations. 

[[0,1],[2,3],[4,5],[6,7]] 
[[0,2],[1,3],[4,6],[5,7]] 
[[1,2],[5,6],[0,4],[3,7]] 
[[1,5],[2,6]] 
[[1,4],[3,6]] 
[[2,4],[3,5]] 
[[3,4]]