文档章节

排序算法笔记:归并排序 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
码字总数 17135
作品 0
海淀
程序员
归并排序(merge sort)

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

itgangan
2014/02/23
0
0
几种常见排序算法

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

brianway
2016/05/08
133
2
JavaScript算法 ,Python算法,Go算法,java算法,系列之【归并排序】篇

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

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

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

湖南小影
2017/05/12
0
0
Cousera 公开课Princeton Algorithms Part 1笔记:Mergesort

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

MrPickles
2017/11/01
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

JS三元运算示例

1. topFlag=topFlag ==0?1:0; 等于 if(topFlag=00){ topFlag=1; }else if(topFlag == 1){ topFlag=0; } 2. 5>3?alert('5大'):alert('3大'); 即 if(5>3){alert('5大')}else{alert('3大')}; 注......

森火
今天
0
0
利用Slf4j的MDC跟踪方法调用链

why? 一个web项目通常提供很多URL访问地址, 项目一般都是分层处理,例如Controller——>Service——>DAO。 如果想根据日志查看用户一次请求都走了哪些方法(多数是查错误)。 如果系统是多人...

杨春炼
今天
6
0
Maven介绍及安装

Maven介绍及安装 以下内容是本人早期学习时的笔记,可能比较详实繁琐,现在复习一下Maven,顺便将内容抛出来,供大家一起学习进步。 一、Maven简介 Maven是Apache旗下的一款项目管理工具,是...

星汉
今天
0
0
小程序Aes解密

主要步骤: 1、下载AES源码(JS版) 2、在小程序中新建一个公共的文件夹,把AES源码拷贝进去(注意:需要暴露接口 module.exports = CryptoJS;) 3、添加一个用于加密解密的公共JS,可取名为...

Mr_Tea伯奕
今天
0
0
Go实现文件传输(基本传输可用)

发送端 package mainimport ("fmt""os""net""io")func SendFile(path string, connect net.Conn){file, oerr :=os.Open(path)if oerr !=nil{fmt.Println("Open", oerr)......

CHONGCHEN
今天
2
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部