一个在线性时间内对数组进行排序的算法

Question

我正在阅读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.

寻找正确高效的红白蓝排序算法。有一种线性时间复杂度的解决方案。

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

- NoNameY0

---

那么我该如何处理呢？现在我正式没有任何方法。顺便说一下，这不是我的实际做法，我只是在为面试做准备。 - NoNameY0

O(n)时间内计算每种颜色的数量；修复索引；将颜色定位到相应的位置。 - जलजनक

请搜索荷兰国旗问题算法。 - Daniel Fischer

你为什么着迷于使用快速排序？这并不是必要的！ - Mitch Wheat

这被视为一个“排序”问题，但实际上是一个“分区”问题。良好的通用排序算法通常具有O(n log n)的时间复杂度。良好的通用分区问题通常为O(n)。问题中预期的运行时复杂度有时可以提示您应该寻找哪些类型的解决方案。 - Adrian McCarthy

Answer 1

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

现在使用“检查”函数从左到右扫描数组。

- 每次遇到红色元素时，使用“交换”函数将其与当前红色指针交换，并增加红色指针。 - 同样，每次遇到蓝色元素时，将其与当前蓝色指针交换并减少蓝色指针。 - 遇到白色元素时，增加当前指针。 - 当当前指针越过蓝色指针时停止。

现在，数组应该按您想要的方式排序。

这就是荷兰国旗问题。

- Abhinav Sarkar

---

另一个问题是，我们不清楚是否允许使用这三个额外的变量来保存索引。 - Will Ness

@WillNess 是的，你可以使用3个变量。 - NoNameY0

那么这个答案看起来还不错。 - Will Ness

@user2117772 为什么不在纸上涂鸦呢？例如，有WWRRBWRRBW；有红色=0，蓝色=9，i=1。第一步很特殊。没有R，也没有交换。增加i，现在i=2。A[i]==R，所以交换回来：swap(A,red,i)。重新进入。等等。 - Will Ness

@AbhinavSarkar 请举个例子 - NoNameY0

Answer 2

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

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

也可以应用三向快速排序来解决。这个演示文稿应该会给你一个很好的想法（相关内容从第37页开始）。此外，它在O(n)中工作，因为不同键的数量是一个常数3（如第43页所述）。

- Roney Michael

---

我可以使用快速排序吗？ - NoNameY0

@user2117772，快速排序中的一个分区操作就可以完成。但是你需要具有多个枢轴区域的变体，而不仅仅是一个枢轴：最终你将拥有“较小的”，然后是“较大的”，然后是“与枢轴相等的”。当然，没有必要进行最后一次交换，将枢轴放入中间位置。 - Will Ness

@user2117772：是的；O(n)。我已经编辑了我的答案以反映它。我希望它回答了你的问题。 - Roney Michael

以下是三路快速排序方法的详细说明以及完整代码 - http://algs4.cs.princeton.edu/23quicksort/ - TheCrazyProgrammer

Answer 3

我已经阅读了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);
}

- Đào Ngọc Thành

---

你能提供更多关于你提供的解决方案的信息吗？ - Datacrawler

Answer 4

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

1. 遍历一次数组，找到红色、白色和蓝色的计数作为rcount、wcount、bcount。

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

3. 对于每个计数器，递增直到达到不是该范围内正确颜色的颜色。

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

当循环结束时，您就得到了您的数组。

- user1952500

---

我只有交换和检查作为我的方法。 - NoNameY0

啊，没有自增操作？至少应该有一个跳转到下一个的goto吧？ - user1952500

不。严格检查并交换。 - NoNameY0

如果没有循环或递增，你将受限于常数时间算法。 - Pieter Geerkens

我能使用快速排序吗？似乎对于这个问题，快速排序的时间复杂度是O(n)。 - NoNameY0

Answer 5

这不是一个排序问题，而是一个分组问题。

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

XXXXYYYYZZZZZZZZZ

其中 X 代表红色，Y 代表白色，Z 代表蓝色。

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

将每个指针向前移动，直到它所在集合中第一个错误的元素。例如，如果 A 是这样的：

XYXXYYXYZZZZZZZZZ

I

我们将指针X提前到第二个位置（索引1），因为该元素不在正确的位置。

如果对于每个指针都这样做，那么您就知道每个三个指针都指向一个不在正确位置的元素。然后遍历列表。每当您发现一个不在正确位置的元素时，请将其与其相应的指针交换，即如果您在Y中找到X，则将其与其Y指针交换，然后递增该指针（Y）直到它再次指向不在正确位置的元素。

继续执行，直到数组排序完成。

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

- Jason

---

我可以使用快速排序吗？ - NoNameY0

快速排序的运行时间是n log n，因此它会打破您的n运行时限制。 - Jason

我觉得快速排序应该是O（n），因为我将只扫描一次数组，同时通过改变枢轴使得其左边的元素都小于枢轴，右边的元素都大于等于枢轴。我使用快速排序手动完成了这个操作，但我无法理解为什么它应该是nlogn而不是n。 - NoNameY0

两次O(n)的遍历仍然是O(n)。 - Will Ness

如果你把它看作是快速排序的特殊情况，那么它基本上是相同的算法。一般来说，Dijkstra算法会更快。 - Jason

Answer 6

我正在研究 Skiena 的书，看到了这个问题。

我得到了一个 O(2n) 的解决方案:

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

1. 首先遍历数组并分区，以 B 为中心轴，使所有的 R 或 W 值都被推到数组的前面。现在 A 将是 ['R', 'W', 'R', 'W', 'B', 'B'] => O(n)

2. 再次遍历 A，以 W 为中心轴进行旋转，这样所有的 R 值将被推到数组的前面。我们可以忽略 B，因为它们已经在正确的位置上了。

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

这是一种线性解决方案。

这正确吗？

- Sreejith

---

你不应该将你的问题写成答案。最好写一个评论。 - TheCrazyProgrammer