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

Question

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

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

这是面试,我只需要一个伪代码.

Answer 1

如何对它进行排序的有希望的方式似乎是计数排序.值得一看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在上面的代码中使用更有效,请告诉我)

Answer 2

它是计算机科学中的标准问题:荷兰国旗问题 请参见链接.

Answer 3

问题描述：你有n个桶，每个桶里有一个硬币，硬币的值可以是5或10或20。你必须在这个限制下对桶进行排序： 1.你只能使用这2个函数：SwitchBaskets (Basket1 , Basket2) \xe2\x80\x93 switch 2 个篮子 GetCoinValue (Basket1) \xe2\x80\x93 返回所选篮子 2 中的硬币值。不能定义大小为 n 的数组 3. 尽可能少地使用 switch 函数。

\n\n

我的简单伪代码解决方案，可以用任何语言实现，复杂度为 O(n)。

\n\n

我将从篮子里挑选硬币\n1) 如果是 5 - 将其推到第一个，\n2) 如果是 20 - 将其推到最后一个，\n3) 如果是 10 - 将其留在原处。\n4) 并查看队列中的下一个桶。

\n\n

编辑： 如果您无法将元素推到第一个或最后一个位置，那么合并排序将是盗版实现的理想选择。其工作原理如下：

\n\n

合并排序利用了将已排序列表合并到新排序列表中的便利性。它首先比较每两个元素（即，1 与 2，然后 3 与 4...），如果第一个元素出现在第二个元素之后，则交换它们。然后，它将每个结果的两个列表合并为四个列表，然后合并这些四个列表，依此类推；直到最后两个列表合并成最终的排序列表。在这里描述的算法中，这是第一个能够很好地扩展到非常大的列表的算法，因为它的最坏情况运行时间是 O(n log n)。合并排序在实际实现中的流行度相对最近激增，被用于编程语言中的标准排序例程

\n