//归并排序  2 
int a[1000002],b[1000002];
__int64 num;
void merge(int *a,int p,int q,int r)
{int i,j=p;
 int startA=p,endA=q-1,startB=q,endB=r;
 while(startA<=endA&&startB<=endB)   
 {
  if(a[startA]<=a[startB]){b[j]=a[startA];j++;startA++;}    
  else
  {//1   9     10       4 5 12
   //  startA           q  
   b[j]=a[startB];j++;startB++;    
   num+=q-startA;//逆序数 
  }
 }
 while(startA<=endA){b[j]=a[startA];startA++;j++;}
 while(startB<=endB){b[j]=a[startB];startB++;j++;} 
 for(i=p;i<=r;i++)a[i]=b[i];   
}
void msort(int *a,int n)
{//a[0],...a[n-1]
  int n0,seg,lastseg,s0,i,j,m;
   n0=n;seg=1;lastseg=1;
   //开始有n段，每段长 seg=1，最后1段长lastseg=1 
  num=0;
  while(n0>=2)
  {// 2  1  9  3  7  8 10 9  4 5 6  m=11 seg=1 lastseg=1
   // 1 2  3 9  7 8   9 10    4 5 6  n0=5 seg0=2 lastseg=3 
   m=n0;//两段合为1段  m段合为n0=m/2段 
   n0/=2;s0=seg*2;
   if(m%2==0)
   {  //有 n0 seg  每seg 长s0 
     for(i=1,j=0;i<=n0;i++,j+=s0)
     { if(i<n0)merge(a,j,j+seg,j+s0-1);
       else merge(a,j,j+seg,n-1);
     }    
     lastseg=seg+lastseg;
     seg=s0;
   }   
   else
   {//   1 2     3  4        5 6 7
    for(i=1,j=0;i<=n0;i++,j+=s0)
     merge(a,j,j+seg,j+s0-1);   
    j=n-lastseg-s0;
    merge(a,j,n-lastseg,n-1);    
    seg=s0;lastseg+=s0;  
   }
   }
}

• 谢大牛！我看看我的问题在哪儿。 (0) testdirk 2007-02-27 17:54:03
  • 又仔细看了下发现我的问题太幼稚了，我输出的时候用的"%d"，应该是"%64Id"，我把这个给弄到输入离去了，就错了。AC了，顶一下！再次谢楼上的大牛！ (0) testdirk 2007-02-27 18:00:47
    • 在这也提醒下后来人，用_int64的时候不能用GCC编译，会CE，具体为什么不知，需要用C编译器就Okla. (0) Nowitzki 2007-02-27 18:03:23
• 非常感谢！ (0) zouwq0209 2008-07-09 15:01:26
• Re:归并排序 逆序数 第2 版 (1398) 6736881 2009-11-13 23:37:33