归并排序

代码走一走，代码999

package main.java.java数据结构与算法第一课;

import java.util.Arrays;

/**
 * 归并排序Demo,递归切分数组，同时对切分的数组排序，因为是递归操
 * 作，所以切分到最终的两两一组，在进行逐渐的合并。
 * 栈的模式操作，不了解的可以先了解下栈的特性
 */
public class MergeSort {
    public static void main(String[] args) {
        int arrs[]= {1,3,2,4,321,5,23,2};
        int[] ints = megerSort(arrs);
        int k = 0;
        System.out.println(Arrays.toString(ints));
    }

    /**
     * 归并排序函数
     * @param arrs
     * @return
     */
    public static int[] megerSort(int arrs[]) {
        //长度小于2没必要排序,直接返回
        if (arrs.length < 2 ) {
            return arrs;
        }
        //获取中间值，第一次取数组中间位置的数据索引值
        int mid = arrs.length/2;
        //通过系统函数copy左右两个函数：开辟空间
        int [] left = Arrays.copyOfRange(arrs,0,mid);
        int [] right = Arrays.copyOfRange(arrs,mid,arrs.length);
        //调用归并函数
        return merger(megerSort(left),megerSort(right));
    }
    
    /**
     * 归并函数
     * 将两个排序好的数组合并  例如   2 5    3 6   合并后    2 3 5 6
     * @return
     */
    public static int [] merger(int [] left , int [] right){
        System.out.println(Arrays.toString(left));
        System.out.println(Arrays.toString(right));
        //存放结果的新数组
        int result [] = new int [left.length+right.length];
        //循环遍历两个拍好序的数组，进行合并
        for (int index = 0 , i = 0 , j = 0 ; index < result.length ; index ++) {
            //i对应记录数组left的下表,所以当下表超出后属于右边数组的位置，这时index的数据为右边数组的值，切换数组
            if (i>=left.length){
                result[index] =right[j++];
            } else if (j>=right.length) {
                result[index] =   left[i++];
            }
            //大小判断,比较左右两边的数：如果左边的大就从右边（或者左边：升序降序控制）的数组抽出
            //放入最终的数组容器中，如果右边的大，则左边的数组抽出放入，i和j同时控制+1操作
            // 记录遍历的左右两个数组当前的指针
            else if (left[i] > right[j]){
                result[index] = right[j++];
            } else {
                result[index] =left[i++];
            }
        }
        return  result;
    }
}