归并排序

package com.inforcreation;

import java.util.Arrays;

/**
 * 归并排序
 *
 * 归并排序（Merge sort）是建立在归并操作上的一种有效的排序算法，
 * 归并排序对序列的元素进行逐层折半分组，然后从最小分组开始比较排序，
 * 合并成一个大的分组，逐层进行，最终所有的元素都是有序的
 *
 *
 * 定义
 *
 * 归并排序（Merge Sort）是建立在归并操作上的一种有效，稳定的排序算法，该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。
 * 将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。
 *
 *
 *

 先将数组递归拆分成长度最大为2的小数组

 拆分阶段完成

 再对拆分后的子数组里面的数字进行排序，将小的移到左边，大的移到右边

 这样所有的子数组都是有序的了

 将这些有序的子数组进行归并

 归并阶段完成

 */
public class Mergesort {


/**
 * 初始数组： {7,8,6,4,5,1,2,3};
 * 1：折半拆分
 *     索引为0-7
 *       第一次差分  (0-7)/2  得到数组长度是4    范围是： 0-3   元素为： 7  8 6  4
 *       第二次拆分 (0+3)/2   得到数组长度是2    范围是：0-1    元素为： 7  8
 *       第三次拆分（0+1）/2   得到数组长度是1    范围是：0      元素为： 7     由于只有一个元素不能继续拆分所以 第二次拆分就可以走else逻辑进行比较
 *    推演展开1：
 *      7<8 直接返回【7，8】的数组
 *     接着拆分范围2-3 的数组 【6 4】
 *       走else里面的逻辑
 *         交换后返回【4，6】数组
 *      最后走mergeArrays把两个有序数组链接成一个有序数组
 *     推演展开2：
 *       获取一个长度为两个有序数组容量的数组
 *         leftArray和 rightArray数组都从下表0开始（此时他们里面都只有2个元素）
 *           左值小于右值，左值放入新数组，索引index++，leftIndex++
 *           右值小于左值，右值放入新数组，索引index++，rightIndex++
 *            直到index<finalArrayLength的条件不再满足，返回一个新的有序数组
 */

    /**
     * 归并排序
     * @param source
     * @return
     */
    private static int[] mergeSort(int[] source) {
        //数组长度
        int sourceLen = source.length;
//        7,8,6,4
        //如果长度大于2就拆分
        if(sourceLen > 2){
            //计算中间分割的索引位置
            int midIndex = sourceLen / 2;
            //对分割位置左边的数组进行递归拆分知道数组长度<=2
            int[] leftArray = mergeSort(Arrays.copyOf(source,midIndex));
            //对分割位置右边的数组进行递归拆分知道数组长度<=2
            //       {7,8,6,4,5,1,2,3};
            int[] rightArray = mergeSort(Arrays.copyOfRange(source,midIndex,sourceLen));
            //上面的递归已经将左右两边的子数组排好序，将两个有序的数组合并为一个数组
            int[] mergeArray = mergeArrays(leftArray,rightArray);
            return mergeArray;
        }
        // 否则说明集合中只有一个或者两个元素，可以进行这两个元素的比较排序了
        else{
            // 如果条件成立，说明数组中只有一个元素，或者是数组中的元素都已经排列好位置了
            if(sourceLen == 1 || source[0] <= source[1]) {
                return source;
            } else {
                //交换左右的值，也就是对子数组中的值排序
                int target[] = new int[sourceLen];
                target[0] = source[1];
                target[1] = source[0];
                return target;
            }
        }
    }
    /**
     * 合并两个有序集合
     * @param leftArray
     * @param rightArray
     * @return
     */
    private static int[] mergeArrays(int[] leftArray, int[] rightArray) {
        //定义一个新的容纳两个子数组的新数组
        int[] finalArray = new int[leftArray.length + rightArray.length];
        //左边子数组的长度
        int leftArrayLength = leftArray.length;
        //右边子数组的长度
        int rightArrayLength = rightArray.length;
        //合并后新数组的长度
        int finalArrayLength = finalArray.length;
        //只需要以新数组的长度便利一次即可
//       {7,8,6,4,5,1,2,3};
        for(int index = 0,leftIndex = 0,rightIndex = 0;index < finalArrayLength;index++){
            //获取左边集合当前索引上的值
            int leftValue = leftIndex >= leftArrayLength?Integer.MAX_VALUE:leftArray[leftIndex];
            //获取右边集合当前索引上的值
            int rightValue = rightIndex >= rightArrayLength?Integer.MAX_VALUE:rightArray[rightIndex];
            //如果左边数组索引上的值<右边数组索引上的值，那么新数组就是左边数组索引上的值
            if(leftValue < rightValue){
                leftIndex++;
                finalArray[index] = leftValue;
            }
            //否则就取右边数组索引上的值
            else{
                rightIndex++;
                finalArray[index] = rightValue;
            }
        }
        return finalArray;
    }

}