每日算法之数组中的逆序对（数组逆序数）

　　本篇文章为你整理了每日算法之数组中的逆序对（数组逆序数）的详细内容，包含有逆序对的概念:数组s 数组逆序数数组逆序是什么意思数组逆排序每日算法之数组中的逆序对，希望能帮助你了解每日算法之数组中的逆序对。

　　在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。即输出P mod 1000000007

　　方法1：暴力

　　算法实现

　　两个for循环，如果前面的数大于后面的计数加1即可

　　问题

　　当输入数过大时，需要的时间会很长，所以此方法不行

package mid.JZ51数组中的逆序对;

　　import java.util.ArrayList;

　　public class Solution {

　　 public int InversePairs1(int[] array) {

　　 int k = 1000000007;

　　 if (array.length = 1) return 0;

　　 int res = 0;

　　 for (int i = 1; i array.length; i++) {

　　 for (int j = i - 1; j j--) {

　　 if (array[i] array[j])

　　 res++;

　　 return res % k;

　　方法2 归并排序思想

　　先分：分呢，就是将数组分为两个子数组，两个子数组分为四个子数组，依次向下分，直到数组不能再分为止！

　　后并：并呢，就是从最小的数组按照顺序合并，从小到大或从大到小，依次向上合并，最后得到合并完的顺序数组！

　　归并统计法，关键点在于合并环节，在合并数组的时候，当发现右边的小于左边的时候，此时可以直接求出当前产生的逆序对的个数。

package mid.JZ51数组中的逆序对;

　　import java.util.Arrays;

　　public class Solution {

　　 * 分治

　　 * @param array

　　 * @return

　　 public int count = 0;

　　 public int InversePairs(int[] array) {

　　 divMerge(array, 0, array.length-1);

　　 return count;

　　 public void divMerge(int[] array, int left, int right) {

　　 if (left = right) return;

　　 int mid = left + (right - left) / 2;

　　 //分左边

　　 divMerge(array, left, mid);

　　 //分右边

　　 divMerge(array, mid + 1, right);

　　 //合并

　　 int i = left;

　　 int j = mid + 1;

　　 //临时数组

　　 int[] tmp = new int[right - left + 1];

　　 int k = 0;

　　 while (i = mid j = right) {

　　 if (array[i] array[j]) {

　　 tmp[k++] = array[j++];

　　 count += mid - i + 1;

　　 count %= 1000000007;

　　 } else {

　　 tmp[k++] = array[i++];

　　 while (i = mid) {

　　 // 如果右边的走完了就把左边的放到tmp后面

　　 tmp[k++] = array[i++];

　　 while (j = right) {

　　 // 如果左边的走完了就把右边的放到tmp后面

　　 tmp[k++] = array[j++];

　　 // 把排好序的tmp 移到 array中

　　 for(int l=0; l l++) {

　　 array[left++] = tmp[l];

　　 public static void main(String[] args) {

　　 System.out.println(new Solution().InversePairs(new int[]{1, 2, 3, 4, 5, 6, 7, 0}));

　　 * 暴力