学步园

利用归并排序求数组总逆序。

#include <iostream><br /> using namespace std;<br /> int original[500005],temp[500005];<br /> __int64 reverse;<br /> void Merge(int first,int mid,int last)<br /> {<br /> int a=first,b=mid+1,p=first;<br /> while((a<=mid)&&(b<=last))<br /> {<br /> if(original[a]<original[b])<br /> {<br /> temp[p++]=original[a++];<br /> }<br /> else<br /> {<br /> temp[p++]=original[b++];<br /> reverse+=mid-a+1;//统计逆序数<br /> }<br /> }<br /> while(a<=mid) temp[p++]=original[a++];<br /> while(b<=last) temp[p++]=original[b++];<br /> for(int i=first;i<=last;i++)<br /> {<br /> original[i]=temp[i];<br /> }<br /> }<br /> void MergeSort(int first,int end)//第一个元素和最后一个元素的下标<br /> {<br /> int mid=(first+end)/2;<br /> if(first<end)<br /> {<br /> MergeSort(first,mid);<br /> MergeSort(mid+1,end);<br /> Merge(first,mid,end);<br /> }<br /> }<br /> int main()<br /> {<br /> int n;<br /> while(scanf("%d",&n)&&n)<br /> {<br /> reverse=0;<br /> for(int i=0;i<n;i++)<br /> {<br /> scanf("%d",&original[i]);<br /> }<br /> MergeSort(0,n-1);<br /> printf("%I64d/n",reverse);<br /> }<br /> return 0;<br /> }<br />