归并排序

思想：

　　先拆分，再合并

　　

 　  核心：归并

　　

　　  时间复杂度： 始终都是 O(nlogn) 。代价是需要额外的内存空间

 

---

 （一） 代码　  

public class MergeSort {

    public static void main(String[] args) {
        int []arr = {9,8,7,6,5,4,3,2,1};
        sort(arr);
        System.out.println(Arrays.toString(arr));
    }

    private static void sort(int[] arr) {
        //新建数组,存放归并数据
        int[] temp = new int[arr.length];
        sortarr(arr,0,arr.length - 1 ,temp);
    }

    //递归方法
    private static void sortarr(int[] arr, int start, int end, int[] temp) {
        if(start < end){
            int mid = (start + end) / 2;
            //左递归
            sortarr(arr,start,mid,temp);
            //右递归
            sortarr(arr,mid+1,end,temp);
            //合并
            merge(arr,start,mid,end,temp);
        }
    }

    //归并方法
    private static void merge(int[] arr, int start, int mid, int end, int[] temp) {
        int i = start; //左指针
        int j = mid+1; //右指针
        int t = 0;     //temp指针
        while(i <= mid && j <= end){
            if(arr[i] <= arr[j]){
                temp[t++] = arr[i++];
            }else{
                temp[t++] = arr[j++];
            }
        }
        //将左序列剩余元素填充进temp中
        while(i <= mid){
            temp[t++] = arr[i++];
        }
        //将右序列剩余元素填充进temp中
        while(j <= end){
            temp[t++] = arr[j++];
        }
        //注意此处 将temp中的元素全部拷贝到原数组中
        t = 0;
        while(start <= end){
            arr[start++] = temp[t++];
        }
    }
}

---

　　　　　　　　晕晕乎乎