算法入门3-归并排序

2021-07-12 07:53:24

  归并排序是常见的排序方法，下面介绍归并排序的定义、实现步骤、时间复杂度分析，以及扩展的小和问题、逆序对问题。由归并改造的题目，是面试工作中常考题型，需要重点掌握。

一、定义

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

二、实现步骤

  1、将这一组数对半分成两区间；

  2、左区间对半分，右区间对半分。左子区间和右子区间继续对半分，依此类推，直到最小区间是只有一个数；

  3、从最小区间开始，左右区间开始有序合并。

  4、合并的结果层层上提，最终合并成有序数组。

  图示：

算法入门3-归并排序

  java代码实现：

// 归并排序
public class MergeSort {

    public static void main(String[] args) {
        Integer[] arr = DataStore.getData();
        String source = "";
        for(int i = 0; i < arr.length; i++) {
            source += arr[i] + " ";
        }
        System.out.println("原数组：" + source);
        MergeSort.sort(arr, 0, arr.length - 1);
        String res = "";
        for(int i = 0; i < arr.length; i++) {
            res += arr[i] + " ";
        }
        System.out.println("排序后：" + res);
    }

    // 归并排序
    public static void sort(Integer[] arr, int L, int R) {
        MergeSort.sort(arr, L, R);
    }
    
    // 二分后合并
    public static void process(Integer[] arr, int L, int R) {
        if(L == R) {
            return;
        }
        // 等价于L +（R - L）/ 2
        int mid = L + ((R - L) >> 1);
        process(arr, L, mid);
        process(arr, mid + 1, R);
        merge(arr, L, mid, R);
    }

    // 合并
    public static void merge(Integer[] arr, int L, int M, int R) {
        // 辅助数组，用于存放R - L区间排序后的值
        Integer[] help = new Integer[R - L + 1];
        // 辅助数组当前位置
        int i = 0;
        // 左区间当前位置
        int p1 = L;
        // 右区间当前位置
        int p2 = M+1;
        // arr[p1]和arr[p2]对比大小，小值放入辅助数组，并自身索引加1
        while(p1 <= M && p2 <= R) {
            help[i++] = arr[p1] <= arr[p2] ? arr[p1++] : arr[p2++];
        }
        // 补充，考虑p2已放完，p1未放完的情况
        while(p1 <= M) {
            help[i++] = arr[p1++];
        }
        // 补充，考虑p1已放完，p2未放完的情况
        while(p2 <= R) {
            help[i++] = arr[p2++];
        }
        for(i = 0; i < help.length; i++) {
            arr[L + i] = help[i];
        }
    }
}

  DataStore工具类

public class DataStore {

    // 随机获取10个整数
    public static Integer[] getData() {
        List<Integer> list = new ArrayList<Integer>();
        for(int i = 0; i < 10; i++) {
            double d = Math.random();
            list.add((int)(d*10));
        }
        Integer[] arrays = new Integer[list.size()];
        list.toArray(arrays);
        return arrays;
    }

    // 数组中两数交换
    public static void swap(Integer[] array, int i, int j) {
        if(array != null && i < array.length && j< array.length) {
            int temp = array[i];
            array[i] = array[j];
            array[j] = temp;
        }
    }
}

输出：

原数组：7 3 7 0 2 3 4 8 8 1
排序后：0 1 2 3 3 4 7 7 8 8

三、时间复杂度分析

​  归并排序是一个不断二分的过程，从上图容易看到，二分的层数是logN，如数组是8个数，一共分3层进行二分，全部的二分次数是N，所以，归并排序复杂度为O(N*logN)。

​  归并排序将排序复杂度O(N2) 降为O(NlogN)的本质原因，是因为不浪费每一次的比较结果。实现方式是对半分数据，左排序，右排序，再归并成一条，这一过程不断从小到大递归，最终得到结果。

四、扩展

