荷兰国旗问题扩展至5种颜色：能否保持O(n)复杂度及实现方法

Great question! Absolutely, you can extend the Dutch National Flag (DNF) problem to 5 colors while keeping the O(n) time complexity—just like the 3-color version, it only needs a single pass through the array with constant extra space. Let me break this down for you.

Core Idea: Extending DNF Partitioning #

The 3-color DNF works by splitting the array into sorted regions plus an unprocessed middle section. For 5 colors (0,1,2,3,4), we expand this logic to 5 sorted regions using 4 boundary pointers to track where each color belongs:

• [0, p0): All sorted 0s
• [p0, p1): All sorted 1s
• [p1, current): All sorted 2s (our stable middle region)
• [current, p3]: Unprocessed elements we'll evaluate
• [p3+1, p4]: All sorted 3s
• [p4+1, arr_size-1]: All sorted 4s

The pointers specifically track the next available position for each color:

• p0: Next index to place a 0
• p1: Next index to place a 1
• p3: Next index to place a 3 (counting from the end)
• p4: Next index to place a 4 (counting from the end)
• current: The element we're currently processing (starts at the array's beginning)

Step-by-Step Logic #

We loop while current <= p3—once current passes p3, all remaining elements are already sorted 3s and 4s:

1. If current element is 0: Swap it with the element at p0, then increment p0, p1, and current. The swapped element from p0 is either a 1 or unprocessed (safe to move current forward since we start from the beginning).
2. If current element is 1: Increment p1 (expand the 1s region) and current—this element is already in the correct place.
3. If current element is 2: Just increment current—2s stay in the middle region until other elements are sorted around them.
4. If current element is 3: Swap it with the element at p3, then decrement p3. Don't increment current—the swapped element could be any unprocessed value that needs re-evaluation.
5. If current element is 4: Swap it with the element at p4, then decrement p4. If p3 ends up greater than p4, adjust p3 to match p4 to avoid overlapping regions. Again, don't increment current—the swapped element needs checking.

C Code Implementation #

Here's the extended function, modeled after your 3-color code:

#include <stdio.h>

void swap(int *x, int *y) {
    int temp = *x;
    *x = *y;
    *y = temp;
}

void sort01234(int a[], int arr_size) {
    int p0 = 0;       // Next position for 0
    int p1 = 0;       // Next position for 1
    int p3 = arr_size - 1; // Next position for 3 (from end)
    int p4 = arr_size - 1; // Next position for 4 (from end)
    int current = 0;  // Current element to process

    while (current <= p3) {
        switch (a[current]) {
            case 0:
                swap(&a[p0], &a[current]);
                p0++;
                p1++;
                current++;
                break;
            case 1:
                p1++;
                current++;
                break;
            case 2:
                current++;
                break;
            case 3:
                swap(&a[current], &a[p3]);
                p3--;
                break;
            case 4:
                swap(&a[current], &a[p4]);
                p4--;
                // Ensure 3s region doesn't overlap with 4s region
                if (p3 > p4) {
                    p3 = p4;
                }
                break;
        }
    }
}

// Example usage
int main() {
    int arr[] = {2, 0, 4, 1, 3, 2, 0, 4, 1};
    int n = sizeof(arr)/sizeof(arr[0]);
    sort01234(arr, n);
    printf("Sorted array: ");
    for (int i=0; i<n; i++) {
        printf("%d ", arr[i]);
    }
    return 0;
}

Is This an Easy Extension? #

Yes! The core DNF logic—partitioning into sorted regions with boundary pointers and a single pass—scales directly to k colors. The only changes are:

• Adding more boundary pointers (for k colors, you need k-1 pointers to track all region edges)
• Adding case statements to handle each color, moving elements to their correct regions
• Adjusting pointer logic for right-side regions (3 and 4 here) since we work from the array's end

It's just a generalization of the 3-color approach—you're adding more "bins" to sort elements into, without sacrificing the linear time, constant space efficiency.

内容的提问来源于stack exchange，提问作者Marc