昨天看到有人问排序的问题了, 个人感觉归并排序是比较强大的 适用于很多情况 分享下 曾经写过的 归并排序: 以分治为主要思想 不断二分, 两个相邻的 数组进行归并 得出最小步数。 #include<cstdio> #include<cstring>
long long a[500010],b[500010],num;
long long merge_sort(long long *A,int x,int y,long long *T)
{
if(y-x>1)
{
int m = (x+y)/2;
int p = x,q = m,i = x;
merge_sort(A,x,m,T);
merge_sort(A,m,y,T);
int ps=x;
while(p<m||q<y)
{
if(q>=y||(p<m&&A[p]<=A[q]))
T[i++] = A[p++],ps++;
else
{
num+=m-p;
//printf("%d.%d.%d.\n",num,A[p],A[q]);
T[i++] = A[q++];
}
}
for(int i = x; i < y; i++)
A = T;
}
}
int main()
{
int n;
while(scanf("%d",&n)&&n)
{
for(int i = 0; i < n; i++)
scanf("%lld",&a);
num=0;
memset(b,0,sizeof(b));
merge_sort(a,0,n,b);
printf("%lld\n",num);
}
return 0;
} |