排序：如何对包含3种数字的数组进行排序(Sorting: how to sort an array that contains 3 kind of numbers)

排序：如何对包含3种数字的数组进行排序(Sorting: how to sort an array that contains 3 kind of numbers)

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

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

这是面试的工作，我只需要一个伪代码。

For example: int A[] = {3,2,1,2,3,2,1,3,1,2,3};

How to sort this array efficiently?

This is for a job interview, I need just a pseudo-code.

最满意答案

问题描述：您有n个桶，每个桶包含一个硬币，硬币的值可以是5或10或20.您必须根据此限制对桶进行分类：1.您只能使用这2个函数：SwitchBaskets（Basket1 ，篮子2） - 切换2篮子GetCoinValue（Basket1） - 返回所选篮子中的硬币值2.你不能定义大小为n的数组3.使用尽可能少的开关功能。

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

我会从篮子里拿硬币1）如果它是5 - 推动它成为第一个，2）如果它是20-推动它成为最后一个，3）如果10 - 把它留在原地。 4）并查看下一个桶。

编辑： 如果你不能将元素推送到第一个或最后一个位置，那么合并排序对于盗版实现来说是理想的。 以下是它的工作原理：

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

Problem description: You have n buckets, each bucket contain one coin , the value of the coin can be 5 or 10 or 20. you have to sort the buckets under this limitation: 1. you can use this 2 functions only: SwitchBaskets (Basket1, Basket2) – switch 2 baskets GetCoinValue (Basket1) – return Coin Value in selected basket 2. you cant define array of size n 3. use the switch function as little as possible.

My simple pseudo-code solution, which can be implemented in any language with O(n) complexity.

I will pick coin from basket 1) if it is 5 - push it to be the first, 2)if it is 20- push it to be the last, 3)If 10 - leave it where it is. 4) and look at the next bucket in line.

Edit: if you can't push elements to the first or last position then Merge sort would be ideally for piratical implementation. Here is how it will work:

Merge sort takes advantage of the ease of merging already sorted lists into a new sorted list. It starts by comparing every two elements (i.e., 1 with 2, then 3 with 4...) and swapping them if the first should come after the second. It then merges each of the resulting lists of two into lists of four, then merges those lists of four, and so on; until at last two lists are merged into the final sorted list. Of the algorithms described here, this is the first that scales well to very large lists, because its worst-case running time is O(n log n). Merge sort has seen a relatively recent surge in popularity for practical implementations, being used for the standard sort routine in the programming languages