POJ-排序-归并排序与逆序对

排序：归并排序与逆序对

一、概念

归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。

时间复杂度：O(nlogn)

二、算法描述

1.将数组拆分成单个元素，两两归并。

2.对于两组同向有序数组，首先判断两组数的首位的大小，并将较小的数保留到一个新数组中。

3.再比较较小组数的第二位和另一组数的第一位，仍然保留较小的数，这样就保证新数组的有序，需要注意的是当任意一组数为空时，就自然将另一组数的剩下数接到新数组后（因为剩下的树肯定比刚放进去的大）。

三、逆序对

逆序对问题设 A 为一个有 n 个数字的有序集 (n>1)，其中所有数字各不相同。如果存在正整数 i, j 使得 1 ≤ i < j ≤ n 而且 A[i] > A[j]，则 A[i], A[j]这个有序对称为 A 的一个逆序对，也称作逆序数。 

例如，数组（3，1，4，5，2）的逆序对有(3,1),(3,2),(4,2),(5,2)，共4个。

四、归并排序与逆序对

因为在排序的合并过程中是将两组有序数进行比较，所以根据逆序对的定义，在数组下标 i 小于 j 时，如果有 a[i] 大于 a[j] 就可以知道下标 i 后面所有数都与 a[j] 构成逆序数，只需添加一句求和语句即可求出逆序数了；

例题 POJ1804 Brainman

解题思路

最简单的关于逆序对的题目，题目大意是给出一个序列，求最少移动多少步能使它顺序，规定只能相邻移动。
相邻移动的话，假设a，b 相邻，若a<b 交换会增加逆序数，所以最好不要做此交换；若a==b 交换无意义，也不要进行此交换；a>b时，交换会减少逆序，使序列更顺序，所以做交换。
由上可知，所谓的移动只有一种情况，即a>b，且一次移动的结果是逆序减1。假设初始逆序是n，每次移动减1，那么就需要n次移动时序列变为顺序。所以题目转化为直接求序列的逆序便可以了。

AC代码

#include<cstdio>
int a[1005];//存储数串的数组
int t[1005];//排好序的数组
int ans;//逆序对数

void merge(int l, int m, int r)//因为起点和终点不变，所以用i，j来表示可变的下标
{
    int k = l, i = l, j = m + 1;
    while (i <= m && j <= r)//分解数组的首元素进行比较，两个数组分别为[l,m][m+1,r]
    {
        if (a[i] > a[j])//构成逆序对
        {
            t[k++] = a[j++];//将较小的元素加入排序后的数组,并移动到下一元素
            ans = ans + m - i + 1;//从i到middle的值都大于a[j]，所以逆序对增加m-i+1
        }
        else
        {
            t[k++] = a[i++];
        }
    }
    while (i <= m) t[k++] = a[i++];//若左边还有剩下的
    while (j <= r) t[k++] = a[j++];
    for (i = l; i <= r; i++)a[i] = t[i];//更新原数组为合并后的数组
}

void mergeSort(int l,int r)//归排
{
    if (l < r)//递归终止条件
    {
        int m = (l + r) / 2;
        mergeSort(l, m);
        mergeSort(m + 1, r);//此时已经通过递归全部拆分
        merge(l, m, r);//从单元素开始合并
    }
}

int main()
{
    int T, n, cnt = 1;
    scanf("%d", &T);
    while (T--)
    {
        ans = 0;
        scanf("%d", &n);
        for (int i = 0; i < n; i++)
            scanf("%d", &a[i]);
        mergeSort(0, n - 1);
        printf("Scenario #%d:
", cnt++);
        printf("%d

", ans);
    }
    return 0;
}

例题 POJ2299 Ultra-QuickSort

解题思路

简单直接的归并排序求逆序数，和上一题一模一样。难点是n < 500000，所以答案用int32会WA，要用int64，用long long int也可以，取值范围一样的，printf函数对应I64d和lld。

AC代码

#include<cstdio>
const int N = 500500;
int a[N];
int t[N];
__int64 ans;

void merge(int l, int m, int r)
{
    int k = l, i = l, j = m + 1;
    while (i <= m && j <= r)
    {
        if (a[i] > a[j])
        {
            t[k++] = a[j++];
            ans += m - i + 1;
        }
        else
        {
            t[k++] = a[i++];
        }
    }
    while (i <= m)t[k++] = a[i++];
    while (j <= r)t[k++] = a[j++];
    for (int i = l; i <= r; i++)a[i] = t[i];
}

void mergeSort(int l, int r)
{
    int m = (l + r) / 2;
    if (l < r)
    {
        mergeSort(l, m);
        mergeSort(m + 1, r);
        merge(l, m, r);
    }
}

int main()
{
    int n;
    scanf("%d", &n);
    while (n != 0)
    {
        ans = 0;
        for (int i = 0; i < n; i++)scanf("%d", &a[i]);
        mergeSort(0, n-1);
        printf("%I64d
", ans);
        scanf("%d", &n);
    }
    return 0;
}