归并排序和快速排序的衍生问题
前面两篇总结了常见的几种排序算法的主要思想以及C++与python两种方式的实现过程， 几种排序算法中比较重要的就是归并排序和快速排序，这两种方法的相同点就是都使用了分治的思想，现在用来解决两个具体问题。
1.分治法
分治法就是将原问题分割成同等结构的子问题，之后将子问题逐一解决后，原问题也就得到了解决。 需要注意的是归并排序和快速排序虽然都使用了分治的思想，但它们分别代表了分治算法的两类基本思想。对于归并排序而言，它对“分”这个过程没有做太多操作，只是简单的将数组分为两部分然后递归的进行归并排序，而归并排序的关键是这样分完之后如何将它们归并起来，即merge()操作。
而对于快速排序来说，则是废了很大功夫放在了如何“分”这个问题上，我们是选取了一个标定点，然后使用partition()这个子过程将这个标定点移到了合适的位置，当它移到了合适的位置之后才将整个数组分成了两部分，而这样分完之后，在“合”的时候就不用做过多的考虑了，只需要一步一步递归下去就好了。
下面解决两个直接从归并排序和快速排序中衍生出来的具体问题的。
2.求逆序对数量
- 问题描述：在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。给定一个数组，求出这个数组中的逆序对的总数。
- 这个问题直接的做法是逐个统计，复杂度是O(n^2)，但显然是很愚蠢的方法，这里可以利用归并排序的思想，在归并排序过程中统计逆序对的个数。
- 实现思想：
归并排序是将数列a[l,r]分成两部分，a[l,mid]和a[mid+1,r]分别进行归并排序，然后再将这两半合并起来。在合并的过程中（设l<=i<=mid，mid+1<=j<=r），当a[i]<=a[j]时，并不产生逆序数；当a[i]>a[j]时，在前半部分中比a[i]大的数都比a[j]大，将a[j]放在a[i]前面的话，逆序数要加上mid+1-i。因此，可以在归并排序中的合并过程中计算逆序数。 - C++实现：
#include <iostream>using namespace std; // 计算逆序数对的结果以long long返回 // 因为对于一个大小为n的数组, 其最大的逆序数对个数为 n*(n-1)/2, 非常容易产生整型溢出 // __merge函数求出在arr[l,mid]和arr[mid+1,r]有序的基础上, arr[l,r]的逆序数对个数long long __merge(int arr[],int l,int mid,int r){ long long res = 0;// 初始化逆序数对个数 res = 0int aux[r - l + 1]; for(int i = l;i <= r;i++) aux[i - l] = arr[i]; int i = l; int j = mid + 1; for(int k = l;k <= r;k++){ if(i > mid){ arr[k] = aux[j - l]; j ++; } else if(j > r){ arr[k] = aux[i - l]; i ++; } else if(aux[i - l] < aux[j - l]){ arr[k] = aux[i - l]; i ++; } else{// 左半部分所指元素 > 右半部分所指元素arr[k] = aux[j - l]; j ++; res += (long long) (mid - i + 1); // 此时, 因为右半部分所指的元素小 // 这个元素和左半部分的所有未处理的元素都构成了逆序数对 // 左半部分此时未处理的元素个数为 mid - j + 1} } return res; } // 求arr[l,r]范围的逆序数对个数long long __inversionCount(int arr[],int l,int r){ if(l >= r) return 0; int mid = l + (r - l) / 2; long long res1 = __inversionCount(arr,l,mid);// 求出 arr[l,mid] 范围的逆序数long long res2 = __inversionCount(arr,mid + 1,r);// 求出 arr[mid+1,r] 范围的逆序数return res1 + res2 + __merge(arr,l,mid,r); } long long inversionCount(int arr[],int n){ return __inversionC