对一个只有3个元素的由100个整数组成的数组进行排序

Question

假设我有一个包含100个数字的数组。数组中唯一的不同值是1,2和3。这些值在数组中随机排序。例如，数组可能被填充为：

int values[100];

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

如何高效地对类似这样的数组进行排序？

- ExploringApple

---

投票关闭 - 数组本质上是连续的 - 听起来像是作业。 - Adrian Cornish

@Adrian：我的意思是说它们没有连续的索引位置。 - ExploringApple

@AdrianCornish：我不同意。这是一个完全合理的问题。只是OP表达得有些奇怪。 - Mike Bailey

这是我读到的面试问题之一。顺便说一下，Mike已经更改了确切的查询。问题是：对具有3个填充数字的元素和其他位置未初始化或具有段数组的100个元素进行排序。 - ExploringApple

@MikeBantegui 在你的编程职业生涯中，你是否曾被要求解决过类似这样的问题 - 明显是人为制造的。 - Adrian Cornish

我假设你不知道这些数字的位置，但你能从未初始化的内存中识别出它们（我不会问你是怎么做到的）。那么以下三个步骤有什么问题呢？1）查找这三个数字（O(n)），2）排序它们（O(1)并且可以忽略不计），3）将它们放入[0]，[1]，[2]中。 - Beta

Answer 1

最快的解决方案是根本不需要“排序”：

• 遍历数组并统计1、2和3的出现次数。这些计数希望能适合寄存器...
• 使用正确数量的1、2和3填充数组，覆盖已经存在的任何内容。

最后你将得到一个完全排序的数组。

通常情况下，当待排序数值的可能取值范围远小于数组大小时，这可以成为一种有用的O(n)排序算法。

- mikera

---

这被称为桶排序，如果你想进一步了解，它是基数排序中最简单的形式。 - Pete Fordham

@mikera：我的数组并不全都是值为1、2、3的。在100个元素的数组中，只有3个元素被初始化，其余字段未初始化或者可以说它们包含了一些垃圾值或者段落。 - ExploringApple

@ExploringApple - 如果您忽略未初始化的值，该技术仍将起作用。但是，如果您知道您只有1、2和3中的每个数字，则甚至不需要计算它们 - 只需将1、2和3输出到数组的前三个元素即可。 - mikera

@PeteFordham：我认为这是“计数排序”，它是桶排序的最简形式，而桶排序是基数排序的一种形式。 - Mooing Duck

什么？数组包含未初始化的值？这使得精确解决方案变得不可能。 - usr

Answer 2

荷兰国旗算法是常被引用的算法，实际上是快速排序的变体中的分区步骤（1表示小于，2表示等于，3表示大于）。在这个变体中，你不需要对中间部分进行排序。

- C A R Whore