1 问题
在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。 即输出P%1000000007。
比如数列{6，202，100，301，38，8，1}，有14个序列对；
比如数列{7, 5, 6, 4}，有5个序列对{7,5}，{7,6}，{7,4}，{5,4}，{6,4}；
2 分析
我们先了解下归并排序，前面博客有介绍 剑指offer之归并排序 ，我们分析数列{6，202，100，301，38，8，1}，
第一次归并后：{6,202},{100,301},{8,38},{1}，这里逆序对1对，就是我们把8插入了38前面，后面只有38一个数据，所以是一度
第二次归并后：{6,100,202,301}，{1,8,38}，这里逆序对有3对，我们把100插入了数组{6,202}之间，后面只有202一个元素，所以有一对逆序对，然后1插入了数组{8， 38}最前面，这里后面还有2个元素，所以这有2个逆序对。
第三次归并后：{1,6,8,38,100,202,301},这里逆序对有10对，把1出入了数组{6,100,202,301}最前面，后面有4个数据，所以4对，然后把8插入数组{6,100,202,301}的第二个数据，后面还有3个数据，就是3对，然后再把38插入数组{6,100,202,301}里面，后面还有3个数据，也就是还有3对逆序对
规律：我们把右边数组里面的元素插入左边数组元素的时候，插进去的位置后面到左边数组尾巴多有多少个元素，就有多少个逆序对，每插入依次，我们统计一次，依次累加。
3 代码实现
#include <stdio.h> int lastResult = 0; void merge(int* source, int* temp, int start, int mid, int end) { if (source == NULL || temp == NULL) { printf("merge source or temp is NULL\n"); return; } int i = start, j = mid + 1, k = start; int count = 0; while (i != mid + 1 && j != end + 1) { if (source[i] > source[j]) { temp[k++] = source[j++]; count = mid - i + 1; lastResult += count; } else temp[k++] = source[i++]; } while (i != mid + 1) temp[k++] = source[i++]; while (j != end + 1) temp[k++] = source[j++]; for(int h = start; h <= end; ++h) { source[h] = temp[h]; } return; } int static result = 0; void mergeSort(int* source, int* temp, int start, int end) { if (source == NULL || temp == NULL) { printf("mergeSort source or temp is NULL\n"); return; } if (start < end) { int mid = start + (end - start) / 2; mergeSort(source, temp, start, mid); mergeSort(source, temp, mid + 1, end); merge(source, temp, start, mid, end); } } void printDatas(int* datas, int len) { for (int i = 0; i < len; ++i) { printf("%d\t", datas[i]); } printf("\n"); } int main(void) { int source[] = {7, 5, 6, 4}; int temp[4]; int length = sizeof(source) / sizeof(int); mergeSort(source, temp, 0, length - 1); printf("lastResult is %d\n", lastResult % 1000000007); return 0; }
4 运行结果
lastResult is 5
这里时间复杂度是O（nlogn）,如果我们用暴力求解，时间复杂度就是O(n * n) .
