问题标签 [dutch-national-flag-problem]

我想对包含 0、1 或 2 的链表进行排序。现在，这显然是荷兰国旗问题的变体。 http://en.wikipedia.org/wiki/Dutch_national_flag_problem

与链接中给出的相同的算法是：

“让顶部组从数组顶部向下生长，底部组从底部向上生长，并保持中间组刚好在底部上方。算法存储位置就在顶部组下方，就在底部上方，并且在三个索引的中间上方。在每一步中，检查中间上方的元素。如果它属于顶部组，则将其与顶部下方的元素交换。如果它属于底部，则将其与元素交换就在底部上方。如果它在中间，则离开它。更新适当的索引。复杂度是 Θ(n) 移动和检查。

并且为此给出的 C++ 实现是：

}

我唯一的问题是我们如何像在数组中那样遍历链表？

我下面的荷兰国旗解决方案似乎不适用于仅包含 3 个元素（0、1 和 2）的给定输入数组。

如果我减小数组的大小，它会起作用。我无法识别错误。

我错过了什么吗？

更新：上面相同的代码适用于较小的数组：http: //ideone.com/bgEgCs

有点帮助，伙计们。你如何根据某种模式对列表进行排序一个例子是对 R、W、B 的列表进行排序，其中 R 先出现，然后是 W，然后是 B。有点(sortf '(W R W B R W B B))像(R R W W W B B B)

非常感谢任何答案。

荷兰国题就是这个问题：我有一个字符序列 x^k (k >= 3) 我的目标是把这句话变成荷兰国旗，也就是说：

xxx 给 RWB

xxxx 给 RWBB

xxxxx 给 RWWBB

xxxxxx 给 RRWWBB

...

R <= W <= B <= R+1

我想设计一个带有一个功能区的图灵机，复杂度为 n.log(n) 。事实是，标准算法正在使用交换，我不能使用它，这在这种图灵机中不可用（效率不够）......

你知道怎么做吗？:)

作为学习练习，我在 C 中实现快速排序算法。枢轴是 3 个值的中位数，对于具有 4 个或更少元素的分区，我切换到插入排序。

现在我一直在测试两种变体：一种使用Hoare 的分区方案，另一种使用Dutch Flag。

更新：包括两个变体的整个文件。

霍尔的：

荷兰国旗：

两者都获得相同的输入，一系列文件，每个文件都包含10^n随机整数值，范围为[0:(10^n)+1]. n范围从 1 到 7（10 到 1000 万个元素）。我预计荷兰国旗的实施至少与 Hoare 的一样快，但事实并非如此。

标志：-O3

然后我更改了输入：大小相同10^n，但使用值[0:10^(n-1)]，这保证了很多重复值。

结果：

即使对于重复值，荷兰国旗也比霍尔的慢。为什么？选择的支点似乎不太可能是唯一的。

我的环境，如果重要的话：

我经历了两种和三种颜色的解决方案，但我无法获得四种颜色的解决方案。

请帮忙。

会rrbb????yyyggg吗？我们将如何交换绿旗？

我尝试了下面的解决方案，但无法将最后一个黄色换成绿色。

我正在尝试解决荷兰国旗问题。基本上，给定一个列表，我想按照红-白-蓝的顺序对它们进行排序。红色、白色和蓝色由它们的谓词定义（即红色（x）、白色（x）等）。目前，我有以下代码：

我的输出如下所示：

我想要的是它看起来像这样：

我已经尝试了几种方法来强制输出我想要的，但一直无法接近。

编辑：看起来我可以通过使用置换所有可能集合并评估集合是否按“荷兰国旗”顺序的蛮力解决方案来解决它。不过有更好的解决方案吗？

我只想知道如何获得两种颜色荷兰国旗的平均交换次数。排序正数和负数而不是颜色。我假设负数等于正数，并且数组的数字是随机配置的，我不确定我的假设是否正确。

谢谢你。

我了解 3 种颜色的 DNF 问题。假设我想将颜色数量扩展到 5 (0,1,2,3,4)，我还能得到 O(n) 复杂度吗？

所以我认为我们有 5 个区域，其中 2 个是未知区域。但是如何实现呢？我可以轻松地将 3 种颜色的算法扩展到 5 种颜色吗？

我正在用 Scala 解决荷兰国旗问题，并提出以下代码：

出于性能原因，我想修改现有数组，而不是创建一个新数组。swap上面的代码可以工作，但是在调用 from时有明显的副作用iterate，这在纯函数式代码中是有问题的。我考虑用swap稍后执行的方法引用替换foreach，类似于 Haskell IO，但正如您可以想象的那样，这样做会使代码有些复杂。

其他想法？