有红黄蓝三种颜色的球各m个, 一共N=3m个球, 次序任意. 只通过操作exchange(i, j),
如何排列成 "红黄蓝红黄蓝红黄蓝..." 的顺序?

解法一:
比较直观的O(N^2)算法是: 对第i=1, 2, ..., N个位置, 从第i+1到第N个球中选取颜色正确的球. 相当于选择排序.

解法二:
最佳算法应该是O(N). 用三个指针. 对每个球, 如果颜色和所在位置应该放的颜色相同, 则看下一个; 否则, 放到该种颜色的指针指到的位置, 同时增加指针. 代码如下. 

测试可以用3N个球的所有排列序列. 可能的情况是:

     N   permutations
     ----------------
     1   6
     2   90
     3   1679
     4   34650
     5   756756
     ... ...

// The color expected at position i.
// 0 - R, 1 - G, 2 - B
int getcolor(int i) { 
    return i % 3;
}

void exchange(int &i, int &j) {
    int tmp = i;
    i = j;
    j = tmp;
}

void arrange(vector<int> &A) {
    int i = 0, n = A.size();
    int kr = 0, kg = 1, kb = 2;
    
    while (i < n) {
        if (A[i] == 0) {
            if ( getcolor(i) == 0 ) { ++ i; }
            else {
                exchange(A[i], A[kr]);
                kr += 3;
            }

        } else if (A[i] == 1) {
            if ( getcolor(i) == 1 ) { ++ i; }
            else {
                exchange(A[i], A[kg]);
                kg += 3;
            }
        
        } else { // A[i] == 2
            if ( getcolor(i) == 2 ) { ++ i; }
            else {
                exchange(A[i], A[kb]);
                kb += 3;
            }
        
        }
    }
}

// A more compact version of arrange().
void arrange2(vector<int> &A) {
    int i = 0, n = A.size();
    int kr = 0, kg = 1, kb = 2;
    
    while (i < n) {
        if (A[i] == getcolor(i)) { 
            ++ i;
        } 
        else {
            if (A[i] == 0) {
                exchange(A[i], A[kr]);
                kr += 3;
            }
            else if (A[i] == 1) {
                exchange(A[i], A[kg]);
                kg += 3;
            }
            else { // A[i] == 2
                exchange(A[i], A[kb]);
                kb += 3;
            }
        }
    }
}


解法三:
另外一种O(N)解法是先用荷兰三色旗排序法排序, 再交换. 例如, 从RRRRGGGGBBBB变到RGBRGBRGBRGB可以这样：

RRRRGGGGBBBB =>
RGRRRGGGBBBB =>
RGBRRGGGRBBB =>
RGBRRRGGGBBB
...

代码如下:

void arrange3(vector<int> &A) {
    int n = A.size();

    // step 1. sort 3 colors.
    int L = 0, R = n-1, p = 0;
    while (p <= R) {
        if (A[p] == 0) {
            swap(A[p], A[L]);
            ++ L; ++ p;
        }
        else if (A[p] == 2) {
            swap(A[p], A[R]);
            -- R;
        }
        else {
            ++ p;
        }
    }

    // step 2. exchange
    for (int i = 0, j = n/3; i < n; i += 3, -- j) {
        exchange(A[i+1], A[i+j]);     // exchange 2nd R with first G
        exchange(A[i+2], A[i+2*j]);   // exchange 3rd R with first B
        exchange(A[i+j+1], A[i+2*j]); // exchange 1st G with last R
    }
}


比较方法二和方法三, 方法二每个球走了一遍, 方法三走了两遍. 都是O(N), 但是方法二应该比方法三快一倍.

推广: 容易看到, 解法一, 解法二及解法三的第二个步骤可以推广到N种颜色的球, N>=2.

上述所有代码都经过测试.