文档章节

排序算法(4)--归并排序

haoran_10
 haoran_10
发布于 2016/07/15 16:39
字数 859
阅读 4
收藏 0

简介:归并排序是建立在归并操作上的一种有效的排序算法,该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。

将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为二路归并

 

一、主要步骤

将待排序数组[0...n-1]看成是n个长度为1的有序序列,将相邻的有序表成对归并,得到n/2个长度为2的有序表;将这些有序序列再次归并,得到n/4个长度为4的有序序列;如此反复进行下去,最后得到一个长度为n的有序序列。

综上可知:

归并排序其实要做两件事:

(1)“分解”——将序列每次折半划分

(2)“合并”——将划分后的序列段两两合并后排序

 

二、演示过程

1、先看合并

(1)、两端相邻的有序子数组,arr[start]~arr[mid] 称为数组A和arr[mid+1]~arr[end] 称为数组B

(2)、每次各从数组A和数组B中取出一个值相比较,小的一个放到临时数组C

(3)、最后数组A和数组B中的数据取完时,数组C就是一个有序的合并后的数组。

(4)、最后在临时数组复制到原数组中

2、在看分解

(1)、先把数组分成最细,gap=1,然后把相邻的两个数据合并排序

(2)、然后设置gap=2,继续把相邻的两个数组合并。若子表个数为奇数,则最后一个子表无须和其他子表归并(即本趟处理轮空);

            若子表个数为偶数,则要注意到最后一对子表中后一个子表区间的上限为n-1。

(3)、直到gap等于数组的长度,数组合并完成

 

如图所示:



 

 

 

三、代码实现

@Override
public void sort(int[] arr) {
	mergeSort(arr);
}

private void merge(int[] array,int start,int mid,int end){
	int temp[] = new int[end-start+1];//临时数组
	
	int firstArrIndex = start;//第一段数组序列的下标
	int secondArrIndex = mid+1;//第二段数组序列的下标
	int tempArrIndex = 0;//临时存放数组的下标
	
	//1.扫描第一个数组序列和第二个数组序列
	while(firstArrIndex <=mid && secondArrIndex<=end){
		//1.1 当第一段数组小于第二段数组 未排序的首个元素时
		if(array[firstArrIndex] <=array[secondArrIndex]){
			temp[tempArrIndex] = array[firstArrIndex];
			firstArrIndex++;
		}else{//1.2 当第二段数组小于第一段数组 未排序的首个元素时
			temp[tempArrIndex] = array[secondArrIndex];
			secondArrIndex++;
		}
		
		tempArrIndex++;
	}
	
	//2.当第一段没有复制完全时,将剩余的数组全部复制到临时数组
	while(firstArrIndex<=mid){
		temp[tempArrIndex] = array[firstArrIndex];
		firstArrIndex++;
		tempArrIndex++;
	}
	
	
	//3.当第二段没有复制完全时,讲剩余的数组全部复制到临时数组
	while(secondArrIndex<=end){
		temp[tempArrIndex] = array[secondArrIndex];
		secondArrIndex++;
		tempArrIndex++;
	}
	
	//4.将临时数组复制到原始数组
	for(tempArrIndex=0,firstArrIndex=start;firstArrIndex<=end;tempArrIndex++,firstArrIndex++){
		array[firstArrIndex] = temp[tempArrIndex];
	}
}

private void mergeSort(int[] arr){
	for (int gap = 1; gap < arr.length; gap = 2 * gap) {
		int i=0;
		//归并gap长度的两个相邻子数组
		for(i=0; i+2*gap-1< arr.length; i = i + 2*gap) {
			merge(arr, i, i+gap-1, i+2*gap-1);
		}
		
		// 余下不足两个合并的子数组。保证第一个数组gap存在。
		if(i + gap - 1 < arr.length){
			merge(arr, i, i + gap - 1, arr.length - 1);
		}
	}
}

 

 

© 著作权归作者所有

共有 人打赏支持
haoran_10
粉丝 25
博文 88
码字总数 80846
作品 0
杭州
程序员
私信 提问
线程基础:多任务处理(16)——Fork/Join框架(排序算法性能补充)

1、概述 在之前的一篇文章《线程基础:多任务处理(13)——Fork/Join框架(解决排序问题)》中,我们使用了fork/join框架提高归并排序的性 能。那篇文章发布后,有的读者联系我,觉得单就归...

yinwenjie
2017/06/06
0
0
8个常用算法的超常剖析

本文来自作者 jack 在 GitChat 上分享「最常用的 8 个排序算法:从原理到改进,再到代码兑现透彻解析」,「阅读原文」查看交流实录 「文末高能」 「更多同类话题」 「查看全部话题」 编辑 | ...

gitchat
2017/11/30
0
0
最常用的 8 个排序算法:从原理到改进,再到代码兑现透彻解析

作者:jack 1. 关于排序 很高兴与大家一起探讨计算机科学中的基础算法之排序算法。排序算法是非常基础同时又应用非常广泛的算法,无论在工作还是在生活中,比如: 数据库脚本,如MSSql, MySq...

小数点
2017/12/04
0
0
排序算法总结(一)---- 直接插入排序,希尔排序(java实现)

一、概述 排序有内部排序和外部排序,内部排序是数据记录在内存中进行排序,而外部排序是因排序的数据很大,一次不能容纳全部的排序记录,在排序过程中需要访问外存。 二、稳定性,时间复杂度...

ljheee
2017/04/08
0
0
算法系列【希尔排序】篇

常见的内部排序算法有:插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等。用一张图概括: 关于时间复杂度: 1. 平方阶 (O(n2)) 排序各类简单排序:直接插入...

湖南小影
2017/05/18
0
0

没有更多内容

加载失败,请刷新页面

加载更多

iOS切面编程

aop编程(面向切面编程),其原理也就是在不更改正常的业务处理流程的前提下,通过生成一个动态代理类,从而实现对目标对象嵌入附加的操作。在iOS中,要想实现相似的效果也很简单,利用OC的动态性,...

RainOrz
19分钟前
1
0
0006-Zookeeper指标分析

1. 问题描述 通过CDH管理平台,进入Zookeeper管理界面,Zookeeper的平均请求延迟、最小请求延迟、最大请求延迟指标趋势图维持不变,指标数据异常。 2.问题复现 登录CDH平台,进入Zookeeper管...

Hadoop实操
27分钟前
1
0
PAT(Basic Level) 乙级练习题 ------ 1047 编程团体赛 java

1047.编程团体赛 题目: 编程团体赛的规则为:每个参赛队由若干队员组成;所有队员独立比赛;参赛队的成绩为所有队员的成绩和;成绩最高的队获胜。 现给定所有队员的比赛成绩,请你编写程序找...

Carol998
31分钟前
1
0
抓包

1、下载 2、 tcpdump -i em1 host 目标域名 -n -X -s0 -w 写入文件名

HenryZhou2
33分钟前
1
0
axios 实现下载excel文件的说明~~~~遇到一个大坑,还是没有熟悉源码的罪过

本来下载文件直接用a标签,非常easy,但是如果数据量巨大的话,没有loading效果,用户体验非常差。优化项目的时候领导要求必须修改。因此只能用axios来下载了。 a标签下载: <a :href="dow...

YJ_
34分钟前
1
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部