算法篇二(分治思想下的归并排序)

分治思想下的归并排序

归并排序

 1.归并思想：首先把一个数组中的元素，按照某一方法，先拆分了之后，按照一定的顺序各自排列，然后再归并到一起，使得归并后依然是有一定顺序的 。
 2.归并排序算法可以利用递归的思想或者迭代的思想去实现。首先我们先把一个无序的数组去拆分，然后利用一定的规则，去合并。类似于二叉树的结构。其总的时间复杂度为O( n log n)。空间复杂度为 S（nlogn）

题目(Leetcode-面试51)

 题目：在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。
  例子：输入[7,5,6,4] 输出 5

解题

1.暴力求解法：一开始我使用的是暴力法，就是直接遍历，用前值去比较后值，如果前值大就加1 ，这样，这个程序的时间复杂度为o(n的平方)，短的数组可能并不会有什么大的问题，但是数组长度太长的话，他的效率会非常的低。、
 代码如下：

    class Solution {
        public int reversePairs(int[] nums) {
            int count = 0;
            for(int i=0;i<nums.length-1;i++){
                for(int j=i+1;j<nums.length;j++){
                    if(nums[i]>nums[j]){
                        count++;
                    }
                }
            }
            return count;
        }
    }

2.归并排序：
 所有的逆序对来自于3个地方
  1.左边区间的逆序对，
  2.右边区间的逆序对，
  3.横跨两个区间的逆序对
 所以我们选择在第二个子区间归并回去的时候，计算逆序对的个数：
  代码如下：

class Solution {
    public int reversePairs(int[] nums) {
        int len = nums.length;
        int[] copy new int[len];

        if(len <2){
            return 0;
        }

        for(int i=0;i<len;i++){
            copy[i] = nums[i];
        }
        int[] temp = new int[len];

        return reversePairs(copy,0,len-1,temp)；

    }


    private int reversePairs(int[] copy,int start,int end,int[] temp){
        if(start == end){
            return 0;
        }
        int mid = start + (end-start)/2;
        int leftPairs = reversePairs(copy,start,mid,temp);
        int rightPairs = reversePairs(copy,mid+1,end,temp);
        if(copy[mid]<copy[mid+1]){
            return leftPairs+rightPairs;
        }

        int crossPairs = mergeAndCount(nums, start, mid, end, temp);
        return leftPairs + rightPairs + crossPairs;
    }

    private int mergeAndCount(int[] copy,int start,int mid,int end,int[] temp){
        for(int i=start;i<end+1;i++){
            temp[i] = copy[i];
        }
        int i = start;
        int j = mid+1;
        for(int k=start;k<end+1;k++){

            // 有下标访问，得先判断是否越界
            if (i == mid + 1) {
                copy[k] = temp[j];
                j++;
            } else if (j == right + 1) {
                copy[k] = temp[i];
                i++;
            } else if (temp[i] <= temp[j]) {
                // 注意：这里是 <= ，写成 < 就不对，因为只有>时才是逆序对
                copy[k] = temp[i];
                i++;
            } else {
                copy[k] = temp[j];
                j++;

                // 在 j 指向的元素归并回去的时候，计算逆序对的个数，只多了这一行代码
                count += (mid - i + 1);
            }
        }
        return count;
        }
    }
}