归并排序

百度：

    归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。

我的理解：

    首先将一组无序的数组按照长度进行等分拆分，直到分成只有一个数字，然后再进行相邻之间的比较，从而再合并起来。是一种先分后和的做法，高逼格说法为分治法（分治法通常要运用递归方法）。

脑补例子：

    原数组     [5,1,6,7,1,6,8,2,10]

    使用递归进行拆分后结果    5 1 6 7 1 6 8 2 10    

    第一次归并后    {1,5}（+1）{6,7} {1,6}（+1）{2,8}（+1）{10}    共比较3次

    第二次归并后    {1,5,6,7} (+2) {1,2,6,8} (+3)  {10}    共比较5次

    第三次归并    {1,1,2,5,6,6,7,8} (+6)    {10}    共比较6次

    第四次归并     {1,1,2,5,6,6,7,8,10}  {+8}     共比较8次    

    自己写的数组，死都要排完......

实现代码（java）：

package com.company;

import java.util.Arrays;public class Main {

    public static void main(String[] args) {

        int[] arr = new int[]{1, 4, 6, 83, 5, 7, 2, 10};

//      Main.merge(arr,0,(arr.length-1)/2,arr.length-1);

        Main.mergeSort(arr, 0, arr.length - 1);        

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

}    

//归并排序    

private static void mergeSort(int[] arr, int low, int hight) {

        int middle = (hight + low) / 2;

        //结束条件

        if (low < hight) {

            //处理左边

            mergeSort(arr, low, middle);

            //处理右边 

           mergeSort(arr, middle + 1, hight);

            //归并

            merge(arr, low, middle, hight);

        }

    }

    public static void merge(int[] arr, int low, int midden, int hight) {

        //用来存储归并后的临时数组

        int[] temp = new int[hight - low + 1];

        //记录第一个数组中需要遍历的下标

        int i = low;

        //记录第二个数组中需要遍历的下标

        int j = midden + 1; 

       //用于记录临时数组中存放的下标

        int index = 0;

        //遍历两组数组取出最小数字，放入临时数组

        while (i <= midden && j <= hight) {

            //第一组数组的数字比第二组数组小

            if (arr[i] <= arr[j]) {

                temp[index] = arr[i];

                i++;

            }

            //反之

            else {

                temp[index] = arr[j];

                j++; 

           }

            index++;

        }

        //当第一组数组有剩下数时，再把剩下的全部添加进临时数组

        while (i <= midden) {

            temp[index] = arr[i];

            i++;

            index++;

        }

        //当第二组数组有剩下数时，再把剩下的全部添加进临时数组

        while (j <= hight) { 

           temp[index] = arr[j];

            j++;

            index++;

        }

        //把临时数组重新放到原数组中

        for (int k = 0; k < temp.length; k++) {

            arr[k + low] = temp[k];

        }

    }

}