归并排序(java)

基本思想:

分解: 将n个待排序的元素分成 n/2个元素的子序列

排序:  递归对每个子序列进行合并,并且两两合并排序

合并: 合并最后已排序的子序列得到排序结果

递归法: 

将待排序序列从中间分割成2部分,再把2部分分割成4部分, 依次分割下去, 直至分割成一个一个的元素, 在把这些元素两两归并在一起,使之有序, 最后递归成一个已排好序的序列

待排序序列     4 2 5 3 1 6 9 7 

分割     [4,2,5,3]                                 [1,6,9,7]

分割        [4,2] [5,3]                         [1,6], [9,7]

分割         [4], [2], [5], [3]                [1], [6], [9], [7]

归并         [2,4]    [3,5]                   [1,6],   [7,9]

归并          [2,3,4,5]                [1,6,7,9]

归并        1 2 3 4 5 6 7 9 

归并排序完成 

伪代码:只需记住核心代码即可, 不增加没必要的记忆负担

public int[] sort(int[] sourceArray){
    //copyOf用法: 第一个参数为要拷贝的数组对象 第二参数为拷贝的新数组长度
    //copyOfRange(data,0,16)用法: 表示复制data数组中第0个到第16个元素到新数组中 
    int[] arr=Arrays.copyOf(sourceArray, sourceArray.length);
    
    int middle = arr.length/2;
    int[] left = Arrays.copyOfRange(arr,0,middle);
    int[] right = Arrays.copyOfRange(arr,middle,arr.length);
    return merge(sort(left),sort(right));
    
}
 
//归并函数
protected int[] merge(int[] left, int[] right){
    int[] result = new int[left.length + right.length];
    int i =0;
    while(left.length>0 && right.length>0){
        //两个数组中取出较小的放入数组
        if(left[0] <= right[0]){
            result[i++]=left[0];
            left=Arrays.copyOfRange(left,1,left.length);
        }else{
            result[i++]=right[0];
            right = Arrays.copyOfRange(right, 1, right.length);
        }
    }
    //如果分割出来的数组不是相等,依次递归左边 子序列 和右边子序列
    while(left.length > 0){
        result[i++]=left[0];
        left = Arrays.copyOfRange()
    }
    // 右边子序列递归
    while(right.length > 0){
        result[i++]=right[0];
        right = Arrays.copyOfRange(right,1, right.length);
    }
    return result
}