侧边栏壁纸
博主头像
惊羽博主等级

hi ,我是惊羽,前生物学逃兵,现系统工程沉迷者 . 贝壳签约工程师 , 曾被雇佣为 联拓数科 · 支付研发工程师 、京东 · 京东数科 · 研发工程师、中国移动 · 雄安产业研究院 · 业务中台技术负责人 .

  • 累计撰写 100 篇文章
  • 累计创建 14 个标签
  • 累计收到 9 条评论

算法练习(5) - 归并排序

惊羽
2021-06-01 / 0 评论 / 0 点赞 / 163 阅读 / 1,166 字 / 正在检测是否收录...
温馨提示:
本文最后更新于 2021-11-05,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。
package top.buukle.buukle._02MergeSort;

import org.junit.Test;

import java.util.Arrays;

public class MergeSort {

    @Test
    public void mergeSort_test() {
//        Integer[] A = {31,41,59,26,41,58};
        Integer[] A = {9,8,7,6,5,4,3,2,1};
        Integer leftIndex = 0 ;
        Integer rightIndex = A.length -1;
        int[] temp = new int[A.length];
        sort(A,leftIndex,rightIndex,temp);
        System.out.println(Arrays.asList(A));
    }

    private void sort(Integer[] a, Integer leftIndex, Integer rightIndex, int[] temp) {
	// 设置递归结束条件为 左右索引相逢时
	if(leftIndex < rightIndex){
		int middle = (leftIndex + rightIndex) / 2;
		sort(a,leftIndex,middle,temp);
		sort(a,middle + 1,rightIndex,temp);	
		merge(a,leftIndex,middle,rightIndex,temp);
	}

    }

    private void merge(Integer[] a, Integer leftIndex, Integer middle, Integer rightIndex, int[] temp) {
        int piLeft = leftIndex;
	int piRight = middle + 1;	
	int tIndex = 0;
    	// 将排序好的2个数组按顺序合并为1个数组,并写到temp临时数组中
	while(piLeft < middle + 1 && piRight < rightIndex + 1){
		if(a[piLeft] < a[piRight ] ){
			temp[tIndex++] = a[piLeft++];
		}else{
			temp[tIndex++] = a[piRight++];
		}
	}
	while(piLeft < middle + 1){
		temp[tIndex++] = a[piLeft++];
	}
	while(piRight < rightIndex + 1){
		temp[tIndex++] = a[piRight++];
	}
	// 将临时数组的值,拷贝到原数组相应的索引之中
	tIndex =0;
	int copyIndex = leftIndex;
	while(leftIndex < rightIndex + 1){
		a[copyIndex ++] = temp[tIndex ++];
	}
    }

}


0
广告 广告

评论区