荷兰国旗

Question

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

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

void sort012(int a[], int arr_size){
int lo = 0;
int hi = arr_size - 1;
int mid = 0;

while (mid <= hi){
    switch (a[mid]){
    case 0:
        swap(&a[lo++], &a[mid++]);
        break;
    case 1:
        mid++;
        break;
    case 2:
        swap(&a[mid], &a[hi--]);
        break;
    }
}
}

Answer 1

绝对是 O(n)：只要颜色数 k 不变，在 O(nk) 中就可以做到。

对于类似于三路分区 (Dutch National Flag problem) 的算法，我建议使用两遍算法。例如，在第一遍中，我们将0视为左侧部分，将1、2和3全部视为中间部分，而4 作为正确的部分。在第二遍中，我们跳过边界处的 0s 和 4s，并对 1s、2s 和 [=16 进行三向划分=]秒。请注意，结果是一个稳定的分区：在每次传递中，相同元素的顺序保持不变。