排序:如何对包含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};
如何有效地对该数组进行排序?
How to sort this array efficiently?
这是一次求职面试，我只需要一个伪代码.
This is for a job interview, I need just a pseudo-code.
推荐答案
问题描述:您有n个桶，每个桶包含一个硬币，硬币的值可以是5或10或20.您必须对这些桶进行排序在此限制下:1.您只能使用这两个功能:SwitchBaskets(Basket1，Basket2)–切换2个篮子GetCoinValue(Basket1)–返回选定篮子中的Coin Value 2.您不能定义大小为n的数组3.使用切换功能尽可能少.
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.
我简单的伪代码解决方案，可以用O(n)复杂度的任何语言来实现.
My simple pseudo-code solution, which can be implemented in any language with O(n) complexity.
我将从篮子里捡硬币 1)如果是5-将其推为第一个， 2)如果是20-将其推到最后， 3)如果10-保留它在原处. 4)并查看行中的下一个存储桶.
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.
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:
合并排序利用了将已排序列表合并到新排序列表中的便利性.首先是比较每两个元素(即1与2，然后3与4 ...)并交换它们(如果第一个应该在第二个之后).然后，将两个结果列表中的每一个合并为四个列表，然后将这些四个列表合并，依此类推；直到最后有两个列表合并到最终排序的列表中.在这里描述的算法中，这是第一种可以很好地扩展到非常大的列表的算法，因为其最坏情况下的运行时间为O(n log n).合并排序已在实际实现中得到了较新的普及，并已被用于编程语言中的标准排序例程.
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
这篇关于排序:如何对包含3种数字的数组进行排序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
