归并排序---java实现

1. 核心是分治算法。
2. 先将数组分开，分为一个元素一个数组。
3. 最后将数组合并为一个数组。
4. 将每个数组中较小的放到临时数组中，如果一个数组全部放入临时数组后，就将后面的一个数组全部放入临时数组；最后将临时数组放进到原始数组中。

归并排序https://gitee.com/ALi_L/javaDataStructurs.git

package DataStructures.sort;

import java.util.Arrays;


public class MergeSort {
    public static void main(String[] args) {

        int[] array = {-9, 78, 0, 23, -567, 70};
        int[] temp = new int[array.length];
        splitAndmerge(array, 0, array.length - 1, temp);

        System.out.println(Arrays.toString(array));

    }

    public static void splitAndmerge(int[] array, int left, int right, int[] temp) {
        if (left < right) {

            int mid = (left + right) / 2;
            //左边划分为一个元素的数组
            splitAndmerge(array, left, mid, temp);
            //右边划分为一个元素的数组
            splitAndmerge(array, mid + 1, right, temp);
            //合并数组
            merge(array, left, mid, right, temp);
        }
    }

    //合并
    public static void merge(int[] array, int left, int mid, int right, int[] temp) {
        int lefti = left;
        int rightj = mid + 1;
        //temp的下标
        int t = 0;

        while (lefti <= mid && rightj <= right) {
            if (array[lefti] <= array[rightj]) {
                temp[t] = array[lefti];
                lefti++;
                t++;
            } else {
                temp[t] = array[rightj];
                rightj++;
                t++;
            }
        }
        //将左或右剩余的数字插入到array中
        while (lefti != mid) {
            temp[t] = array[lefti];
            t++;
            lefti++;
        }
        while (rightj != right) {
            temp[t] = array[rightj];
            t++;
            rightj++;
        }

        //将temp数组合并到array
        for (int i = 0; i < temp.length; i++) {
            array[i] = temp[i];
        }
    }


}