排序一个由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

回答