【编程笔记】利用归并排序求逆序对

逆序对的定义

对于数列的第 i 个和第 j 个元素，如果满足 i<j且 a[i]>a[j]，则其为一个逆序对；否则不是。

归并排序求逆序对的思路

一个区间的逆序对数=左边逆序对的数+右边逆序对的数+跨边界的逆序对数。

其实就是在归并过程中，如果有的某一个数大于左边的一个数，就把左边遍历到的数字数量加上。因为左边是有序的，只要右边的数大于左边的一个数，就会大于左边那个数前面所有的数

平均时间复杂度为O(nlogn)。

归并排序求逆序对的过程

1. 递归左区间，计算左边逆序对的数

2. 递归右区间，计算右边逆序对的数

3. 循环比较左右区间，计算跨边界的逆序对数

4. 归并

而对于跨边界的逆序对数量，由归并排序的特点可知第三种情况的个数为当数组[i] > 数组[j] 时，i后面的所有数都大于数组[j]即个数为mid - i + 1。

感叹，归并真的神奇。

夕弦的图片由NovelAI生成， 练了个新模型，但似乎效果和up红心咖啡_Official的差不多