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

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

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

How to sort this array efficiently?

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

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

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

15 个解决方案

#1

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.

问题描述:你有n个桶，每个桶包含一枚硬币，硬币的价值可以是5或10或20。你必须在这个限制下对桶进行排序:1。您只能使用这两个函数:开关篮(篮球1，篮球2)-开关2篮子GetCoinValue(篮球1)-返回选定篮子2中的硬币值。你不能定义大小为n 3的数组。尽可能少地使用开关功能。

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

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

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.

我将从篮子中挑选1)如果是5——推它为第一个，2)如果是20——推它为最后一个，3)如果是10——把它放在原地。4)看看下一个水桶。

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

Merge sort利用了将已经排序的列表合并到新的排序列表的便利。它首先比较每两个元素(例如。， 1加2，然后3加4)如果第一个应该在第二个之后，就交换它们。然后它将两个结果列表中的每一个合并到四个列表中，然后合并这些四个列表，以此类推;直到最后两个列表被合并到最终排序的列表中。在这里描述的算法中，这是第一个在非常大的列表中扩展的，因为它最坏的运行时间是O(n log n)。归并排序在实际实现中出现了相对较新的流行，被用于编程语言中的标准排序例程。

#2

The promising way how to sort it seems to be the counting sort. Worth to have a look at this lecture by Richard Buckland, especially the part from 15:20.

有希望的排序方式似乎是计数排序。值得一看Richard Buckland的讲座，特别是15:20的部分。

Analogically to the counting sort, but even better would be to create an array representing the domain, initialize all its elements to 0 and then iterate through your array and count these values. Once you know those counts of domain values, you can rewrite values of your array accordingly. Complexity of such an algorithm would be O(n).

类似于计数排序，但更好的方法是创建一个表示域的数组，将其所有元素初始化为0，然后遍历数组并计数这些值。一旦知道了这些域值的计数，就可以相应地重写数组的值。这种算法的复杂度是O(n)。

Here's the C++ code with the behaviour as I described it. Its complexity is actually O(2n) though:

下面是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;

Note, that if there is big difference between domain values, storing domain as an array is inefficient. In that case it is much better idea to use map (thanks abhinav for pointing it out). Here's the C++ code that uses std::map for storing domain value - occurrences count pairs:

注意，如果域值之间有很大的差异，那么将域存储为数组是无效的。在这种情况下，最好使用map(感谢abhinav指出的)。这里是使用std的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;

(if there is a way how to use std::map in above code more efficient, let me know)

(如果有办法使用std::map in上述代码更有效，请让我知道)

#3

Its a standard problem in computer science : Dutch national flag problem See the link.

这是计算机科学的一个标准问题:荷兰国旗问题见链接。

#4

count each number and then create new array based on their counts...time complexity in O(n)

计算每个数字，然后根据它们的计数创建新的数组……在O(n)时间复杂度

 int counts[3] = {0,0,0};
 for(int a in A)
  counts[a-1]++;
 for(int i = 0; i < counts[0]; i++)
  A[i] = 1;
 for(int i = counts[0]; i < counts[0] + counts[1]; i++)
  A[i] = 2;
 for(int i = counts[0] + counts[1]; i < counts[0] + counts[1] + counts[2]; i++)
  A[i] = 3;

#5

I think the question is intending for you to use bucket sort. In cases where there are a small number of values bucket sort can be much faster than the more commonly used quicksort or mergesort.

我认为这个问题是想让你们用桶排序。在有少量值的情况下，bucket排序可能比更常用的quicksort或merge esort要快得多。

#6

As robert mentioned basketsort (or bucketsort) is the best in this situation.

正如罗伯特提到的，在这种情况下，篮子(或桶篮)是最好的。

