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

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) 排序算法。