文档章节

排序算法笔记:归并排序 MergeSort

CheN_exe
 CheN_exe
发布于 2014/01/04 13:40
字数 237
阅读 53
收藏 0
/**
 * 归并排序
 * 简述:稳定算法
 * 		用递归的方式平分数组,直至只有一个元素为止.然后分别将两个数组进行排序并合并,直至数组完全合并为止.
 * 时间复杂度:
 * 		Θ(nlgn)
 * 空间复杂度:
 * 		O(n)
 * 递归式:
 * 		T(n) = if n=1 Θ(1)
 *        	   if n>1 2T(n/2)+Θ(n) 
 * 优点:
 * 		
 * 缺点:
 * 		
 * 可改进:
 * 		
 * @author CheN
 * 
 */
public class MergeSort {

	/**
	 * 正序int[]
	 * 
	 * @param int[]
	 */
	public static int[] asc( int[] array ) {
		return divide( array );
	}
	
	/**
	 * 分化
	 * @param array
	 * @return
	 */
	private static int[] divide( int[] array ) {
		if( array.length > 1 ){
			int[] leftArray = divide( Arrays.copyOfRange( array , 0, array.length/2 ));
			int[] rightArray = divide( Arrays.copyOfRange( array , array.length/2 , array.length ));
			return combine( leftArray , rightArray );
		}else{
			return array;
		}
	}
	
	/**
	 * 合并
	 * @param leftArray
	 * @param rightArray
	 * @return
	 */
	private static int[] combine( int[] leftArray, int[] rightArray ){
		int array[] = new int[leftArray.length + rightArray.length];
		int leftIndex = 0, rightIndex = 0;
		while( leftIndex + rightIndex < array.length ){
			if( leftIndex == leftArray.length ){
				array[ leftIndex + rightIndex ] = rightArray[rightIndex];
				rightIndex++;
			}else if( rightIndex == rightArray.length || leftArray[leftIndex] <= rightArray[rightIndex] ){
				array[ leftIndex + rightIndex ] = leftArray[leftIndex];
				leftIndex++;
			}else{
				array[ leftIndex + rightIndex ] = rightArray[rightIndex];
				rightIndex++;
			}
		}
		return array;
	}
}

 

若有错误或不妥之处,敬请谅解并指点。

© 著作权归作者所有

共有 人打赏支持
CheN_exe
粉丝 2
博文 40
码字总数 17192
作品 0
海淀
程序员
归并排序(merge sort)

归并排序 这是一种分治法的应用,就是对于一个待排序的序列,将它一分为二,二分为四……,分到最后,每一个序列中只会包含一个元素,这时,每一个小序列就已经有序了(因为只有一个元素,所...

itgangan
2014/02/23
0
0
JavaScript算法 ,Python算法,Go算法,java算法,系列之【归并排序】篇

常见的内部排序算法有:插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等。用一张图概括: 归并排序(英语:Merge sort,或mergesort),是创建在归并操作上...

湖南小影
2017/05/12
0
0
JavaScript算法 ,Python算法,Go算法,java算法,系列之【归并排序】篇

常见的内部排序算法有:插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等。用一张图概括: 归并排序(英语:Merge sort,或mergesort),是创建在归并操作上...

湖南小影
2017/05/12
0
0
几种常见排序算法

几种常见排序算法 标签: algorithms [TOC] 本文介绍几种常见排序算法(选择排序,插入排序,希尔排序,归并排序,快速排序,堆排序),对算法的思路、性质、特点、具体步骤、java实现以及t...

brianway
2016/05/08
133
2
Cousera 公开课Princeton Algorithms Part 1笔记:Mergesort

Mergesort merge sort里的基本思路就是递归的将要排序的数组划分成两个部分,然后将这两个子数组排序后在做归并,这样就得到一个排序后的数组。 一个简单的例子 mergesort uses at most Nlo...

MrPickles
2017/11/01
0
0

没有更多内容

加载失败,请刷新页面

加载更多

网站优化技术包括哪些内容

网站优化Incapsula超越简单的内容缓存,可以优化网站性能或应用程序的用户体验,优化包括内容缩小、动态文件压缩、图像压缩、会话重用优化、TCP优化和连接预合并。 动态文件压缩,普通的web...

上树的熊
11分钟前
0
0
业界 | Teradata全球调研:四分之三企业分析项目数据科学家“缺货”

当地时间10月15日,2018 Teradata全球用户大会在美国拉斯维加斯举行。来自15个国家的3000多位数据人参与了本次峰会。 大会第一日,Teradata发布了针对“企业数据分析”的2018年调研结果。 调...

Mr_zebra
12分钟前
0
0
java 通过Unsafe不使用构造器直接创建对象

这里有一个User没有无参构造 public class User { public User(String username, String password) { this.username = username; this.password = password; } ......

ValSong
14分钟前
0
0
eureka 高可用配置 unavailable-replicas 问题.

在使用spring cloud 配置eureka 高可用配置时.发现配置的节点一直无法获取心跳. eureka控制台界面上一直显示的挂载节点 是 unavailable-replicas 查看日志.就是获取心跳的地址不对. 默认的健...

拖鞋莫止步
14分钟前
0
0
Vue2 模板template的四种写法

<div id="app">    <h1>我是直接写在构造器里的模板1</h1></div> <template id="demo3">    <h1 style="color:red">我是选项模板3</h1></template> <script type="x-t......

粒子数反转
15分钟前
0
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部