I would also added next algorithm (it's actually very similar to busket sort):

我还会添加下一个算法(它实际上非常类似于busket排序):

[pseudocode is java-style]

(伪代码是java风格)

Create a HashMap<Integer, Interger> map and cycle throught your array:

创建一个HashMap map and cycle through your array: ,>

for (Integer i: array)
{
    Integer value = map.get(i);
    if (value == null)
    {
        map.put(i, 1);
    }
    else
    {
        map.put(i, value+1);
    }
}

#7

I think I understasnd the question - you can use only O(1) space, and you can change the array only by swapping cells. (So you can use 2 operations on the array - swap and get)

我认为我低估了这个问题——你只能使用O(1)空间，而你只能通过交换单元来改变数组。(所以你可以对数组使用2个操作——交换和获取)

My solution:

我的解决方案:

Use 2 index pointers - one for the position of the last 1, and one for the position of the last 2.

使用两个索引指针——一个表示最后一个的位置，另一个表示最后两个的位置。

In stage i, you assume that the array is allready sorted from 1 to i-1, than you check the i-th cell: If A[i] == 3 you do nothing. If A[i] == 2 you swap it with the cell after the last 2 index. If A[i] == 1 you swap it with the cell after the last 2 index, and than swap the cell after the last 2 index (that contains 1) with the cell after the last 1 index.

在阶段i中，假设数组已经从1排序到i-1，而不是检查第i个单元格:如果A[i] = 3，那么什么也不做。如果A[i] == 2，则在最后两个索引之后将其与单元格交换。如果A[i] = 1，则在最后两个索引之后与单元格进行交换，而不是在最后一个索引之后与单元格进行交换。

This is the main idea, you need to take care of the little details. Overall O(n) complexity.

这是主要思想，你需要注意细节。整体O(n)的复杂性。

#8

Have you tried to look at wiki for example? - http://en.wikipedia.org/wiki/Sorting_algorithm

你试过看看维基吗?——http://en.wikipedia.org/wiki/Sorting_algorithm

#9

This code is for c#:

此代码用于c#:

However, you have to consider the algorithms to implement it in a non-language/framework specific way. As suggested Bucket set might be the efficient one to go with. If you provide detailed information on problem, i would try to look at best solution. Good Luck...

但是，您必须考虑以非语言/框架特定的方式实现它的算法。正如所建议的，Bucket集可能是最有效的。如果你提供关于问题的详细信息，我将尝试寻找最好的解决方案。祝你好运…

Here is a code sample in C# .NET

下面是c# .NET中的代码示例

int[] intArray = new int[9] {3,2,1,2,3,2,1,3,1 };
Array.Sort(intArray);
// write array
foreach (int i in intArray) Console.Write("{0}, ", i.ToString());  

#10

Just for fun, here's how you would implement "pushing values to the far edge", as ElYusubub suggested:

只是为了好玩，以下是你如何实现“将价值观推向远方”的方法。

sort(array) {
  a = 0
  b = array.length
  # a is the first item which isn't a 1 
  while array[a] == 1
    a++
  # b is the last item which isn't a 3
  while array[b] == 3
    b--

  # go over all the items from the first non-1 to the last non-3
  for (i = a; i <= b; i++)
    # the while loop is because the swap could result in a 3 or a 1
    while array[i] != 2
      if array[i] == 1
        swap(i, a)
        while array[a] == 1
          a++
      else # array[i] == 3
        swap(i, b)
        while array[b] == 3
          b--

This could actually be an optimal solution. I'm not sure.

这实际上是一个最优解。我不确定。

#11

Here is the groovy solution, based on @ElYusubov but instead of pushing Bucket(5) to beginning & Bucket(15) to end. Use sifting so that 5's move toward beginning and 15 towards end.

下面是groovy解决方案，它基于@ElYusubov，而不是将Bucket(5)推到开始和Bucket(15)。使用筛选，使5的移动向开始，15向结束。

Whenever we swap a bucket from end to current position, we decrement end, do not increment current counter as we need to check for the element again.

每当我们将一个bucket从一端交换到当前位置时，我们就会递减结束，不要增加当前计数器，因为我们需要再次检查元素。

array = [15,5,10,5,10,10,15,5,15,10,5]

    def swapBucket(int a, int b) {

        if (a == b) return; 
        array[a] = array[a] + array[b]
        array[b] = array[a] - array[b]
        array[a] = array[a] - array[b]

    }

def getBucketValue(int a) {
    return array[a];
}

def start = 0, end = array.size() -1, counter = 0;
// we can probably do away with this start,end but it helps when already sorted.

// start - first bucket from left which is not 5
while (start < end) {

    if (getBucketValue(start) != 5) break;
    start++;

}     

// end - first bucket from right whichis not 15
while (end > start) {

    if (getBucketValue(end) != 15) break;
    end--;

}

// already sorted when end = 1 { 1...size-1 are Buck(15) } or start = end-1      

for (counter = start; counter < end;) {

    def value = getBucketValue(counter)

    if (value == 5) { swapBucket(start, counter); start++; counter++;}
    else if (value == 15) { swapBucket(end, counter); end--; } // do not inc counter
    else { counter++; }

}

for (key in array) { print " ${key} " }

#12

Lets break the problem we have just two numbers in array . [1,2,1,2,2,2,1,1]

让我们打破这个问题我们只有两个数字在数组中。(1、2、1、2、2、2、1、1]

We can sort in one pass o(n) with minm swaps if; We start two pointers from left and right until they meet each other. Swapping left element with right if left element is bigger. (sort ascending)

我们可以用minm交换来进行一次o(n)排序;我们从左和右开始两个指针，直到它们相遇。如果左元素较大，则将左元素与右元素交换。(升序)

We can do another pass, for three numbers (k-1 passes). In pass one we moved 1's to their final position and in pass 2 we moved 2's.

我们可以再做一次，3个数字(k-1次)。在传1中，我们把1移动到最后位置，在传2中，我们移动了2。

def start = 0, end = array.size() - 1;

// Pass 1, move lowest order element (1) to their final position 
while (start < end) {
    // first element from left which is not 1
    for ( ; Array[start] ==  1 && start < end ; start++);
    // first element from right which IS 1
    for ( ; Array[end] != 1 && start < end ; end--);

    if (start < end) swap(start, end);
}     

// In second pass we can do 10,15

// We can extend this using recurion, for sorting domain = k, we need k-1 recurions 

#13

This can be done very easily using-->

使用>可以很容易地做到这一点

Dutch national Flag algorithm http://www.csse.monash.edu.au/~lloyd/tildeAlgDS/Sort/Flag/

荷兰国旗算法http://www.csse.monash.edu.au/~lloyd/ tilgds /Sort/Flag/

instead of using 1,2,3 take it as 0,1,2

而不是1 2 3取0 1 2

#14

def DNF(input,length):
    high = length - 1
    p = 0
    i = 0
    while i <= high:
            if input[i] == 0:
                    input[i],input[p]=input[p],input[i]
                    p = p+1
                    i = i+1
            elif input[i] == 2:
                    input[i],input[high]=input[high],input[i]
                    high = high-1
            else:
                    i = i+1
input = [0,1,2,2,1,0]
print "input: ", input
DNF(input,len(input))
print "output: ", input

#15

//Bubble sort for unsorted array - algorithm
public void  bubleSort(int arr[], int n) { //n is the length of an array
    int temp;
    for(int i = 0; i <= n-2; i++){
        for(int j = 0; j <= (n-2-i); j++){
            if(arr[j] > arr[j +1]){
                temp = arr[j];
                arr[j] = arr[j +1];
                arr[j + 1] = temp;

            }
        }

    }