归并排序

import org.junit.Test;

import java.util.Arrays;

/**
 * Created by wc on 2018/4/28.
 */

public class 归并排序 {

    @Test
    public void test(){
        int [] array={1,2,5,9,3,4,10,16};
        mergeSort(array,0,array.length-1);
        System.out.print(Arrays.toString(array));
    }

    /**
     * 数据量很大且链式结构
     * @param array
     * @param start
     * @param mid
     * @param end
     */
    public void merge(int[] array,int start,int mid,int end){
        int leftSize=mid-start;
        int rightSize=end-mid;
        int[] leftArray=new int[leftSize];
        int[] rightArray=new int[rightSize];
        //填充数组
        for(int i=start;i<mid;i++){
            leftArray[i-start]=array[i];
        }
        for(int i=mid;i<end;i++){
            rightArray[i-mid]=array[i];
        }

        //合并数组
        int i=0;
        int j=0;
        int k=start;
        while(i<leftSize&&j<rightSize){
            if(leftArray[i]<rightArray[j]){
                array[k++]=leftArray[i++];
            }else{
                array[k++]=rightArray[j++];
            }
        }

        while(i<leftSize){
            array[k++]=leftArray[i++];
        }

        while(j<rightSize){
            array[k++]=rightArray[j++];
        }
    }
    public void mergeSort(int[] array,int left,int right){
        if(left==right){
            return ;
        }else{
            int mid=(left+right)>>1;
            //后序遍历
            mergeSort(array,left,mid);//对左边的排序
            mergeSort(array,mid+1,right);//对右边的排序
            merge(array,left,mid+1,right);//在对左右进行融合
        }
    }
}