arrays - 排序：如何对包含 3 种数字的数组进行排序

Question

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

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

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

score 10 · 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;

请注意，如果域值之间存在很大差异，则将域存储为数组是低效的。在这种情况下，最好使用 map （感谢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在上面的代码中更有效地使用，请告诉我）

score 9 · Accepted Answer

9

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

于 2012-06-17T15:04:14.717 回答

score 4 · Accepted Answer

计算每个数字，然后根据它们的计数创建新数组...时间复杂度 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;

score 3 · Accepted Answer

我认为这个问题是打算让你使用bucket sort。在有少量值的情况下，桶排序可以比更常用的快速排序或合并排序快得多。

score 3 · Accepted Answer

正如罗伯特提到的篮子排序（或桶排序）在这种情况下是最好的。

我还将添加下一个算法（它实际上与 busket 排序非常相似）：

[伪代码是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);
    }
 }

score 3 · Accepted Answer

问题描述：你有n个桶，每个桶包含一个硬币，硬币的价值可以是5或10或20。在这个限制下你必须对桶进行排序：1。你只能使用这2个功能：SwitchBaskets（Basket1 , Basket2) – 切换 2 个篮子 GetCoinValue (Basket1) – 返回选定篮子中的硬币值 2. 你不能定义大小为 n 的数组 3. 尽量少使用 switch 函数。

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

我将从篮子中挑选硬币 1）如果是 5 - 将其推为第一个，2）如果是 20- 将其推为最后一个，3）如果是 10 - 将其留在原处。4) 并查看排队的下一个桶。

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

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

score 2 · Accepted Answer

我想我理解这个问题 - 你只能使用 O(1) 空间，你只能通过交换单元格来更改数组。（因此您可以在数组上使用 2 个操作 - 交换和获取）

我的解决方案：

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

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

这是主要思想，您需要注意小细节。总体 O(n) 复杂度。

score 2 · Accepted Answer

这是基于@ElYusubov 的常规解决方案，但不是将 Bucket(5) 推到开始并将 Bucket(15) 推到结束。使用筛选，使 5 向开始移动，15 向结束移动。

每当我们将存储桶从 end 位置交换到当前位置时，我们都会减少 end，不要增加当前计数器，因为我们需要再次检查元素。

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

score 1 · Accepted Answer

1

例如，您是否尝试过查看 wiki？- http://en.wikipedia.org/wiki/Sorting_algorithm

于 2012-06-16T21:44:59.733 回答

score 1 · Accepted Answer

此代码适用于 c#：

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

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

score 1 · Accepted Answer

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

这实际上可能是一个最佳解决方案。我不知道。

score 1 · Accepted Answer

这可以很容易地使用-->

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

而不是使用 1,2,3 将其视为 0,1,2

score 0 · Accepted Answer

让我们打破数组中只有两个数字的问题。[1,2,1,2,2,2,1,1]

如果：我们从左右两个指针开始，直到它们相遇。如果左元素更大，则将左元素与右元素交换。（升序）

我们可以为三个数字再做一遍（k-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

score 0 · Accepted Answer

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

score 0 · Accepted Answer

我会在这里使用递归方法

fun sortNums(smallestIndex,largestIndex,array,currentIndex){
if(currentIndex >= array.size)
   return
if (array[currentIndex] == 1){
You have found the smallest element, now increase the smallestIndex
//You need to put this element to left side of the array at the smallestIndex position.
//You can simply swap(smallestIndex, currentIndex)
// The catch here is you should not swap it if it's already on the left side
//recursive call
sortNums(smallestIndex,largestIndex,array,currentIndex or currentIndex+1)// Now the task of incrementing current Index in recursive call depends on the element at currentIndex. if it's 3, then you might want to let the fate of currentIndex decided by recursive function else simply increment by 1 and move further
} else if (array[currentInde]==3){
// same logic but you need to add it at end
}
}

您可以通过 sortNums(smallestIndex=-1,largestIndex=array.size,array,currentIndex=0) 启动递归函数

你可以在这里找到示例代码代码链接

score -1 · Accepted Answer

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

            }
        }

    }

arrays - 排序：如何对包含 3 种数字的数组进行排序

16 回答 16

Related

Reference