algorithm - 荷兰国旗

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)：O(nk)只要颜色的数量k是恒定的，就很容易做到。

对于类似于三路分区（荷兰国旗问题）的算法，我建议使用两遍算法。例如，在第一遍时，我们将0所有的 、 和 视为左侧部分，1并将2和3视为中间部分，并4视为右侧部分。在第二遍中，我们在边界处跳过0s 和s，并对s、s 和s4进行三向划分。请注意，结果是一个稳定的分区：每次通过时，相同元素的顺序保持不变。123