排序:如何对包含 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. 您只能使用这 2 个函数: SwitchBaskets (Basket1, Basket2) – 切换 2 个篮子 GetCoinValue (Basket1) – 返回所选篮子中的币值 2. 您不能定义大小为 n 的数组 3. 使用 switch 函数尽量少.

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屋！