荷兰红旗问题

sqdtss 2021-08-29 原文

设有一个仅由红、白、蓝三种颜色的条块组成的条块序列，请编写一个时间复杂度为O（n）的算法，使得这些条块按红、白、蓝的顺序排好，即排成荷兰国旗图案。
 1 #include <stdio.h>
 2 #include <algorithm>
 3 using namespace std;
 4 
 5 typedef enum
 6 {
 7     RED,
 8     WHITE,
 9     BLUE
10 } color; //定义荷兰国旗颜色枚举数组
11 
12 void flag_arrange(color sz[], int len)
13 {
14     // i以前全为红色，k以后全为蓝色，i和k中间
15     int i = 0, j = i, k = len - 1;
16     while (j <= k)
17     {
18         // 如果为红色，则和i交换
19         if (sz[j] == RED)
20             swap(sz[i++], sz[j++]);
21         else if (sz[j] == BLUE) // 如果为蓝色，则和k交换
22             swap(sz[k--], sz[j]); //这里没有j++以防交换后仍为蓝色的情况
23         else
24             j++;
25     }
26 }
27 int main()
28 {
29     // 定义一个荷兰国旗数组
30     color a[] = {RED, WHITE, WHITE, BLUE, BLUE, RED, WHITE, BLUE, RED, RED, BLUE, WHITE};
31     // 执行排序
32     flag_arrange(a, 12);
33     // 打印输出排序结果
34     for (int i = 0; i < 12; i++)
35         printf("%d%c", a[i], i == 11 ? \'\n\' : \' \');
36     return 0;
37 }