1、小和问题

  在一个数组中，每一个数左边比当前数小的数累加起来，叫做这个数组的小和。求一个数组的小和。

  例子：[1, 3, 4, 2, 5]

  1左边比1小的数，没有；

  3左边比3小的数，1；

  4左边比4小的数，1、3；

  2左边比2小的数，1；

  5左边比5小的数，1、3、4、2；

  所以小和为1+1+3+1+1+3+4+2=16。

  分析：这个题目当然可以用暴力解法，直接遍历每一个数，但时间复杂度是O(N ^ 2)。其实可以用归并法解决，时间复杂度降为O(N*logN)。

  先来看，**小和问题可以等价于，把数组中每一个数自身累加，累加的次数为右边比它大的数的个数。**比如题目中的1，右边比它大的数是3、4、2、5，所以1要累加的次数是4。

  在经典归并排序实现的基础上，解答小和问题，实现步骤：

  1）merge方法内，当arr[p1] == arr[p2]时，先拷贝arr[p2]进辅助数组，因为这样才能保证arr[p1]比arr[p2]小时，（R-p2+1）一定是右区间的数比arr[p1]大的个数；

  2）merge方法内，当arr[p1] < arr[p2]时，累加(R - p2 + 1) * arr[p1]结果，这里的意思是把一个数自身累加，累加的次数为右边比它大的数的个数；

  3）将累加结果不断递归返回。

  java实现代码：

// 归并法求小和
public class MergeSortSmallSum {

    public static void main(String[] args) {
        // 小和值：2 + 1 + 2 + 1 = 6
        Integer[] arr = {2,1,4,3};
        String source = "";
        for(int i = 0; i < arr.length; i++) {
            source += arr[i] + " ";
        }
        System.out.println("原数组：" + source);
        Integer smallSum = MergeSortSmallSum.process(arr, 0, arr.length - 1);
        String res = "";
        for(int i = 0; i < arr.length; i++) {
            res += arr[i] + " ";
        }
        System.out.println("排序后：" + res);
        System.out.println("小和：" + smallSum);
    }

    // 二分后归并
    public static Integer process(Integer[] arr, int L, int R) {
        if(L == R) {
            return 0;
        }
        // 等价于L +（R - L）/ 2
        int mid = L + ((R - L) >> 1);
        return process(arr, L, mid)
                + process(arr, mid + 1, R)
                + merge(arr, L, mid, R);
    }

    // 归并，并计算小和
    public static Integer merge(Integer[] arr, int L, int M, int R) {
        // 辅助数组，用于存放R - L区间排序后的值
        Integer[] help = new Integer[R - L + 1];
        // 辅助数组当前位置
        int i = 0;
        // 左区间当前位置
        int p1 = L;
        // 右区间当前位置
        int p2 = M+1;
        int res = 0;
        while(p1 <= M && p2 <= R) {
            // 求小和等效于，把数组中每一个数自身累加，累加的次数为右边比它大的数的个数
            // 右区间已排好序，所以当arr[p1]比arr[p2]小时，右区间的数比arr[p1]大的个数是（R-p2+1）
            res += arr[p1] < arr[p2] ? (R - p2 + 1) * arr[p1] : 0;
            // arr[p1]和arr[p2]对比大小，小值放入辅助数组，并自身索引加1
            // 与经典merge过程不一样的地方，这里arr[p1] == arr[p2]时，先拷贝arr[p2]进辅助数组，
            // 因为这样才能保证arr[p1]比arr[p2]小时，（R-p2+1）一定是右区间的数比arr[p1]大的个数
            help[i++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++];
        }
        // 补充，考虑p2已放完，p1未放完的情况
        while(p1 <= M) {
            help[i++] = arr[p1++];
        }
        // 补充，考虑p1已放完，p2未放完的情况
        while(p2 <= R) {
            help[i++] = arr[p2++];
        }
        for(i = 0; i < help.length; i++) {
            arr[L + i] = help[i];
        }
        return res;
    }
}

输出：

原数组：2 1 4 3
排序后：1 2 3 4
小和：6

