三色旗的问题最早由 E.W.Diikstra 所提出，他所使用的用语为 Dutch Nation Flag（Dijkstra 为荷兰人），而多数的作者则使用 Three-Color Flag 来称之。

假设有一条绳子，上面有红、白、蓝三种颜色的旗子，起初绳子上的旗子颜色并没有顺序，您希望将之分类，并排列为蓝、白、红的顺序，要如何移动次数才会最少，注意您只能在绳子上进行这个动作，而且一次只能调换两个旗子。

三色旗问题可以用一个线性时间算法来解决，利用双指针法将问题简化为在数组中按照顺序排放三种颜色的元素。我们可以用整数表示颜色（例如：0 表示蓝色，1 表示白色，2 表示红色）。目标是以最少的交换次数将数组按照颜色排序为蓝、白、红的顺序。

• 定义三个指针：

• 遍历数组，根据 mid 指针所指元素的值进行以下操作：

• 停止条件是 mid > high。

#include <stdio.h>void sortColors(int arr[], int n) {int low = 0, mid = 0, high = n - 1;while (mid <= high) {if (arr[mid] == 0) {  // 蓝色// 交换 mid 和 low 指针的元素int temp = arr[low];arr[low] = arr[mid];arr[mid] = temp;low++;mid++;} else if (arr[mid] == 1) {  // 白色mid++;  // 直接跳过} else {  // 红色// 交换 mid 和 high 指针的元素int temp = arr[high];arr[high] = arr[mid];arr[mid] = temp;high--;}}
}void printArray(int arr[], int n) {for (int i = 0; i < n; i++) {printf("%d ", arr[i]);}printf("\n");
}int main() {int flags[] = {2, 0, 1, 1, 0, 2, 1, 0, 2};int n = sizeof(flags) / sizeof(flags[0]);printf("Before sorting:\n");printArray(flags, n);sortColors(flags, n);printf("After sorting:\n");printArray(flags, n);return 0;
}

flags[] = {2, 0, 1, 1, 0, 2, 1, 0, 2};

Before sorting:
2 0 1 1 0 2 1 0 2 
After sorting:
0 0 0 1 1 1 2 2 2 

• 时间复杂度：O(n)，只需遍历数组一次。
• 空间复杂度：O(1)，仅用到三个指针，没有额外的空间开销。

这种方法通过双指针和交换操作，将交换次数最小化并高效解决问题，非常适合处理这类三分区问题。