k个数字和N个元素的最快排序方法，k <<< N

Question

问题：有n个球，标记为0、1、2，顺序乱，我想从小到大排序。球：

1, 2, 0, 1, 1, 2, 2, 0, 1, 2, ...

一定要用最快的方式来解决，不能用sort()函数，我想了很多办法，比如冒泡排序，插入排序等等，但是速度不快。是否有一种算法使时间复杂度为 O(logn) 或 O(n)？

给定的球列表 A[] 和长度 n

void sortBalls(int A[], int n)
{
 //code here
}

Answer 1

鉴于项目类型（0、1和2）的数量非常有限，您只需计算每种类型的出现次数。然后打印“排序”数组，你重复打印每个标签出现的次数。运行时间是O(N)

int balls[N] = {...};  // array of balls: initialized to whatever
int sorted_balls[N];   // sorted array of balls (to be set below)
int counts[3] = {};    //   count of each label, zero initialized array.

// enumerate over the input array and count each label's occurance
for (int i = 0; i < N; i++)
{
    counts[balls[i]]++;
}

// sort the items by just printing each label the number of times it was counted above
int k = 0;
for (int j = 0; j < 3; j++)
{
    for (int x = 0; x < counts[j]; x++)
    {
        cout << j << ", ";   // print
        sorted_balls[k] = j; // store into the final sorted array
        k++;
    }
}