【老掉牙系列之四】如果作为一个程序猿，你连这些都还不会，你就等着被![]() 叭！
【说明】
三色旗的问题最早由E.W.Dijkstra所提出，他所使用的用语为Dutch Nation Flag(Dijkstra为荷兰
人)，而多数的作者则使用Three-Color Flag来称之。
假设有一条绳子，上面有红、白、蓝三种颜色的旗子，起初绳子上的旗子颜色并没有顺序，您
希望将之分类，并排列为红、白、蓝的顺序，要如何移动次数才会最少，注意您只能在绳子上
进行这个动作，而且一次只能调换两个旗子。
其实这是一个快速排序的算法。
好吧不理解题意的筒子打开下面这个链接：
http://www.csse.monash.edu.au/~lloyd/tildeAlgDS/Sort/Flag/
然后到
Three Colours版块
![]()
点go
然后就会出一个随机数，排好序啦。
觉得脑洞够大的筒子可以不看下面自行解决了。
好吧然后……
解决思路其实已经在链接里面被说明得很清楚了……
先来想办法把色列排成这样：
a[1..Lo-1] zeroes (red)
a[Lo..Mid-] ones (white)
a[Mid..Hi] unknown
a[Hi+1..N] twos (blue)
然后再进行下面一步：
Lo := 1; Mid := 1; Hi := N;
while Mid <= Hi do
Invariant: a[1..Lo-1]=0 and a[Lo..Mid-1]=1 and a[Hi+1..N]=2; a[Mid..Hi] are unknown.
case a[Mid] in
0: swap a[Lo] and a[Mid]; Lo++; Mid++
1: Mid++
2: swap a[Mid] and a[Hi]; Hi--
--- Dutch National Flag Algorithm, or 3-way Partitioning ---
至于配套的图嘛，看链接里的图好啦。
楼主反正是看完图才终于理解了该算法的精髓的。
有兴趣的筒子可以把上述0、1、2排序的结果用C语言实现一下。对于大神理应是轻而易举。对于楼主小白要去好好在墙角思索一下敲出代码来![]() 。
那么三色旗的C语言实现代码如下（假设排列为BWR哈，至于排列为RWB，筒子们可以稍微改动一下哈）：
- #include <stdio.h>
- #include <stdlib.h>
- #include <string.h>
-
- #define SWAP_FLAGS(x, y) { char temp; \
- temp = flags[x]; \
- flags[x] = flags[y]; \
- flags[y] = temp; }
-
- void printFlags(char* flags) {
- int i;
- for(i = 0; i < strlen(flags); i++) {
- printf("%c ", flags[i]);
- }
- printf("\n");
- }
-
- void adjust(char* flags) {
- int w = 0;
- int b = 0;
- int r = strlen(flags) - 1;
- while(flags[w] == 'B' && w < strlen(flags)) { b++; w++; }
- while(flags[r] == 'R' && r > 0) { r--; }
- while(w <= r) switch(flags[w]) {
- case 'W':
- w++;
- break;
- case 'B':
- SWAP_FLAGS(b, w);
- b++; w++;
- break;
- case 'R':
- SWAP_FLAGS(r, w);
- r--;
- }
- }
-
- int main() {
- char flags[] = {'R', 'W', 'B', 'W', 'W',
- 'B', 'R', 'B', 'W', 'R', '\0'};
-
- printFlags(flags);
- adjust(flags);
- printFlags(flags);
-
- return 0;
- }
-
输出结果如下：
R W B W W B R B W R
B B B W W W W R R R
好吧容我做一下代码的搬运工 - -
论数学的重要性 = =
刚刚提到排序0、1、2
楼主小白花了大概4个小时终于把上面的0、1、2能排出来了…………虽然还是参考了很多上述的代码，啊感觉还是要多多思索深入理解一下啊。
- #include <stdio.h>
- #include <stdlib.h>
-
- void adjust(int *a, int n) {
- int x = 0;
- int y = 0;
- int z = n - 1;
- printf("x %d y %d z %d\n", x, y, z);
- printf("%d\n", a[x]);
- while(a[y] == 0 && y < n) {
- x++;
- y++;
- printf("x %d y %d z %d\n", x, y, z);
- } //如果最左边是0的话，把0保留在最左边
- while(a[z] == 2 && z > 0) {
- z--;
- printf("x %d y %d z %d\n", x, y, z);
- } //如果最右边是2的话，把2保留在最右边。
- //至此第一步完成，减少第二步的工作量，提高算法效率
- while(y <= z) {
- switch(a[y]) { //第二步开始，按照上面的思想
- case 0:
- a[y] = a[y] + a[x] - (a[x] = a[y]);
- x++;
- y++;
- break;
- printf("x %d y %d z %d\n", x, y, z);
- case 1:
- y++;
- break;
- printf("x %d y %d z %d\n", x, y, z);
- case 2:
- a[y] = a[y] + a[z] - (a[z] = a[y]);
- z--;
- printf("x %d y %d z %d\n", x, y, z);
- }
- } //至此第二步完成
- int i;
- for(i = 0; i < 6; i++) {
- printf("%d ", a[i]);
- }
- }
-
- int main() {
- int numbers[6] = {0, 2, 1, 0, 2, 1}; //我这里懒得生成随机数了 - -
- int i;
-
- adjust(numbers, 6);
-
- printf("\nsorted numbers are \n");
- for(i = 0; i < 6; i++) {
- printf("%d ", numbers[i]);
- }
-
- return 0;
- }
好吧虽然楼主觉得对于数字而言，会有比这更高效的排序算法的。
啊终于可以去睡觉啦！！！！！![]()
参考：
http://www.openhome.cc/Gossip/AlgorithmGossip/ThreeColorsFlags.htm
http://www.csse.monash.edu.au/~lloyd/tildeAlgDS/Sort/Flag/
| 
