Wo ye kan bu dong Ya！

这样吧，我先把AC代码贴上来。代码很简单，但证明这段代码可以完成任务的理论分析就不那么容易了。各位先看看。

这段代码只要修改宏即可改变元素范围，比如如果要求元素范围是1－10，那么将宏修改为10就可以解决。

#include<stdio.h>
#define MAX_NUM    3
int cal(int * a, int n)
{
    int c[MAX_NUM + 1] = {0}, ct = 0, cb = 0, i, j, k;
    for(i = 0; i < n; c[a[i++]]++);
    for(i = j = 0; i < n; j++)
    for(k = 0; k < c[j]; k++, i++) a[i] > j ? ct++ : a[i] < j ? cb++ : 0;
    return ct > cb ? ct : cb;
}

int main()
{
    int a[1024], n, i;
    for(scanf("%d", &n), i = 0; i < n; scanf("%d", &a[i++]));
    printf("%d\n", cal(a, n));
    return 0;
}

 

是英文啊，有点看不懂意思

....太牛了，beyondyf，你只分为两类啊，天啊。。佩服

讲讲分类这两类的理由啊~~~。。。只知道c[j]用来统计个数，并且j代表改数~~其它的不知所云。。。

#include<stdio.h>
#define N 10
void main()
{
    int a[N]={9,2,2,1,3,3,3,2,3,1};
 int b[N]={9,2,2,1,3,3,3,2,3,1};
 int re=0,i,j,t;
    for(i=0;i<N;i++)
  for(j=i;j<N;j++)
   if(a[i]>a[j]) { t=a[i];  a[i]=a[j];  a[j]=t;}

    for(i=0;i<N;i++)   printf("%d\t",a[i]);
    printf("\n");
 for(i=0;i<N;i++)   if(a[i]!=b[i])   re+=1;

 if(re%2==1) re+=1;

 printf("最少交换几次 :%d\n",re/2);
}
//本人自己想的算法，不知道对吗？？和大家分享下

杨大哥的代码依旧是那么精彩养眼啊！

c数组的作用毋庸置疑，用来统计a中各个元素的个数，c[0]无作用，因为0不参加排序。

ct和cb我想应该是top和below的意思，ct的意思是统计整个数列中 比 某个位置的目标元素大的元素个数，比如说某个数列的前3位排序好了以后应该都为1，即该数列中1的个数为3，而未排序的数列前3位为1,3,2，那么在前3位中，ct = 2，因为3和2都大于1。

cal函数的作用就是统计整个数列中不乖（不乖指的是不在自己应该在的位置上）的元素分别有多少个，即ct和cb的数目分别为多少，若把大者处理完，那么整个数列就排序好了。

理论分析等小曹上。

现在在公司，晚上把我的代码贴出来，请杨大哥指正。

一直AC不了，气死我了。

呵呵，关于这个理论的证明可以写篇小论文了。结论很简单，但论证过程比较复杂。

关于这个问题的结论是：最少交换次数等于需要向前交换的元素（该元素所处位置靠后于它应该处于的位置范围）数量和需要向后交换的元素数量中的最大值。

唉，我不喜欢长篇大论，但有些问题话少了又说不清楚（我写过的长篇都是这个原因）。

如果各位只想知道怎么做，那记住这个结论就行了。这里喜欢理论的人并不多，我费劲写半天没人看也挺没劲的，呵呵。

呵呵，和兄弟你交流真是太痛快了。连我的变量取名含意都能猜透。因为我是使用矩阵来分析的，计算的是上三角元素和与下三角元素和，所以变量名就取了top和button的意思。我的英语并不是很好，也许取名不太合适，请指正

小曹和我的思维方式很不相同，应该会从另一个角度分析，我也很期待看看他的想法

对了，demonleer兄弟怎么称呼？