归并与逆序对(ly).cpp

归并排序算法

#include<iostream>
using namespace std;

int re;

void merge(int *a, int left, int mid, int right)    //默认是left<right
{
    int *l=new int[mid-left+1];
    int *r=new int[right-mid];
    for (int i=0; i!=mid-left+1; ++i)
        l[i]=a[left+i];
    for (int j=0; j!=right-mid; ++j)
        r[j]=a[mid+1+j];
    int i=0, j=0;
    for (int f=left; f<=right; ++f)
    {
        if (i!=mid-left+1 && j!=right-mid)
        {
           if (l[i]<=r[j])
           {
              re+=j;    //逆序对 
              a[f]=l[i];
              ++i;
           }
           else
           {
              a[f]=r[j];
              ++j;
           }
        }
        else if (i==mid-left+1)
        {
           a[f]=r[j];
           ++j;
        }
        else
        {
            re+=j;    //逆序对 
            a[f]=l[i];
            ++i;
        }
    }
    delete []l;
    delete []r;
}

void merge_sort(int *a ,int left, int right)
{
    int mid=(left+right)/2;
    if (left<mid)
       merge_sort(a, left, mid);
    if (mid+1<right)
       merge_sort(a, mid+1, right);
    merge(a, left, mid, right);
}


int main()
{
    int a[10] = {1, 2, 3, 4, 1, 1, 2, 6, 7, 9};
    merge_sort(a, 0, 9);    //0-9计算的是10个元素 
    for (int i=0; i!=10; ++i)
        cout <<a[i] <<" ";
    cout <<endl;
    cout << "Sum of reverse pairs is " << re << endl;
    system("pause");
    return 0;
}