归并排序-最小和-逆序对

归并排序

归并排序(MERGE-SORT)是利用归并的思想实现的排序方法,该算法采用经典的分治(divide-and-conquer)策略(分治法将问题(divide)成一些小的问题然后递归求解,而治(conquer)的阶段则将分的阶段得到的各答案”修补”在一起,即分而治之)。

大概过程如下:

代码实现

   public static void  megerSort(int[] nums ){
        if (nums == null || nums.length < 2) return;
        process(nums,0,nums.length - 1);
    }

    public static void process(int[] array , int L , int R){
        //只有一个数
        if (L == R)
            return;

        int mid = L + ((R - L) >> 2);

        process(array, L , mid);
        process(array, mid + 1 , R);
        meger(array , L , mid ,R);
    }

    public static void meger(int[] array, int l, int mid, int r){
        int[] help = new int[r - l + 1];
        int helpIndex  = 0;
        int pLeft = l;
        int pRight = mid + 1;

        while (pLeft <= mid && pRight <= r){
            help[helpIndex++] = array[pLeft] <= array[pRight] ? array[pLeft++] : array[pRight++];
        }
        while (pLeft <= mid){
            help[helpIndex++] = array[pLeft++];
        }
        while (pRight <= r){
            help[helpIndex++] = array[pRight++];
        }
        for (int i = 0; i < help.length; i++) {
            array[l + i] = help[i];
        }
    }

例题

1. 小和问题

一个数列,其中一个数p,其左边所有比p小的数的和,是数p的小和。
求这个数列所有数的小和之和。

一般而言我们会直接想到暴力遍历,对第i位置的数,查找0~i里比i位置的数小的数并且相加。这样的时间复杂度为O(N*N)。

但换个思路,对i位置的数而言,我们只需要知道右边比array[i]大的数有几个(比如有n个),我们只想知道对左边而言,右边有多少个数大于左边,那么右边只作为比较使用而不产生小和。那么在最终的最小和里就会有n* array[i] , 只要找出所有符合条件的数字相加就能得出答案。

比如查找 7 2 3 6 8 3 4 9的最小和

初始划分:
7 2 3 6 | 8 3 4 9

    对左组
    7 2 | 3 6
                对左组
                7 | 2  
                ————合并 变成 2 7。对左组而言 7 > 2 大 ,由于我们找的是右边有没有比左边大的,所以只归并,不产生小和,或者说,产生了 0 个 7

                对右组
                3 | 6
                ————合并,变成 3 6.对左组而言 3 < 6 ,满足产生小和的条件。所以归并且产生了 1*3


    对左组
    2 7 | 3 6
    ————合并,对2 ,右组比2大的数有两个,此时产生2 * 2 ;对 7 ,右边组比7大的数字没有,不产生小和。此时合并为 2 3 6 7


    对右组
    8 3 | 4 9
                对左组
                8 | 3
                ————合并 变成 3 8 ,8 的右组不存在比8大的数,所以不产生小和

                对右组
                4 | 9
                ————合并 , 由于4所在的左组比右组小 , 所以产生了 1 * 4,合并结果为 4 9

    对右组
    3 8 | 4 9
    ————合并 , 对左组的3 , 在右组有4 和 9 比他大 , 就产生了 2 * 3 的小和 , 对 8 ,右组有9 比他大,产生了 1 * 8 的小和。合并结果为 3 4 8 9

合并最后一个分组
左组 | 右组
2 3 6 7 | 3 4 8 9
————合并过程:
    对2 , 在右组有4个比他大 ,产生 4 * 2;
    对3 , 右组有3个比他大 ,产生 3 * 3
    对6 , 右组有2个比他大,产生 2 * 6
    对7 , 右组有2个比他大,产生 2 * 7


最终的小和
smallSum = 1*3 + 2*2 + 1*4 + 2*3 + 1*8 + 4*2 + 3*3 + 2*6 + 2*7 = 68

代码实现

//小和问题
public class Code02_SmallSum {
    public static int smallSum(int[] array){
        if (array == null || array.length < 2) return 0;
        return process(array , 0 ,array.length - 1);
    }

    //array[L……R] ,既要排序,也要求小和
    public static int process(int[] array , int L , int R){
        if (L == R) return 0;
        int mid = L + ((R - L) >> 1);
        //左边小和 + 右边小和 + merge产生的小和
        return process(array , L , mid) + process(array , mid + 1 ,R) + merge(array, L , mid , R);
    }

    public static int merge(int[] array , int L , int mid ,int R){
        int[] helpArray = new int[R - L + 1];
        int pLeft = L;
        int pRight = mid + 1;
        int helpIndex = 0;

        int smallSum = 0;

        while (pLeft <= mid && pRight <= R){
        //有 r - pright + 1 个比他大
        //当前的左组 比 右组小吗?是 右边有序,则证明有 r - pright + 1个比当前左组的数大
            smallSum += array[pLeft] < array[pRight] ? ( R - pRight + 1) * array[pLeft] : 0;
            helpArray[helpIndex++] = array[pLeft] < array[pRight] ? array[pLeft++] : array[pRight++];
        }
        while (pLeft <= mid)
            helpArray[helpIndex++] = array[pLeft++];
        while (pRight <= R)
            helpArray[helpIndex++] = array[pRight++];

        //合并
        for (int i = 0; i < helpArray.length; i++) {
            array[L + i] = helpArray[i];
        }

        return smallSum;
    }

    public static void main(String[] args) {
       //7 2 3 6 8 3 4 9
        Scanner scanner = new Scanner(System.in);
        int i = scanner.nextInt();
        int[] array = new int[i];
        for (int j = 0; j < i; j++) {
            array[j] = scanner.nextInt();
        }
        System.out.println(smallSum(array));
        System.out.println(1*3 + 2*2 + 1*4 + 2*3 + 1*8 + 4*2 + 3*3 + 2*6 + 2*7);
    }
}

2. 逆序对个数/交换次数

在一个数组中,左边的数如果比右边的数大,则这两个数构成一个逆序对。

这个问题也适合使用归并排序的方法进行批量计算,例如

代码实现

public class Code03_MergeSortValerLina {

    public static int mergeSort(int[] array){
        if (array == null && array.length < 2) return 0;
        return process(array , 0 ,array.length - 1);
    }

    public static int process(int[] array, int L , int R){
        if (L == R) return 0;

        int mid = L + ((R - L) >> 1);

        return process(array, L, mid)  + process(array, mid + 1, R) + merge(array , L , mid , R);
    }

    public static int merge(int[] array , int L , int mid , int R){
        int[] helpArray = new int[R - L + 1];
        int helpIndex = 0;
        int pLeft = L;
        int pRight = mid + 1;
        int count = 0;

        while (pLeft <= mid && pRight <= R){
            if (array[pLeft] <= array[pRight])
                helpArray[helpIndex++] = array[pLeft++];
            else {
                helpArray[helpIndex++] = array[pRight++];
                //count %= 1000000007;
                count += (mid - pLeft + 1);
            }
        }

        while (pLeft <= mid)
            helpArray[helpIndex++] = array[pLeft++];
        while (pRight <= R)
            helpArray[helpIndex++] = array[pRight++];

        for (int i = 0; i < helpArray.length; i++) {
            array[L + i] = helpArray[i];
        }
        return count;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int i = scanner.nextInt();
        int[] array = new int[i];
        for (int j = 0; j < i; j++) {
            array[j] = scanner.nextInt();
        }

        System.out.println(mergeSort(array));
    }

}
  • 微信
  • 快加我微信吧~
  • QQ
  • 快加我QQ吧~
  • weinxin
Betterts

发表评论 取消回复