哈哈，杨大哥一直都是个爽快的人，我叫施鹏。以后请杨大哥多多指教啊

英文不行的帮顶下

我湿了，给跪
不得不说这个太打击人了

想模拟过程结果无限混乱，这是何等的差距……

[ 本帖最后由 随风飘荡 于 2012-7-23 14:43 编辑 ]

我分析一下：
对于给定：
2 2 1 3 3 3 2 3 1  
其排序目标是：
1 1 2 2 2 3 3 3 3

其中“不乖”的数有两类，
变大的(ct)： <1,2> <1,2> <2,3> <2,3>
变小的(cb)： <2,1> <3,2> <3,1>

其实很容易想到 要么ct==cb, 要么|ct-cb|==1；               
也可以发现：ct与cb集合中有很多相对称的地方：                  
ct中有：<1,2> <2,3>                           
对应cb中有：<2,1> <3,2>                       

在交换只要他们相互交换就行了，剩下的仅仅是1,2,3组成的三组数对，  只要交换两次；                     
或者其中的两个1，2；1，3；2，3组成的两组数对，只要交换1次；                    
还有要么没剩下（不交换），不可能剩下一对的……            
这样的话交换的次数就是 max(cb,ct);

上面证明的只是3个数排序，对于更多的数，好像这个理论不太对；

比如 排序：3 1 4 2四个数， 目标：1 2 3 4
cb=ct=2;
= =! 不过我交换两次怎么都排不了啊！ = =！


[ 本帖最后由 回首依依 于 2012-7-23 14:28 编辑 ]

深圳这边刮个风下个雨，我那脆弱的网络直接断了，哥昨天郁闷了一下午加一晚上！

我的代码里倒是有交换的步骤，晚上我贴出来给大家看看，欢迎批评指正

施鹏好，指教谈不上，相互交流学习吧！

回首依依提到的问题确实存在，呵呵感谢指正。我有时间检查一下到底遗漏了什么，搞清楚这一点也许我真该写一篇论文了呵呵

真心佩服版主的编程能力，代码写得真漂亮！ 以后大家一起交流，互相促进

呵呵谢了，再次感谢你的指正。我来这里的目的亦是为了发现自己的不足，学习提高。以后多交流！

[ 本帖最后由 beyondyf 于 2012-7-23 19:37 编辑 ]

3种数，分成两个目标，先排列较少的那个目标，并且输出了交换步骤，然后统计另外一个目标，得出结果。

#include<stdio.h>
#include<stdlib.h>

int number[3];
int position[3];

#define STATE(x,y,z) x>y?(x>z?1:3):(y>z?2:3)
#define SWAP(x,y) do{x^=y;y^=x;x^=y;}while(0)

void printf_store(int *p , int n)
{
    int i = 0;
    while (i<n)
    {
        printf("%d ",*(p+i++));
    }
    printf("\n");
}

int belongto(int i)
{
    if (i<position[1])return 1;
    if (i>=position[2])return 3;
    else return 2;
}

void sort_function()
{
    int N, *store, target1, target2, chg, state;
    int i = 0, j = 0, t = 0, m = 0, flag = 0, total = 0;
    if (NULL==(store=(int *)malloc(1000*sizeof(int)))) return;
    for (scanf("%d",&N); i<N; scanf("%d",store+i++));
    for (i=0; i<N; number[*(store+i++)-1]++);   // learned this skill from BEYONDYF!!
    state = STATE(number[0],number[1],number[2]);
    position[1] = number[0], position[2] = position[1] + number[1];
    target1 = state%3 + 1;
    target2 = target1%3 + 1;
    if (number[target1-1]>number[target2-1]) SWAP(target1,target2);
    for(i=0; number[target1-1]!=0; i++)
    {
        if(*(store+i)==target1)
        {
            if (i>=position[target1-1] && i<position[target1-1]+number[target1-1])
            {
                t++;
                printf("no change!\n");
                printf_store(store,N);
                if (t==number[target1-1]) break;
            }
            else
            {
                while (target1==*(store+position[target1-1]+j)) j++;
                chg = belongto(i);
                for (m=j,flag=0; m<number[target1-1]; m++)
                {
                    if (chg==*(store+position[target1-1]+m))
                    {
                        flag = 1;
                        break;
                    }
                }
                flag<1?(m=j):1;
                *(store+i) = *(store+position[target1-1]+m);
                *(store+position[target1-1]+m) = target1;
                total++;
                printf("be changed!\n");
                printf_store(store,N);
                if (j==number[target1-1]-1) break;
            }
        }
    } //target1 has been stored!
    for (i=0; i<N; i++)
    {
        if (i == position[target1-1]) i += number[target1-1];
        if(i>=N)break;
        if(*(store+i)==target2)
        {
            if (i<position[target2-1]||i>=position[target2-1]+number[target2-1]) total++;
        }
    } // how many target2 were not be the right locality!
    printf("%d\n", total);
    free(store);
}

void main()
{
    sort_function();
}

我自己都跪了，估计这种代码没人愿意看吧。

[ 本帖最后由 demonleer 于 2012-7-24 10:16 编辑 ]