首页 / 软件开发 / 数据结构与算法 / 经典算法（9） 从归并排序到数列的逆序数对（微软笔试题）

经典算法（9） 从归并排序到数列的逆序数对（微软笔试题）2014-01-03 csdn MoreWindows首先来看看原题

微软2010年笔试题

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

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

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

"）;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
", 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可以组成一个逆序数对。