归并排序算法

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

分：使用递归将数组不断拆分两个长度相同的子数组，直到子数组中只有一个数字

治：按递归顺序对子数组排序，最后整个数组排序完成

public class MergeSort {
    public static void main(String []args){
        int []arr = {6,3,8,5,4,1,2,7};
        test(arr);
        System.out.println(Arrays.toString(arr));
    }
 
    public static void test(int []arr){
        // 在排序前，先建好一个长度等于原数组长度的临时数组，避免递归中频繁开辟空间
        int []temp = new int[arr.length];
        sort(arr,0,arr.length-1,temp);
    }
    // 递归方法 
    private static void sort(int[] arr,int left,int right,int []temp){
        if(left 
六、奇数的归并排序 
1、先把{6,3,5,4,1,2,7}当作数组 {6,3,5,4,1,2}和{7}
 
2、然后对{6,3,5,4,1,2}归并排序 
 
3、再对{1,2,3,4,5,6}和{7}排序
 
七、归并排序的时间复杂度和稳定性 
归并排序时间复杂度
 归并排序的时间复杂度是O(N*lgN)。
 假设被排序的数列中有N个数。遍历一趟的时间复杂度是O(N)，需要遍历多少次呢？
 归并排序的形式就是一棵二叉树，它需要遍历的次数就是二叉树的深度，而根据完全二叉树的可以得出它的时间复杂度是O(N*lgN)。
 
归并排序稳定性
 归并排序是稳定的算法，它满足稳定算法的定义。
算法稳定性 -- 假设在数列中存在a[i]=a[j]，若在排序之前，a[i]在a[j]前面；并且排序之后，a[i]仍然在a[j]前面。则这个排序算法是稳定的！