算法<四>归并排序

适用于合并数组

package com.example.demo.SortAlgorithm;
/*
 * @Author: i_heh
 * @Date: 2019/7/4
 * @Time: 18:14
 * @Description: 归并排序
 */
import org.junit.Test;
import java.util.Arrays;
public class MergeSort {

    //1 两个有序数组a,b合并成c
    static int[] sum(int[] a,int alen,int[] b,int blen,int[] c){
        //初始化三个指针对应三个数组
        int i,j,k;
        i=j=k=0;
        //循环直到i或j越界
        while (i<alen && j<blen){
            if (a[i]<b[j]){
                //先放小的数,放完+1
                c[k++]=a[i++];
            }else {
                c[k++]=b[j++];
            }
        }
        //经过上边的循环后的i,j如果还有元素,直接放进去
        while (i<alen){
            c[k++]=a[i++];
        }
        while (j<blen){
            c[k++]=b[j++];
        }
        return c;
    }
    @Test
    public void a1() {
        int[] a={1,3,5,7,9};
        int[] b={2,4,6,8,10,12,14};
        int[] c=new int[a.length+b.length];
        int[] sum = sum(a, a.length, b, b.length, c);
        System.out.println(Arrays.toString(sum));
    }
    //2 归并排序
    //递归,将数组分为两组,判断是否有序,无序继续分两组,直到有序
    @Test
    public void a2(){
        int[] arr={4,5,2,3,6,8,0,9,1,7};
        //start=1从第二个元素开始比较
        int[] res = merge(arr, 1, arr.length);
        System.out.println(Arrays.toString(res));
    }
    //合并方法
    public int[] merge(int[] data,int start,int end){
        if (start<end){
            //取中间点作分组尝试
            int mid=(start+end)/2;
            //递归再二分
            merge(data,start,mid);
            merge(data,mid+1,end);
            //调用分组方法
            System.out.println(Arrays.toString(data));
            part(data,start,mid,end);
        }
        return data;
    }
    //分两组方法
    public void part(int[] data,int start,int mid,int end){
        //分两组A和B,长度分别为中间到左右端长度
        int lena=mid-start+1;//start从1开始,要把这个长度补上
        int lenb=end-mid;
        int[] A=new int[lena+1];//左数组
        int[] B=new int[lenb+1];//右数组
        //分别遍历数组A和B,将给定数组的左右元素分别插入对应位置
        for (int i = 0; i < lena; i++) {
            A[i] = data[i+start-1];
        }A[lena]=Integer.MAX_VALUE;//将数组A的最后一个元素赋值为最大整数
        System.out.println("A:"+Arrays.toString(A));
        for (int i = 0; i < lenb; i++) {
            B[i] = data[i+mid];
        }B[lenb]=Integer.MAX_VALUE;
        System.out.println("B:"+Arrays.toString(B));
        //此时左右两个数组已经是有序的,依次比较放入小数即可
        int m=0;
        int n=0;
        for (int i = start-1; i < end; i++) {
            if (A[m]>B[n]){
                //先放小的数
                data[i]=B[n++];
            }else {
                data[i]=A[m++];
            }
        }
        //最终返回的数组长度依然为初始长度,因此追加的两个最大整数会在A,B的最后被抛弃
    }
}