归并排序(Merge sort)

实现原理

将两个未排序的“小”数组的所有元素有序的填充到一个新数组中，在排序同时完成“合并”。

先将两个数组中的第一个元素进行对比，将较小数字填充到新数组中（升序）

将取走了数据的数组的下一个元素与未取走数据的之前那一位进行对比，再将较小数字填充到新数组中

3

5

重复相同操作，直到最后一个放进去

3

5

6

7

分治策略（分而治之）

实际数组会反复拆分，得到小数组（长度为1），然后进行排序合并操作

分治

将问题分成一些小问题，然后递归求解，然后再将分的阶段得到的问题合并在一起

递归

表现在方法的内部，调用当前方法自身

例如在a()方法的内部调用a()方法

仅当内部调用a()方法的内部调用a()方法，才会继续运行外部a()方法剩余的代码

不熟练的情况下，慎用递归，否则会形成“死循环”效果

实现思想

将数组一分为二

中间点：上级数组第一个下标+（上级数组最大下标-上级数组第一个下标）/2

左侧：上级数组第一个下标-中间点

右侧：中间点+1-上级数组最大下标

 

实现代码

import java.util.Arrays;
import java.util.Random;

public class MergeSort {
    /**
     *
     * @param array 原始数组
     * @param left  左位置
     * @param right 右位置
     * @return  排列后的新数组
     */
    public static int[] mergeSort(int[] array ,int left ,int right){
        //起始下标和结束下标一致则表示当前数组只有一个元素，不能再分
        if (left == right){
            return new int[]{array[left]};//返回此数组
        }
        //确定中间位置
        int middle = left + (right - left)/2;
        //左数组取值范围 上一级数组的左位置到中间点
        int[] leftArray = mergeSort(array ,left ,middle);
        //右数组取值范围 上一级数组中间点向右一位到右位置
        int[] rightArray = mergeSort(array ,middle + 1 ,right);
        //重新排序的数组长度为两个数组相加的长度
        int[] newArray = new int[leftArray.length + rightArray.length];
        //左数组起始下标
        int l = 0;
        //右数组起始下标
        int r = 0;
        //新数组起始下标
        int m = 0;
        //左数组循环完毕或右数组遍历完则结束循环
        while (leftArray.length > l && rightArray.length > r){
            //两数组比较大小并将较小元素放入新数组中，结束操作后，进行了数据移动的数组与新数组的下标+1
            newArray[m++] = leftArray[l] > rightArray[r]?rightArray[r++]:leftArray[l++];
        }
        //循环结束后将还有剩余的数组其中元素全部放入新数组
        while (l < leftArray.length){
            newArray[m++] = leftArray[l++];
        }
        while (r < rightArray.length){
            newArray[m++] = rightArray[r++];
        }
        return newArray;
    }
    public static void main(String[] args) {
        Random rd = new Random();
        //生成数组
        int[] arr = new int[rd.nextInt(100)];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = rd.nextInt(500);
        }
        System.out.println(Arrays.toString(arr));
        //调用方法
        int[] brr = mergeSort(arr ,0 ,arr.length-1);
        System.out.println(Arrays.toString(brr));
    }
}