经典算法(9) 从归并排序到数列的逆序数对（微软笔试题）

首先来看看原题

微软2010年笔试题

在一个排列中，如果一对数的前后位置与大小顺序相反 ，即前面的数大于后面的数，那么它们就称为一个逆序数对。一个排列中逆序的总数就称为这个排列的逆序 数。如{2，4，3，1}中，2和1，4和3，4和1，3和1是逆序数对，因此整个数组的逆序数对个数为4，现在给定 一数组，要求统计出该数组的逆序数对个数。

计算数列的逆序数对个数最简单的方便就最从前向后依 次统计每个数字与它后面的数字是否能组成逆序数对。代码如下：

#include <stdio.h>
int main()
{
    printf("     数列的逆序数对 \n");
    printf(" -- by MoreWindows( http://blog.csdn.net/MoreWindows ) --\n\n");      

    const int MAXN = 8;
    int a[MAXN] = {1, 7, 2, 9, 6, 4, 5, 3};  

    int nCount = 0;
    int i, j;
    for (i = 0; i < MAXN; i++)
        for (j = i + 1; j < MAXN; j++)
            if (a[i] > a[j])
                nCount++;  

    printf("逆序数对为: %d\n", nCount);
}

运行结果如下：

这种方法用到了双循环，时间复杂度为O(N^2)，是一个不太优雅的方法。因此我们尝试用其它方法来解决 。

在《白话经典算法系列之五归并排序的实现》中观察归并排序——合并数列(1，3，5)与(2，4)的 时候：

1．先取出前面数列中的1。

2．然后取出后面数列中的2，明显！这个2和前面的3，5都 可以组成逆序数对即3和2，5和2都是逆序数对。

3．然后取出前面数列中的3。

4．然后取出后 面数列中的4，同理，可知这个4和前面数列中的5可以组成一个逆序数对。

以上是小编为您精心准备的的内容，在的博客、问答、公众号、人物、课程等栏目也有的相关内容，欢迎继续使用右上角搜索按钮进行搜索数组
， fibonacci数列
， java 笔试题
， 前面
， 笔试题
， 个数
， 算法 最大子数列
， 一个
， 逆序环视
， 逆序
， 归并方法
， 逆序arraylist
， 递减数列
数列
归并排序求逆序数、归并排序 逆序数、归并求逆序数、归并 逆序数、归并排序，以便于您获取更多的相关知识。