我的荷兰国旗算法出了什么问题？ [英] What's wrong with my Dutch National Flag algorithm?

问题描述

我正在尝试这样一个数组：

I'm trying to turn an array like this:

0, 1, 2, 2, 1, 0, 1, 0, 0, 1, 2

进入：

0 0 0 0 1 1 1 1 2 2 2

这是我的代码：

public static int[] sortDNF(int[] tape) {
    int smaller = 0; // everything with index < smaller is 0
    int bigger = tape.length - 1; // everything with index > bigger is 2
    int current = 0; // where we are looking now
    int tmp;

    while (current <= bigger) {
        if (tape[current] == 0) {
            tmp = tape[smaller];
            tape[smaller] = tape[current];
            tape[current] = tmp;
            smaller++;
        }
        if (tape[current] == 2) {
            tmp = tape[bigger];
            tape[bigger] = tape[current];
            tape[current] = tmp;
            bigger--;
        }
        current++;
    }

    return tape;
}

这就是它产生的：

 0  0  0  1  1  1  1  0  2  2  2 

我的问题是什么？

推荐答案

猜测：

每次循环都不应该增加电流，因为它应该代表1和未知数之间的分区。例如，当你击中前2个时，你最终用另外2个交换它然后继续前进。后来2换成0的事实是偶然的。较小和当前之间的元素应始终为1并且会被破坏。

You should not be increasing current every time through the loop since that is supposed to represent the partition between the 1's and the unknowns. For example, when you hit the first 2 you end up swapping it with another 2 and then moving on. The fact that the 2 later gets swapped for a 0 is accidental. The elements between smaller and current should always be 1's and that is broken.

当前++应仅在磁带[current]！= 2的情况下完成。磁带[current] = 0时可以这样做，因为你没有改变[较小 - >当前] =仅1的条件。当磁带[current] = 1时移动它是可以的，因为它满足1-only条件。

current++ should only be done in the tape[current] != 2 case. It's ok to do it when tape[current] = 0 because you haven't changed the [smaller -> current] = 1-only condition. And it's ok to move it when tape[current] = 1 because that satisfies the 1-only condition.

...但我还没有尝试过。

...but I haven't tried it.

这篇关于我的荷兰国旗算法出了什么问题？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！