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

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

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

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

问题描述：您有n个存储桶，每个存储桶包含一个硬币，硬币的值可以为5或10或20。您必须在以下限制下对存储桶进行排序：1.您只能使用以下两个功能：SwitchBaskets（Basket1

，Basket2）–切换2个篮子GetCoinValue（Basket1）–返回选定篮子2中的硬币价值。您不能定义大小为n的数组3.尽量少使用切换功能。

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

我将从篮子中挑选硬币：1）如果是5-将其推为第一个，2）如果是20-将其推为最后，3）如果为10-将其保留在原处。4）并查看下一个存储桶。

如果您不能将元素推到第一个或最后一个位置，

那么合并排序将是理想的实现。运作方式如下：

合并排序利用了将已排序列表合并到新排序列表中的便利性。它首先比较每两个元素（即1与2，然后3与4

…）并交换它们（如果第一个应该在第二个之后）。然后，将两个结果列表中的每个合并为四个列表，然后合并四个列表，依此类推；直到最后将两个列表合并到最终排序的列表中。在这里描述的算法中，这是第一个可以很好地扩展到非常大的列表的算法，因为其最坏情况下的运行时间为O（n

log n）。合并排序在实际实现中已经出现了相对较新的流行，被用于编程语言中的标准排序例程