琪露诺的排序

前言：

依旧是OJ上的门槛题，当作复习用。这题主要考察的是排序里面的归并排序。

Description

笨蛋琪露诺喜欢用冰块搭积木。这天她用她的能力制造了N根冰柱作为材料，但这些冰柱显得参差不齐，不过好在她知道这些冰柱的高度。患有强迫症的小妖精琪露诺决定将这N根冰柱从小到大排列，不幸的是，琪露诺是个笨蛋，她只能将相邻的两根冰柱调换位置。现在她想知道她最少需要进行几次调换才能使这些冰柱变得有序。

Input

输入共两行。
第一行N(0<N<=500000)，代表冰柱的个数。
第二行N个数，代表每根冰柱的高度hi(0<hi<2^32)

Output

一个整数，代表琪露诺最少的调换次数。

Sample Input 1

4
4 3 2 1

Sample Output 1

6

思路：

为什么前面说这题一定要用归并排序呢，因为如果你不这样，用别的方法，比如冒泡排序什么什么的，你会发现超时了，因为他们的时间复杂度都是O(n2),而归并排序的时间复杂度只有O(N*log2N) 且非常稳定。这题的解法只需要在归并排序的基础代码上改一些就行了，这里先解释归并排序是怎么实现的。

归并排序分为两步：

1.分

(1)我们会得到一个长为N的数组，起始位置为low，末位置为high。
(2)判断low是否对于high。
(3)是则退出。
(4)否则令mid为low和high的中点，递归调用“分”函数，mid分别作为两个函数的末位置和起始位置。
(5)即为继续第一步

2.并

每次分完之后都会并一次，顺序自定义，由于分是递归调用的，所以先合并的是两个长度为1的数组，而后就是两长度为2的数组合并，直到数组对半合并

改进：

为了完成这道题目的要求仅仅这样还是不行的，我们需要一点小改动，我们需要改进的地方只有计算逆序对的方法，有上面概念可知，在并这个过程这，两个数组都是有序的，所以当第一个序列的第x个数比第二个序列的第y个数大时，就产生了N-x+1个逆序对，这在排序过程中就可以进行统计。

源码：

#include<iostream>
using namespace std;
long long int sum=0;
//并函数
void merge(long long int a[],long long int b[],int low,int mid,int high){
    int i=low,j=mid+1,k=low;
    while(i<=mid&&j<=high){
        if(a[i]<=a[j]){
            b[k++]=a[i++];
        }else{
            b[k++]=a[j++];
            sum+=mid-i+1;
        }
    }
    while(i<=mid){
        b[k++]=a[i++];
    }
    while(j<=high){
        b[k++]=a[j++];
    }
    for(int i=low;i<=high;i++){
        a[i]=b[i];
    }
}
//分函数
void msort(long long int a[],long long int b[],int low,int high){
    if(low==high){
        b[low]=a[low];
    }else{
        int mid=(low+high)/2;
        msort(a,b,low,mid);
        msort(a,b,mid+1,high);
        merge(a,b,low,mid,high);
    }
}
int  main(){
    int n;
    cin>>n;
    long long int a[n],b[n];
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    msort(a,b,0,n-1);
    cout<<sum;
    return 0;
}