4

我正在阅读 Skiena 的算法设计手册，但无法解决这个问题。

假设数组 A 由 n 个元素组成，每个元素是红色、白色或蓝色。我们寻求对元素进行排序，使所有的红色排在所有白色之前，所有白色排在所有蓝色之前。键上允许的唯一操作是

Examine(A,i) { report the color of the ith element of A.
Swap(A,i,j) { swap the ith element of A with the jth element.

找到一个正确有效的红白蓝排序算法。有一个线性时间的解决方案。

我尝试使用快速排序，并且在 3 个枢轴上，我应该能够解决它，但是当我在快速排序中看到重复项时，我不知道该怎么办。

4

6 回答 6

2

维护两个指针：一个最初指向 0 的红色指针和一个指向数组最后一个元素的蓝色指针。

Examine现在使用函数从左到右扫描数组。

  • 每次遇到红色元素时，将其（使用Swap函数）与当前红色指针交换并递增红色指针。
  • 同样，每次遇到蓝色元素时，将其与当前蓝色指针交换并减少蓝色指针。
  • 遇到白色元素时增加当前指针。
  • 当当前指针穿过蓝色指针时停止。

现在应该根据需要对数组进行排序。

这就是荷兰国旗问题。

于 2013-03-03T15:09:23.933 回答
1

这其实是 Dijkstra 提出的一个非常有名的问题，被称为荷兰国旗问题。

上面链接的维基百科对如何解决这个问题和其他类似问题给出了相当不错的说明。

也可以应用 3 路快速排序来解决此问题。本演示文稿应该让您很好地了解如何执行此操作（相关内容从第 37 页开始）。此外，它确实在 O(n) 中工作，因为不同键的数量是一个常数，3（如第 43 页所述）。

于 2013-03-03T15:08:46.377 回答
0

一个非常简单的线性时间算法是：

  1. 在数组中循环一次，找到红色、白色和蓝色的计数为 rcount、wcount、bcount。

  2. 有三个从 0 开始的计数器，rcount, (rcount + wcount)。称它们为 rcounter、wcounter 和 bcounter。

  3. 对于每个计数器，递增，直到获得不适合该范围的颜色

  4. 从 0 开始，每当你遇到一种颜色：如果颜色为红色且（计数器 < rcount），则增加 rcount 并继续（同样适用于白色和蓝色，具体取决于范围） b。如果颜色为白色，则与 wcounter 和 wcounter++ c 交换。如果颜色为蓝色，则与 bcounter 和 bcounter++ 交换

当循环结束时，你有你的数组。

于 2013-03-03T15:05:29.277 回答
0

这不是一个真正的排序问题。这是一个分组问题。

遍历列表，计算红色、白色和蓝色元素的数量。现在您知道了解决方案的确切结构，例如：

XXXXYYYYZZZZZZZZZ

其中 X 为红色，Y 为白色，Z 为蓝色。

现在创建三个指针：一个在 X 开头的位置，一个在 Y 的开头，一个在 A 中 Z 的开头。

推进每个指针，直到它在其集合中的第一个元素是错误的。例如，如果这是 A：

XYXXYYXYZZZZZZZZZ

我

我们将 X 指针 I 推进到第二个位置（索引 1），因为该元素不合适。

如果你对每个指针都这样做，你就会知道三个指针中的每一个都指向一个不合适的元素。然后遍历列表。每当你发现一个元素不合适时，将它与其对应的指针交换，即如果你在 Y 中找到一个 X，将它与其 Y 指针交换，然后递增该指针 (Y) 直到它指向不合适的东西再次。

继续直到数组排序。

由于您遍历列表一次（n 个操作）以获取结构，然后每个指针最多将遍历列表一次（4 个指针 → 4n），因此您的总最大运行时间将为 5n，即 O(n)。

于 2013-03-03T15:10:54.947 回答
0

我浏览了 Skiena 的书，也看到了这个问题，这是我的解决方案。

#include <stdio.h>

//swap the ith element of A with the jth element.
void swap(char arr[], int i, int j) {
    char temp;
    temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
    return;
}

int partition_color(char arr[], int low, int high, char color)
{
    int i;          // counter
    char p;          // pivot element
    int firsthing; // divider position for pivot

    p = color;          // choose the pivot element
    firsthing = high; // divider position for pivot element

    for (i = low; i < firsthing; i++) {
        if (arr[i] == color) {
            swap(arr, i, firsthing);
            firsthing--;
        }
    }

    return(firsthing);
}

void red_white_blue_sorting(char arr[], int n) {
    int pos;
    pos = partition_color(arr, 0, n, 'b');
    partition_color(arr, 0, pos, 'w');
    return;
}

int main() {

    char arr[] = {'r', 'b', 'r', 'w', 'b', 'w', 'b', 'r', 'r'};
    int n = sizeof(arr) / sizeof(arr[0]);

    red_white_blue_sorting(arr, n);
    for (int i = 0; i < n; i++)
        printf("%c ", arr[i]);

    printf("\n");
    return(0);
}
于 2018-02-07T16:31:06.967 回答
-1

我正在浏览 Skiena 的书，看到了这个问题。

我得到了 O(2n) 的解决方案：

假设 A = [B,R,W,R,W,B]

  1. 首先遍历数组并以 B 为轴进行分区，这样，所有 R 或 W 的值都将被推到数组的前面。

现在A将是；['R', 'W', 'R', 'W', 'B', 'B'] => O(n)

  1. 再次通过 A，以 W 为中心，这样所有 R 的值都将被推到数组的前面。我们可以忽略 B，因为它们已经到位。

结果：['R', 'R', 'W', 'W', 'B', 'B'] => O(2n)

这是一个线性解决方案。

这是正确的方法吗？

于 2015-06-09T10:22:33.800 回答