arrays - 排序:如何对包含 3 种数字的数组进行排序

Question

例如:int A[] = {3,2,1,2,3,2,1,3,1,2,3};

如何有效地对这个数组进行排序？

这是为了求职面试，我只需要一个伪代码。

Answer 1

如何排序的有前途的方式似乎是 counting sort 。值得一看this lecture由理查德·巴克兰 (Richard Buckland) 撰写，尤其是 15:20 的部分。

类似于计数排序，但更好的方法是创建一个表示域的数组，将其所有元素初始化为 0，然后遍历数组并对这些值进行计数。一旦知道域值的这些计数，就可以相应地重写数组的值。这种算法的复杂度为 O(n)。

这是具有我描述的行为的 C++ 代码。但它的复杂度实际上是 O(2n):

int A[] = {3,2,1,2,3,2,1,3,1,2,3};
int domain[4] = {0};

// count occurrences of domain values - O(n):  
int size = sizeof(A) / sizeof(int);
for (int i = 0; i < size; ++i)
    domain[A[i]]++;

// rewrite values of the array A accordingly - O(n):    
for (int k = 0, i = 1; i < 4; ++i)
    for (int j = 0; j < domain[i]; ++j)
        A[k++] = i;

请注意，如果域值之间存在很大差异，则将域存储为数组是低效的。在这种情况下，最好使用 map (感谢 abhinav 指出)。这是使用 std::map 的 C++ 代码用于存储域值 - 出现次数对:

int A[] = {2000,10000,7,10000,10000,2000,10000,7,7,10000};
std::map<int, int> domain;

// count occurrences of domain values:  
int size = sizeof(A) / sizeof(int);
for (int i = 0; i < size; ++i)
{
    std::map<int, int>::iterator keyItr = domain.lower_bound(A[i]);
    if (keyItr != domain.end() && !domain.key_comp()(A[i], keyItr->first))
        keyItr->second++; // next occurrence 
    else
        domain.insert(keyItr, std::pair<int,int>(A[i],1)); // first occurrence
}

// rewrite values of the array A accordingly:    
int k = 0;
for (auto i = domain.begin(); i != domain.end(); ++i)
    for (int j = 0; j < i->second; ++j)
        A[k++] = i->first;

(如果有一种方法如何在上面的代码中更有效地使用 std::map，请告诉我)