2、逆序对问题

  在一个数组中，左边的数如果比右边的数大，则这两个数构成一个逆序对，请打印所有逆序对。

  分析：同样的，这个题目可以用暴力解法，直接遍历每一个数，但时间复杂度仍然是O(N ^ 2)。同样，我们用归并法解决，时间复杂度降为O(N*logN)。

  在经典归并排序实现的基础上，解答逆序对问题，实现步骤：

  1）merge方法内，当arr[p1] == arr[p2]时，先拷贝arr[p2]进辅助数组，因为这样才能保证arr[p1]比arr[p2]大时，（R-p2+1）一定是右区间的数比arr[p1]小的个数；

  2）merge方法内，当arr[p1] > arr[p2]时，累加(R - p2 + 1)的结果，即逆序对的个数，并遍历arr[p2]到arr[R]的数，打印逆序对；

  3）将累加结果不断递归返回。

  java实现代码：

// 归并法求逆序对
public class MergeSortReverse {

    public static void main(String[] args) {
        // 逆序对：{2,1} {4,3}
        Integer[] arr = {2,1,4,3};
        String source = "";
        for(int i = 0; i < arr.length; i++) {
            source += arr[i] + " ";
        }
        System.out.println("原数组：" + source);
        Integer count = MergeSortReverse.process(arr, 0, arr.length - 1);
        String res = "";
        for(int i = 0; i < arr.length; i++) {
            res += arr[i] + " ";
        }
        System.out.println("排序后：" + res);
        System.out.println("逆序对数：" + count);
    }

    // 二分后合并
    public static Integer process(Integer[] arr, int L, int R) {
        if(L == R) {
            return 0;
        }
        // 等价于L +（R - L）/ 2
        int mid = L + ((R - L) >> 1);
        return process(arr, L, mid) +
                process(arr, mid + 1, R) +
                merge(arr, L, mid, R);
    }

    // 合并
    public static Integer merge(Integer[] arr, int L, int M, int R) {
        // 辅助数组，用于存放R - L区间排序后的值
        Integer[] help = new Integer[R - L + 1];
        // 辅助数组当前位置
        int i = 0;
        // 左区间当前位置
        int p1 = L;
        // 右区间当前位置
        int p2 = M+1;
        // 逆序对数
        int count = 0;
        // arr[p1]和arr[p2]对比大小，大值放入辅助数组，并自身索引加1
        while(p1 <= M && p2 <= R) {
            // 右区间已排好序，所以当arr[p1]比arr[p2]大时，右区间的数比arr[p1]小的个数是（R-p2+1）
            if(arr[p1] > arr[p2]) {
                count += (R - p2 + 1);
                for(int k = p2; k <= R; k++) {
                    System.out.println("逆序对：{" + arr[p1] + "," + arr[k] + "}");
                }
            }
            // arr[p1]和arr[p2]对比大小，大值放入辅助数组，并自身索引加1
            help[i++] = arr[p1] > arr[p2] ? arr[p1++] : arr[p2++];
        }
        // 补充，考虑p2已放完，p1未放完的情况
        while(p1 <= M) {
            help[i++] = arr[p1++];
        }
        // 补充，考虑p1已放完，p2未放完的情况
        while(p2 <= R) {
            help[i++] = arr[p2++];
        }
        for(i = 0; i < help.length; i++) {
            arr[L + i] = help[i];
        }
        return count;
    }
}

输出：

原数组：2 1 4 3
逆序对：{2,1}
逆序对：{4,3}
排序后：4 3 2 1
逆序对数：2

上一篇：编写C语言代码，实现以下功能：输入平面上两个点P1(x1,y1)和P2(x2,y2)的坐标，以这两个点为左上角和右下角可以确定一个矩形，输出这个矩形的周长。要求平面上点的坐标和矩形都用结构体来表示。


下一篇：《C语言深度剖析》第三章 预处理详解 p2（完结） C语言从入门到入土（进阶篇）