荷兰国旗问题是将一个包含三种元素的数组排序的问题，通常的做法是用三个指针：low、mid、high。初始时，low和mid都指向数组的起始位置，high指向末尾。然后通过遍历数组，根据mid指针所指的元素的值来进行交换和移动指针。

以下是完整的C语言代码示例：

#include <stdio.h>

// 交换两个整数的值
void swap(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

// 荷兰国旗算法实现
void dutchFlagSort(int arr[], int n) {
    int low = 0;       // 指向当前0的区域的末尾+1
    int mid = 0;       // 遍历指针
    int high = n - 1;  // 指向当前2的区域的开头-1

    // 当mid指针未超过high时继续处理
    while (mid <= high) {
        switch (arr[mid]) {
            case 0:
                // 如果遇到0，交换到low区域
                swap(&arr[low], &arr[mid]);
                low++;  // low区域向右扩展
                mid++;  // mid指针前进（因为交换过来的值已经被检查过）
                break;
            case 1:
                // 遇到1直接跳过
                mid++;
                break;
            case 2:
                // 遇到2，交换到high区域
                swap(&arr[mid], &arr[high]);
                high--; // high区域向左扩展
                // 注意：这里不需要移动mid指针，因为交换过来的值尚未检查
                break;
        }
    }
}

// 打印数组
void printArray(int arr[], int n) {
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

int main() {
    int arr[] = {2, 0, 1, 1, 2, 0, 1, 2};
    int n = sizeof(arr) / sizeof(arr[0]);

    printf("原始数组: ");
    printArray(arr, n);

    dutchFlagSort(arr, n);

    printf("排序结果: ");
    printArray(arr, n);

    return 0;
}

代码执行结果

原始数组: 2 0 1 1 2 0 1 2 
排序结果: 0 0 1 1 1 2 2 2 

详细解释

1. 算法思想

使用三个指针将数组划分为三个区域：

• low 左侧：已排序的0
• low 到 mid：已排序的1
• high 右侧：已排序的2
• mid 到 high：待处理区域

2. 核心逻辑

• 遇到0：与low位置的元素交换，low和mid都右移（因为交换到mid位置的元素必定是1）
• 遇到1：直接跳过，mid右移
• 遇到2：与high位置的元素交换，high左移（但mid不动，因为交换过来的元素可能是0或1）

3. 时间复杂度

• O(n)：只需一次遍历
• 空间复杂度O(1)：原地排序

4. 关键点

• mid <= high 是循环终止条件
• 当处理2时，mid指针不移动（因为交换来的新值需要重新检查）

适用场景

• 三值排序问题
• 需要线性时间且原地操作的排序需求
• 扩展可用于多色排序（需调整指针数量）

这个实现是荷兰国旗问题的经典解决方案，兼顾效率与简洁性。