算法<四>归并排序
2019-07-05 本文已影响0人
小吖么小一郎
适用于合并数组
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的最后被抛弃
}
}