文档章节

排序算法笔记:归并排序 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

没有更多内容

加载失败,请刷新页面

加载更多

用PyTorch创建一个图像分类器?So easy!(Part 1)

摘要: 本文将为你介绍为何要重用神经网络?哪部分可以重用,哪部分不可以重用。了解完这些基础概念,你就可以自行创建一个图像分类器了。 经过了几个月的学习和实践,我完成了优达学城网站上...

阿里云官方博客
6分钟前
0
0
ssh使用正确的密码登录服务器被拒绝

1、用一个普通用户登录服务器被拒绝。 2、在服务器上,tail -f /var/log/secure, 看到: Dec 19 11:03:20 mmi5 sshd[11126]: pam_tally2(sshd:auth): user carrot (1003) tally 144, deny 3 ......

gelare
6分钟前
0
0
基于腾讯AI Lab词向量进行未知词、短语向量补齐与域内相似词搜索

AI Lab开源大规模高质量中文词向量数据,800万中文词随你用,质量非常高,就是一个词向量.txt文件都有16G之多,太夸张了。。不过的确非常有特点: ⒈ 覆盖率(Coverage): 该词向量数据包含...

火力全開
9分钟前
0
0
Shiro简介——《跟我学Shiro》

1、《跟我学Shiro》PDF完结版下载 2、shiro简介——《跟我学Shiro》 3、shiro demo

近在咫尺远在天涯
9分钟前
0
0
教你一个vue小技巧,一般人我不说的

本文由云+社区发表 1. 需求 最近的项目中,需要实现在vue框架中动态渲染带提示框的单选/多选文本框,具体的效果如下图所示,在输入框聚焦时,前端组件通过接收的kv参数渲染出选项,用户点击选...

腾讯云加社区
12分钟前
0
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部