假设有一个数组, 它有n个元素,每一个不外乎是红、白、蓝3种颜色之一的代号, 就说是R, W, B好了。这些元素在数组中并没有依同样颜色的元素排在一起的方式来排列, 请写一个程序把这些元素排成所有蓝色在前, 然后是白色, 最后是红色的排列方式, 不过在写程序时要满足下面的条件

1. 不能用到额外的内存,换句话说,只能在数组之内用互换的方式完成。
2. 互换两个元素的动作要越少越好
3. 对于每一个元素而言,测试它是红, 白, 还是蓝的工作, 每种颜色最多只能做一次测试

在这个限制之下,请编写一个最快的程序

说明: 有些人很自然地会想到把蓝色当成1、白色当成2、红色当成3, 然后用排大小的程序把次序排出来,自然地蓝色在前, 白色居中, 红色最后了; 完全正确, 不过却违背了规定。也就是说, 互换两个元素的动作是不是太多了呢? 对每一个元素测试它的颜色的行为是否违反了要求呢? 对前者而言,不同的排序方法会有不同数目的互换动作。比如说,如果用选择法, 每次找到计i+1 ~ n中最小的值, 与第i个元素互换, 那么排序的动作只不过用了n-1次互换。但是对第三个限制而言, 就很难保证对每一个元素、每一种颜色都最多只测试次了

第三个条件需要仔细地说明, x[i]表示第i个元素。第三个条件是说, x[i] == R, x[i] == W, x[i] == B 这3个比较的任何一个都最多只能做一次。举个例子, 如果在决定观应该放在什么地方时,上述3个比较都各做一次,是正确的。任取两个或任取一个各做一次,也是正确的。但x[i] == R、x[i] == W、x[i] == R就是错的了, 因为对R的测试做了两次。

其实这个题目并不难, 把数组从头到尾查一次就可以做出结果, 那3个繁琐的条件, 不过是防止去用排序或“不够快”的方法来解题而已。

解答见three_flag.py