我正在阅读 Dutch national flag problem我不明白:为什么这与简单的排序问题不同？
我的意思是:如果我们将 0 分配给红色，将 1 分配给白色，将 2 分配给蓝色并执行标准快速排序或其他任何操作......为什么我不能得到正确答案？
我错过了什么吗？
最佳答案
荷兰国旗问题只是更一般的排序问题的特例，其中唯一允许的元素是 0、1 和 2。您完全可以使用标准排序算法解决它。
这个问题本身很有趣，部分是出于历史原因，但主要是因为很难找到稳定、时间效率 (O(n)) 和空间效率 (O(1)) 的解决方案。很容易获得具有这三个属性中的两个的解决方案，但同时获得所有这三个属性(我相信)是一个悬而未决的问题。作为开发快速排序和使用重复键分区的算法的场所，它也很有趣；您可以将 0、1 和 2 视为小于主元、等于主元和大于主元，并且基本上可以对重复元素进行快速排序。
希望这对您有所帮助!
关于algorithm - 荷兰国旗问题与排序的区别，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/31223561/