归并排序与求逆序对

60 阅读 0 评论 40 点赞

我是靠谱客的博主忧心冰棍，最近开发中收集的这篇文章主要介绍归并排序与求逆序对，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

1，归并排序

归并排序的基本思想是：将数组分段处理，然后将不同数据段重新组合起来。比如现在有这么一个数组：
6， 3，5，8，2 ，9，7，4
我们先把它分为两段
即 6，3，5，8 和 2，9，7，4
之后，每段继续拆分为
6，3 和 5，8
以及 2，9 和 7，4
好，我们继续拆分，再接着拆不就只有一个数了吗？一个数是不用比较的呀！所以这时就是我们的递归终止条件（如果用递归的话）。
之后进行合并，合并的时候首先每两个数字进行合并，合并 6 和 3 ，两数进行比较，小的那个放在前面，大的那个放在后面，两两合并后的结果为
3，6 和 5，8 和 2，9 和 4，7
接着将3，6 和 5，8 合并起来，即 3，5，6，8
2，9 和 4，7 也同样。合并后为 2，4，7，9
最后将 3，5，6，8 和 2，4，7，9 合并起来
得到：2，3，4，5，6，7，8，9
感觉整个过程是自顶向下拆分，之后从底往上合并。从递归程序来看可能没这么清晰，但是内里思想就是这样的
贴一下 y总总结的模板

#include <iostream>
using namespace std;

const int N=100010;
int q[N], tmp[N];

void merge_sort(int p[], int l, int r)
{
    if(l >= r) return;
    int mid= l+r >> 1;
    
    merge_sort(p, l, mid), merge_sort(p, mid+1, r);
    
    int k=0, i=l, j=mid+1;
    while(i <= mid && j <= r)
    {
        if(p[i] >= p[j]) tmp[k ++] = p[j ++];
        else tmp[k ++] = p[i ++];
    }
    while(i <= mid) tmp[k ++] = p[i ++];
    while(j <= r) tmp[k ++] = p[j ++];
    
    for(i = l, j = 0; i <= r; i++, j++)
        p[i] = tmp[j];
}

int main()
{
    int n;
    scanf("%d",&n);
    
    for(int i=0; i<n; i++)
    {
        scanf("%d",&q[i]);
    }
    
    merge_sort(q, 0, n-1);
    
    for(int i=0; i<n; i++)
    {
        printf("%d ",q[i]);
    }
    
    return 0;
}

2，计算数组中的逆序对

这个题目有一个基础版本，还有进阶版本
一个进阶版本链接: 逆序对.
感兴趣的童鞋自己去做一下，这里只分析基础版本。

题目：

给定一个长度为n的整数数列，请你计算数列中的逆序对的数量。

逆序对的定义如下：对于数列的第 i 个和第 j 个元素，如果满足 i < j 且 a[i] > a[j]，则其为一个逆序对；否则不是。

输入格式
第一行包含整数n，表示数列的长度。
第二行包含 n 个整数，表示整个数列。

输出格式
输出一个整数，表示逆序对的个数。

数据范围
1≤n≤100000

输入样例：
6
2 3 4 5 6 1
输出样例：
5

题目分析：

这道题是这样婶儿的，就是找这个数组里面前面数比后面数大的对数。当然可以不用归并排序做，我们主要讲一下如何用归并来做。

用归并算法来做的话，因为我们每次都是合并两个数组，现在假设只剩两个数组需要合并了，也就是说，一共 N 个数，现在有两个长度为 N/2 的子数组需要合并，因为是用递归的方法排序，所以到这步的时候，我们应该已经知道左边数组和右边数组内的逆序对数了（在前面递归的时候知道的，大家可以仔细想一想递归过程），现在需要知道的就是两个数组之间的逆序对数。

注：总的逆序对数=左边数组逆序对数+右边数组逆序对数+两个数组之间的逆序对数。

两个数组之间的逆序对数怎么求呢？因为现在这两个数组都是排好序的状态了，因为合并的时候我们在左右数组各放一个指针 i 和 j，然后比较指针所指当前值的大小，把小的那个放到备用数组 tmp[ ] 中去，现在假设左边数组中第 i 个数比右边数组第 j 个数要大，说明 i 及其之后的所有数都大于第 j 个数，所以对于此时的 j 来说，逆序对有 mid-i+1 个，其中 mid 为左子数组最后一个数的下标。将每个 j 对应的逆序对数加起来，就是我们要求的两数组之间的逆序对数啦。这些都可以在递归循环里面完成，相比上面的代码其实就加了一行代码。

代码如下：

#include <iostream>
using namespace std;

typedef long long ll;

const int N=100010;
int p[N],tmp[N];

ll merge_sort(int q[], int l, int r)
{
    if(l >= r) return 0;
    int mid = l + r >> 1;
    int k = 0, i = l, j = mid + 1;
    
    ll res = merge_sort(q, l, mid) + merge_sort(q, mid + 1, r);
    
    while(i <= mid && j <= r)
    {
        if(q[i] <= q[j]) tmp[k ++] = q[i ++];
        else 
        {
            tmp[k ++] = q[j ++];
            res += mid - i + 1;
        }
    }
    while(i <= mid) tmp[k ++] = q[i ++];
    while(j <= r) tmp[k ++] = q[j ++];
    
    for(int i = l, j = 0; i <= r; i ++, j++) q[i] = tmp[j];
    
    return res;
}

int main()
{
    int n;
    scanf("%d",&n);
    for(int i; i < n; i ++)
    {
        scanf("%d",&p[i]);
    }
    
    cout << merge_sort(p, 0, n-1) << endl;
    
    return 0;
}