algorithm - 毛里求斯国旗问题

Question

我已经为 Dutch national flag problem 做了一个解决方案已经。

但这一次，我想尝试一些更难的事情:毛里求斯国旗问题 - 4 种颜色，而不是 3 种颜色。有什么有效算法的建议吗？

毛里求斯国旗问题基本上侧重于如何根据毛里求斯国旗的颜色顺序(红、蓝、黄、绿)对给定的成对列表进行排序。并且数字也必须按升序排序。

方案编程示例输入:

( (R . 3) (G . 6) (Y . 1) (B . 2) (Y . 7) (G . 3) (R . 1) (B . 8) )

输出:

( (R . 1) (R . 3) (B . 2) (B . 8) (Y . 1) (Y . 7) (G . 3) (G . 6) )

Answer 1

这是我想出的。我没有使用颜色，而是使用了数字。

// l  - index at which 0 should be inserted.
// m1 - index at which 1 should be inserted.
// m2 - index at which 2 should be inserted.
// h  - index at which 3 should be inserted.
l=m1=m2=0;
h=arr.length-1
while(m2 <= h) {
    if (arr[m2] == 0) {
        swap(arr, m2, l);
        l++;

        // m1 should be incremented if it is less than l as 1 can come after all
        // 0's
        //only.
        if (m1 < l) {
            m1++;
        }
        // Now why not always incrementing m2 as we used to do in 3 flag partition
        // while comparing with 0? Let's take an example here. Suppose arr[l]=1
        // and arr[m2]=0. So we swap arr[l] with arr[m2] with and increment l.
        // Now arr[m2] is equal to 1. But if arr[m1] is equal to 2 then we should
        // swap arr[m1] with arr[m2]. That's  why arr[m2] needs to be processed
        // again for the sake of arr[m1]. In any case, it should not be less than
        // l, so incrmenting.
        if(m2<l) {
            m2++;
        }       
    }
    // From here it is exactly same as 3 flag.
    else if(arr[m2]==1) {
        swap(arr, m1, m2)
        m1++;
        m2++;           
    }
    else if(arr[m2] ==2){
        m2++;
    }
    else {
        swap(arr, m2, h);
        h--;
    }           
}


}

同样我们可以写五个标志。

    l=m1=m2=m3=0;
    h= arr.length-1;
    while(m3 <= h) {
        if (arr[m3] == 0) {
            swap(arr, m3, l);
            l++;
            if (m1 < l) {
                m1++;
            }
            if(m2<l) {
                m2++;
            }
            if(m3<l) {
                m3++;
            }

        }
        else if(arr[m3]==1) {
            swap(arr, m1, m3);
            m1++;
            if(m2<m1) {
                m2++;
            }
            if(m3<m1) {
                m3++;
            }   

        }
        else if(arr[m3] ==2){
            swap(arr,m2,m3);
            m2++;
            m3++;
        }
        else if(arr[m3]==3) {
            m3++;
        }
        else {
            swap(arr, m3, h);
            h--;
        }   
    }