|
int count(int *a,int *tmp,int left,int right);
int merge_count(int *a,int *tmp,int left,int middle,int right);
int count(int *a,int left,int right)
{
int tmp[50];
return count(a,tmp,left,right);
};
int count(int *a,int *tmp,int left,int right)
{
int all=0;
if(left<right)
{
int middle=(left+right)/2 ;
int result1,result2;
result1=count(a,tmp,left,middle);
result2=count(a,tmp,middle+1,right);
all=merge_count(a,tmp,left,middle, right);
return all=all+result1+result2;
}
return all;
}
int merge_count(int *a,int *tmp,int left,int middle,int right)
{
int leftend=middle;
middle++;
int count=0;
int temppos=left;
int num=right-left+1;
while(left<=leftend&&middle<=right)
{
if(a[left]<a[middle])
tmp[temppos++]=a[left++];
else{
count=count+(leftend-left+1);
tmp[temppos++]=a[middle++]; }
}
while(left<=leftend)
tmp[temppos++]=a[left++];
while(middle<=right)
tmp[temppos++]=a[middle++];
for(int i=0;i<num;i++)
{
a[right]=tmp[right];
right--;
}
return count;
}
归并排序的一个改进，在归并的同时多了一个计算逆序数的动作。另外请教大家为什么我在第一个过程中写
int tmp[right-left+1]提升错误啊 | 
转播
