文档章节

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

CheN_exe
 CheN_exe
发布于 2014/01/04 13:40
字数 237
阅读 53
收藏 0
点赞 0
评论 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
博文 31
码字总数 16744
作品 0
海淀
程序员
排序之概述

※、很多发布年代不清楚,如果你知道,如果你愿意,不妨告诉我和大家(包括这里没有列举且你认为有必要列举的)。 根据排序过程中涉及的存储器不同,可以将排序方法分为分内部排序和外部排序...

壶漏子 ⋅ 2015/06/01 ⋅ 0

外排序之归并排序

归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。 首先考虑下如何将将二个有序数列合并。这个非常简单,只要从比较二个数...

golang_yh ⋅ 2014/04/07 ⋅ 0

归并排序(merge sort)

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

itgangan ⋅ 2014/02/23 ⋅ 0

几种常见排序算法

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

brianway ⋅ 2016/05/08 ⋅ 2

JavaScript算法 ,Python算法,Go算法,java算法,系列之【归并排序】篇

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

湖南小影 ⋅ 2017/05/12 ⋅ 0

JavaScript算法 ,Python算法,Go算法,java算法,系列之【归并排序】篇

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

湖南小影 ⋅ 2017/05/12 ⋅ 0

Cousera 公开课Princeton Algorithms Part 1笔记:Mergesort

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

MrPickles ⋅ 2017/11/01 ⋅ 0

白话经典算法系列之五 归并排序的实现

归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。 首先考虑下如何将将二个有序数列合并。这个非常简单,只要从比较二个数...

长平狐 ⋅ 2012/12/10 ⋅ 0

排序的整理

自己之前搞的一些排序算法,希望对大家有帮助。差不多就这么多种吧。 void bubblesort(int *a,int n) //冒泡排序 {int i,j,t; for(i=0;i<n-1;i++) for(j=0;j<n-i-1;j++) { if(a[j]>a[j+1]) ......

fans1991 ⋅ 2013/04/11 ⋅ 0

用Java实现几种常见的排序算法

用Java语言实现的各种排序,包括插入排序、冒泡排序、选择排序、Shell排序、快速排序、归并排序、堆排序、SortUtil等。 插入排序: package org.rut.util.algorithm.support; import org.rut...

晨曦之光 ⋅ 2012/03/09 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

android -------- 颜色的半透明效果配置

最近有朋友问我 Android 背景颜色的半透明效果配置,我网上看资料,总结了一下, 开发中也是常常遇到的,所以来写篇博客 常用的颜色值格式有: RGB ARGB RRGGBB AARRGGBB 这4种 透明度 透明度...

切切歆语 ⋅ 10分钟前 ⋅ 0

CentOS开机启动subversion

建立自启动脚本: vim /etc/init.d/subversion 输入如下内容: #!/bin/bash## subversion startup script for the server## chkconfig: 2345 90 10# description: start the subve......

随风而飘 ⋅ 13分钟前 ⋅ 0

Nginx + uwsgi @ubuntu

uwsgi 安装 sudo apt-get install python3-pip # 注意 ubuntu python3默认没有安装pippython3 -m pip install uwsgi 代码(test.py) def application(env, start_response): start_res......

袁祾 ⋅ 14分钟前 ⋅ 0

版本控制工具

CSV , SVN , GIT ,VSS

颖伙虫 ⋅ 16分钟前 ⋅ 0

【2018.06.19学习笔记】【linux高级知识 13.1-13.3】

13.1 设置更改root密码 13.2 连接mysql 13.3 mysql常用命令

lgsxp ⋅ 24分钟前 ⋅ 0

LVM

LVM: 硬盘划分分区成物理卷->物理卷组成卷组->卷组划分逻辑分区。 1.磁盘分区: fdisk /dev/sdb 划分几个主分区 输入t更改每个分区类型为8e(LVM) 使用partprobe生成分区的文件:如/dev/sd...

ZHENG-JY ⋅ 52分钟前 ⋅ 0

彻底删除Microsoft Office的方法

参照此链接彻底删除Office https://support.office.com/zh-cn/article/%e4%bb%8e-pc-%e5%8d%b8%e8%bd%bd-office-9dd49b83-264a-477a-8fcc-2fdf5dbf61d8?ui=zh-CN&rs=zh-CN&ad=CN......

Kampfer ⋅ 今天 ⋅ 0

大盘与个股之间关系

大盘走多:积极出手 顺势加码 大盘走空: 少量出手 退场观望 大盘做头:逆势减码 少量操作 大盘做底 : 小量建仓 小量试单

guozenhua ⋅ 今天 ⋅ 0

Day16 LVM(逻辑卷管理)与磁盘故障小案例

lvm详解 简述 LVM的产生是因为传统的分区一旦分区好后就无法在线扩充空间,也存在一些工具能实现在线扩充空间但是还是会面临数据损坏的风险;传统的分区当分区空间不足时,一般的解决办法是再...

杉下 ⋅ 今天 ⋅ 0

rsync实现多台linux服务器的文件同步

一、首先安装rsync,怎样安装都行,rpm,yum,还是你用源码安装都可以。因为我用的是阿里云的ESC,yum install rsync就ok了。 二、配置rsync服务 1.先建立个同步数据的帐号 123 groupadd r...

在下头真的很硬 ⋅ 今天 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部