排序一個由100個元素組成的整數數組，其中只有3個元素

假設我有一個由100個數組組成的數組。數組中唯一不同的值是1,2和3.這些值在整個數組中隨機排序。例如，該陣列可能填充爲：排序一個由100個元素組成的整數數組，其中只有3個元素

int values[100]; 

for (int i = 0; i < 100; i++) 
    values[i] = 1 + rand() % 3;

如何有效地對這樣的數組進行排序？

投票關閉 - 數組本身是連續的 - 聽起來像作業 –

@阿德里安：我的意思是說沒有放在連續索引位置 – ExploringApple

@AdrianCornish：我會不同意。這是一個完全合法的問題。 OP只是表達了奇怪的意思。 –

最快的解決方案是不是「那種」不惜一切：通過數組

最後你會有一個完全排序的數組。

一般來說，如果與數組的大小相比，可能值的範圍很小，則這可能是一種有用的O（n）排序算法。

2012-09-16 02:53:59 mikera

如果您對某些進一步閱讀感興趣，這稱爲桶排序並且是基數排序的最簡單形式。 –

@mikera：我沒有具有值1,2,3的所有數組。在100的數組中，它只有3個元素被初始化，剩餘字段未初始化，或者你可以說它有段或任何垃圾值。 – ExploringApple

@ExploringApple - 如果忽略未初始化的值，該技術仍然可以工作。但是如果你知道你只有1,2和3中的每一個，那麼你甚至不需要對它們進行計數 - 只需將1,2和3輸出到數組的前三個元素即可。 – mikera

Dutch National flag algorithm是這方面的常用算法，實際上是quicksort變體之一的分區步驟（1對應於小於2，等於3和大於）。在該變體中，您不需要對中間部分進行排序。

2012-09-16 15:40:08

回答