c++ - 对包含 100 个元素的整数数组进行排序，其中只有 3 个元素

Question

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

int values[100];

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

我怎样才能有效地对这样的数组进行排序？

Answer 1

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

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

最后，您将拥有一个完全排序的数组。

通常，当与数组大小相比，可能值的范围非常小时，这可能是一种有用的 O(n) 排序算法。

Answer 2

荷兰国旗算法是常用的算法，实际上是快速排序变体之一中的分区步骤（1 对应于小于，2 对应于，3 对应于大于）。在该变体中，您不需要对中间部分进行排序。