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

DNF 的一个变体如下：

额外的空间复杂度为 O(1)。那是因为交换不依赖于输入长度吗？时间复杂度，给定为 O(N^2)，是因为嵌套循环吗？谢谢

我一直在探索 Dikstra 分区算法。以下是我给出的：

我有这个未分区的数组。

我希望它按以下格式分区：R、W、B 连续。

鉴于：

下面是我的算法：

输出应该是这样的：

我的问题是：

1. 我可以减少掉期的数量吗？如果是，如何？
2. 如果要划分 4 种颜色，该算法是否适用？

谢谢你。我真的需要理解这个概念。

我是 CompSci 1 的 10 年级学生。在我们的教科书Practical Programming 3rd Edition, An Introduction to Computer Science Using Python 3.6中，它提到了荷兰国旗问题。以下是它如何逐字说明练习：

Edsgar Dijkstra 以其在编程语言方面的工作而闻名。他提出了一个巧妙的问题，他称之为荷兰国旗问题：给定一个字符串列表，每个字符串要么是“red”、“green”或“blue”（每个在列表中表示多次），重新排列列表，使字符串按照荷兰国旗的顺序排列——首先是所有“红色”字符串，然后是所有“绿色”字符串，然后是所有“蓝色”字符串。

这是我为练习编写的 python 代码：

我的代码在 O(n) 时间内运行。但是，我的老师告诉我们，这个程序需要一个排序算法，充其量是 O(n*logn)。为什么我的代码更快？

给定一个包含 0、1 和 2 的大小为 N 的数组 A；您需要按升序对数组进行排序。

输入： 第一行包含一个整数“T”，表示测试用例的总数。然后是 T 测试用例。每个测试用例包含两行输入。第一行表示数组 N 的大小。第二行包含由空格分隔的数组 A 的元素。

下面是java代码为什么最高元素不在数组的后端？

对于输入：

你的输出是：

我正在尝试实现 3-Way 分区以进行快速排序。我用很多自定义测试用例进行了测试，但如果工作正常，但对于一些未知的情况它会失败。我无法弄清楚我要去哪里。

这是代码。分区：

排序功能：

如果您能帮助我，我将不胜感激。

你能解释一下在最好的情况下如何对 O(N) 进行快速排序吗？为什么会有O(N)？

我不明白它在哪里溢出。5 个元素 [2 3 9 2 2] 的数据的输出是 [7208668 3 2 2 9] 而不是 [2 2 2 3 9]。

这个分区是从另一个函数调用的，该函数选择一个随机枢轴并调用这个分区函数。它需要这个分区函数的输出递归地调用它自己的函数来执行快速排序。

编辑：这里的 swap() 是 C++ 库中的一个内置函数。

因此，我尝试在 Dafny 中实现一个简化的荷兰国旗问题的程序，其中所有索引 0 <= n < k 都是红色的，所有索引 k <= n < arr.Length 都是蓝色的，除了它一直说 k 可能会消失即使根据我的编码方式，它最多应该是 arr.Length 。我在这里做错了什么？