众所周知，任何基于比较模型的排序算法都有nlogn的下界，即Omega（nlogn）。这在数学上是可以证明的。
但众所周知，荷兰标志问题可以在O（n）时间内对3个不同的元素（重复使用）进行排序。它也基于比较模型，但可以在O（n）时间内排序。那么，我们如何证明基于比较模型的排序下限是合理的呢？因为荷兰标志问题有点违反了这一点。
请帮我理解其中的区别。。。。。
感谢
在我看来，这不是下界的相关"矛盾"，因为这是一种特殊的情况（值的可能范围小于元素的总数，事实上它是一个常数，3），可以用来找到比O（N*logN）更快的算法，这是基于一般比较的排序算法的下限（即，在没有关于序列内容的信息的情况下）。
通常在N个元素在0..K的范围内且K<N可以有效地利用类似计数排序的非比较排序来解决O（N）中的问题。
绑定Omega(n log n)为任意元素的基于比较的排序提供了一个下界。
荷兰标志问题所考虑的只是一种情况，即您没有任意元素，但每个元素只有三个选项。
因此，在没有附加约束的情况下，约束Omega(n log n)一般适用于该问题。然而，如果你施加其他约束（例如，每个元素只有三个选项），你很可能能够找到比这个界限更好的算法，因为你可以考虑的特定情况，在那里你可以应用其他启发式方法等。
重点是：荷兰标志集不是完全有序的。有许多相等的元素，事实上，当你计算不同的对象时，它是一组（最多）大小为3的元素。
当对象a和b的a<b或b>a成立时，Omega(n log n)界可能才是硬的（也就是说：所有对象都是不同的）
事实上，当所有对象都必须是null时，我可以在O(0)中进行排序。
假设至少有两个不同的对象，我相信适当的界是类似于Omega(n log m)的东西，其中n是对象的数量，m是不同对象的数量（排序不相等）。简单地说，log m是查找输出桶所需的决策数。在一般情况下，如果相等对象的数量较低，则为O(log m)=O(log n)。在荷兰国旗问题中，m=3。
Radix sort以不同的方式利用了这一点。它也被认为是线性的。然而，它需要log m传递数据，其中m是可能不同的元素的数量。所以实际上，Radix排序也是Omega(n log m)，其中m是它可以辨别的对象的数量。
荷兰标志问题比普通排序有一些更基本的数据，它知道有三个不同的值，如果你在维基百科页面上查看算法，它是：
void threeWayPartition(int data[], int size, int low, int high) {
int p = -1;
int q = size;
for (int i = 0; i < q;) {
if (data[i] < low) {
swap(data[i], data[++p]);
++i;
} else if (data[i] >= high) {
swap(data[i], data[--q]);
} else {
++i;
}
}
}
事实上，它不使用元素对之间的比较，它只使用元素的下界/中上界之间的比较。这与正常排序中使用的其他比较方法无关，您可以将其与计数排序进行比较。
Dutch Flag问题更多的是一种分区算法。
这只是排序的第一步。您可以使用它进行排序（通过一次又一次地将其应用于分区），但我想您最终会得到Omega（nlogn）。
知道不同值的数量（在标志的情况下为3）及其值（蓝色、白色、红色）是非常罕见的情况。