C语言实现荷兰国旗问题

荷兰国旗问题是经典的排序算法题目，它利用了分治策略和数组原地操作的思想。这个任务的目标是将一个包含三种颜色（红、白、蓝）的整数数组，按照“红色 -> 白色 -> 蓝色”的顺序排列。以下是C语言的一个简单实现：

#include <stdio.h>

void swap(int* a, int* b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

void partition(int arr[], int low, int high) {
    int pivot = arr[high], i = (low - 1); // 将最后一个元素作为基准

    for (int j = low; j <= high - 1; j++) {
        if (arr[j] == 0) {   // 红色元素
            i++;
            swap(&arr[i], &arr[j]);
        }
    }
    swap(&arr[i + 1], &arr[high]);
}

void quicksort(int arr[], int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high);
        quicksort(arr, low, pi - 1);  // 对左边部分递归排序
        quicksort(arr, pi + 1, high);   // 对右边部分递归排序
    }
}

void dutch_flag_problem(int arr[], int n) {
    quicksort(arr, 0, n - 1);
}

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

    printf("Original array: ");
    for (int i = 0; i < n; i++)
        printf("%d ", arr[i]);

    dutch_flag_problem(arr, n);

    printf("\nSorted array after Dutch flag problem: ");
    for (int i = 0; i < n; i++)
        printf("%d ", arr[i]);

    return 0;
}

在这个程序中，`quicksort`函数负责排序，`partition`函数则用于将数组划分为两部分，红色元素都在左侧，蓝色元素都在右侧，而白色元素居中。最后，`dutch_flag_problem`调用快速排序完成整个过程。