归并排序 && 51Nod1019逆序数 && 最小的交换
一、归并排序
递归思路，将一个序列二分，使前半段有序，使后半段有序，然后使用双指针扫一遍使整段有序。
对于n个元素，每个元素都在排序1个元素，2个元素，4个元素，8个元素......的时候出现，因此复杂度是O(nlogn)。
二、求逆序数
在一个排列中，如果一对数的前后位置与大小顺序相反，即前面的数大于后面的数，那么它们就称为一个逆序。一个排列中逆序的总数就称为这个排列的逆序数。
如2 4 3 1中，2 1，4 3，4 1，3 1是逆序，逆序数是4。给出一个整数序列，求该序列的逆序数。
输入
第1行：N，N为序列的长度（n <= 50000) 第2 - N + 1行：序列中的元素（0 <= A[i] <= 10^9）
输出
输出逆序数
输入样例
4
2
4
3
1 输出样例
4
思路
考虑在每次归并两个有序序列的过程中，我们会将后面一个有序序列的部分元素前移，那么从后向前中间超越的元素与它成为一个逆序对，代码中为当前总位置j减去已经被分配的比它小的元素k，即超越的元素数。
1 #include<iostream> 2 #include<cstdio> 3 using namespace std; 4 int a[50020],b[50020]; 5 int n; 6 long long merge(int low,int mid,int high){ 7 int i=low,j=mid+1,k=low; 8 long long count=0; 9 while(i<=mid&&j<=high){ 10 if(a[i]<=a[j]){ 11 b[k++]=a[i++]; 12 } 13 else{ 14 b[k++]=a[j++]; 15 count+=j-k; 16 } 17 } 18 while(i<=mid){ 19 b[k++]=a[i++]; 20 } 21 while(j<=high){ 22 b[k++]=a[j++]; 23 } 24 for(i=low;i<=high;i++){ 25 a[i]=b[i]; 26 } 27 return count; 28 } 29 long long mergeSort(int x,int y){ 30 31 if(x<y){ 32 int mid=(x+y)/2; 33 long long count=0; 34 count+=mergeSort(x,mid); 35 count+=mergeSort(mid+1,y); 36 count+=merge(x,mid,y); 37 return count; 38 } 39 return 0; 40 } 41 int main(){ 42 cin>>n; 43 for(int i=0;i<n;i++){ 44 scanf("%d",&a[i]); 45 } 46 cout<<mergeSort(0,n-1); 47 return 0; 48 }
三、最小的交换
只能相邻元素交换，求让序列升序的最小交换次数。
我们不可避免的让大数向后交换，那么我们考虑最大的一个数，让其向后交换，肯定会交换到最后一位，交换的次数为后面比它小的数的个数，即包含它且它更大的逆序对数，再把次小的元素向后移动......最后的移动次数即为逆序对数。
代码同上
失业啃老第二年，熬夜玩手机中。。
