排序：如何对包含三种类型数字的数组进行排序

Question

排序：如何对包含三种类型数字的数组进行排序

arraysalgorithmsortinglanguage-agnosticpseudocode

14

例如：int A[] = {3,2,1,2,3,2,1,3,1,2,3}; 如何高效地对这个数组进行排序？

这是面试需要的，只需要提供一个伪代码。

- thechmodmaster

面试明天，但已经参加过同样面试的某人被问到了这个问题。 - thechmodmaster

1

作弊的方法。如果你真的想了解它们，可以查找排序算法。 - Andre

3

为什么不直接计算每个元素的数量，然后根据数量生成一个新的数组呢？ - Matt Wolfe

1

我学习了所有的排序算法，但因为这个数组只包含3个选项（1、2和3），所以我认为这里有一个诀窍。 - thechmodmaster

Matt Wolf：我不能定义另一个数组。我可以交换单元格（需要尽可能少地交换）。 - thechmodmaster

显示剩余5条评论

16个回答

9

这是计算机科学中的一个标准问题：荷兰国旗问题。请查看链接。

- Ravi Gupta

4

计算每个数字的出现次数，并根据它们的数量创建新数组...时间复杂度为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;

- sluki

我不能定义另一个数组。我可以交换单元格（需要尽可能少地交换）。 - thechmodmaster

2

所以，不要使用数组计数，而是使用三个变量。 - sluki

实际上，这是 O(n+k) 的时间复杂度，其中 n 是输入的大小，k 是可能出现的值的数量。由于在原帖中 k < n，因此这是一个无意义的问题，但我认为应该向未来的访问者明确说明。 - robert

3

我认为问题的意图是让您使用桶排序。在数值较少的情况下，桶排序比更常用的快速排序或归并排序要快得多。

- robert

3

问题描述：你有n个桶，每个桶里面都有一枚硬币，硬币的面值可以是5、10或20。你需要在以下限制下对这些桶进行排序：1. 只能使用以下两个函数：SwitchBaskets（Basket1，Basket2）- 交换两个篮子；GetCoinValue（Basket1）- 返回所选篮子中的硬币面值。2. 不能定义大小为n的数组。3. 尽可能少地使用switch函数。

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

我将从篮子中取出硬币： 1）如果它是5，则将其推到第一个位置， 2）如果它是20，则将其推到最后一个位置， 3）如果它是10，则把它留在原地。 4）然后看看下一个篮子。

编辑：如果您无法将元素推到第一个或最后一个位置，则合并排序将是理想的实现方法。下面是它的工作方式：

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

- Yusubov

你不能推到最后或第一个 - 你只能在两个桶之间切换。 - thechmodmaster

1

ElYusubov，非常感谢您的所有帮助，我真的非常感激！！ - thechmodmaster

3

正如Robert所提到的，BasketSort（或BucketSort）是这种情况下最好的选择。

我还想补充另一个算法（实际上与busket sort非常相似）：

[伪代码采用Java风格]

创建一个HashMap<Integer, Interger> map并循环遍历你的数组：

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

- ArtemStorozhuk

你有n个桶，每个桶里面都有一枚硬币，硬币的面值可以是5、10或20。你需要在以下限制下对这些桶进行排序：1. 你只能使用以下两个函数：SwitchBaskets(Basket1, Basket2) - 交换两个篮子；GetCoinValue(Basket1) - 返回所选篮子中的硬币面值。2. 你不能定义大小为n的数组。3. 尽可能少地使用交换函数。 - thechmodmaster

@thechmodmaster你需要更新你的问题，加入这些信息。 - catch23

@ArtemStorozhuk，你的代码中排序区域在哪里？ - catch23

2

这是基于@ElYusubov的Groovy解决方案，但不是将Bucket(5)推到开头和Bucket(15)推到结尾，而是使用筛选，使5向开头移动，15向结尾移动。

每当我们从结尾交换桶时，我们会将end减1，不会增加当前计数器，因为我们需要再次检查该元素。

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} " }

- d1val

2

我认为我理解了这个问题——您只能使用O(1)的空间，并且只能通过交换单元格来更改数组。（因此，您可以对数组使用2个操作——交换和获取）

我的解决方案：

使用2个索引指针——一个用于最后一个1的位置，另一个用于最后一个2的位置。

在第i阶段，您假设数组已经按从1到i-1排序，然后检查第i个单元格：如果A[i] == 3，则什么也不做。如果A[i] == 2，则将其与最后一个2索引后面的单元格交换。如果A[i] == 1，则将其与最后一个2索引后面的单元格交换，然后将包含1的最后一个1索引后面的单元格与最后一个1索引后面的单元格交换。

这是主要的想法，您需要注意一些细节。总体复杂度为O(n)。

- barak1412

2

可以非常容易地使用以下方式进行-->

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

不要使用1、2、3，而是将其视为0、1、2

- Anil Arya

1

仅供娱乐，以下是如何实现“将值推送到远端”的方法，正如ElYusubub所建议的：

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

这可能是一个最优的解决方案。我不确定。

- configurator

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- LihO · Accepted Answer

看起来最有前途的排序方法似乎是计数排序。建议查看这个讲座，由Richard Buckland主讲，特别是从15:20开始的部分。

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

这是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;

请注意，如果域值之间存在很大差异，则将域存储为数组是低效的。在这种情况下，更好的想法是使用映射（感谢abhinav指出）。以下是使用std::map存储域值-出现次数对的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;

如果有更高效使用std::map的方法，请告诉我。