我们从一道面试题入手开始
微软面试题2010年：
在一个排列中，如果一对数的前后位置与大小顺序相反，即前面的数大于后面的数，那么它们就称为一个逆序数对。
一个排列中逆序的总数就称为这个排列的逆序数。如{2，4，3，1}中，2和1，4和3，4和1，3和1是逆序数对，
因此整个数组的逆序数对个数为4，现在给定一数组，要求统计出该数组的逆序数对个数。
解：看到逆序数的次数有没有想到我们常见的归并排序呢，逆序数的求解本文的分享就是从归并排序衍生出来的一种方法。
比如我们现在有两个顺序序列：
arr1[] = {1,3,5}
arr2[] = {2,2}
组成的序列位：1,3,5,2,2
当arr1[i] < arr2[j]时，看不出来是否存在逆序
但是当arr1[i] > arr2[j] ,则此时构成逆序对;
算法实现时还有个点不能遗漏，比如arr2在合并排序中因为较小早早被合并进去，那arr1就会有剩余的元素，剩余的元素和原来的arr的每一个元素都构成逆序对
/*================================================================ * Copyright (C) 2020 baichao All rights reserved. * * 文件名称：mergeSort.cpp * 创 建 者：baichao * 创建日期：2020年12月28日 * 描 述： * ================================================================*/#include <iostream>int inverNumCount = 0;int sort(int *arr,int *temp,int start,int end){ if(start >= end) return -1; int k = start,len; int start1,end1,start2,end2; int mid = start + (end-start)/2; sort(arr,temp,start,mid); sort(arr,temp,mid+1,end); start1 = start; end1 = mid; start2 = mid +1; end2 = end; int flag = 0; while(start1 <= end1 || start2 <= end2) { if(start2>end2) { inverNumCount += (end-mid); flag = 1; temp[k++] = arr[start1++]; continue; } if(start1 > end1) { temp[k++] = arr[start2++]; continue; } if(arr[start1] <= arr[start2]) { temp[k++] = arr[start1++]; } else { temp[k++] = arr[start2++]; inverNumCount++; } } for(int i = start; i <= end; ++i) arr[i] = temp[i]; if(flag ==1) inverNumCount -= (end-mid);}int mergeSort(int *arr,int arr_size){ int temp[arr_size]; sort(arr,temp,0,arr_size - 1); std::cout<<inverNumCount<<std::endl; return 0;}int main(){ int arr[] = {1,3,5,2,2}; mergeSort(arr,sizeof(arr)/sizeof(arr[0])); return 0;}运行结果：