文档章节

合并排序

notAcoder
 notAcoder
发布于 2013/09/13 19:07
字数 449
阅读 26
收藏 0

合并排序采用分治的模式,分治模式在每一层递归上都有3个步骤:

1、分解(Divide):将原问题分解成一系列的子问题。

2、解决(Conquer):递归第解决子问题。

3、合并(Combine):将子问题的结果合并成原问题的解。

合并排序完全按照上面的模式,直观的操作如下:

分解:将n个元素分成n/2个元素的子问题。

解决:用合并排序对两个子序列递归的排序。

合并:合并两个已经排序的子序列得到排序的结果。

用java实现的合并排序代码如下:

import java.util.Arrays;

public class MergeSortTest {
	
	public static void main(String[] args) {
		int a[] = {100,2,9,6,3,4,7,45,11,1,8};
		merge_sort(a,0,a.length-1);
		System.out.println(Arrays.toString(a));
	}
	
	public static void merge_sort(int a[],int p, int r){
		if(p<r){
			//分解
			int q = (p+r)/2;
			merge_sort(a,p,q);
			merge_sort(a,q+1,r);
			//合并
			merge(a,p,q,r);
		}
	}
	
	//合并两个已经排好序的数组到目标数组a中
	public static void merge(int []a,int p,int q,int r)
	{
		int n1 = q-p+1;
		int n2 = r-q;
		int L[] = new int[n1];
		int R[] = new int[n2];
		int i,j,k;
		for(i=0; i<n1; i++)
		{
			L[i] = a[p+i];
		}

		for (j=0; j<n2; j++) 
		{
			R[j] = a[q+j+1]; 
		}

		i = 0;
		j = 0;

		for (k=p; k<=r;k++) 
		{
			
			if (L[i]>=R[j]) {
				a[k] = L[i];
				i++;
				//如果L数组中的所有元素全部被复制到a中了,就把R数组中剩下的元素全部复制到a数组中
				if(i==n1){
					k++;
					for (;  j< R.length; j++) {
						a[k++] = R[j];
					}
					break;
				}
			}else{
				a[k] = R[j];
				j++;
				//如果R数组中的所有元素全部被复制到a中了,就把L数组中剩下的元素全部复制到a数组中
				if(j==n2){
					k++;
					for (;  i< L.length; i++) {
						a[k++] = L[i];
					}
					break;
				}
			}
			
		}
	}

}
结果:

[100, 45, 11, 9, 8, 7, 6, 4, 3, 2, 1]


© 著作权归作者所有

上一篇: 插入排序
下一篇: 模2运算的原理
notAcoder
粉丝 5
博文 30
码字总数 12671
作品 0
巴南
架构师
私信 提问
排序——合并排序法

一、合并排序法的概念 合并排序(Merge Sort)就是将两个或多个有序表合并成一个有序表。将两个有序表合并成一个有序表的过程称为二路合并。 二、算法描述 二路合并排序的基本思想是:对于两...

翼动动空
2016/06/17
1K
0
【译】Swift算法俱乐部-归并排序

本文是对 Swift Algorithm Club 翻译的一篇文章。 Swift Algorithm Club是 raywenderlich.com网站出品的用Swift实现算法和数据结构的开源项目,目前在GitHub上有18000+⭐️,我初略统计了一下...

Andy_Ron
2018/09/23
0
0
java中Arrays.sort()实现原理

先在网上找到一些说法: java中Arrays.sort使用了两种排序方法,快速排序和优化的合并排序。 快速排序主要是对哪些基本类型数据(int,short,long等)排序, 而合并排序用于对对象类型进行排序...

liujiest
2016/05/07
1K
0
JAVA 实现 归并排序算法

什么是合并? 与很多有用的算法类似,合并排序基于这样一个技巧:将 2 个大小为 N/2 的已排序序列合并为一个 N 元素已排序序列仅需要 N 次操作。这个方法叫做合并。 我们用个简单的例子来看看...

颓废的幻想者
2016/08/22
46
0
合并排序,合为重

陆小凤原创 小白:陆大侠,从快排到合排,算法思想有变化吗? 陆小凤:在设计思想上,它们是一样的,都是“分而治之”的思想。 小白:“分而治之”,就是我老板常说的话啦:“没有什么是搞不...

奇哥十年程序
2017/12/14
0
0

没有更多内容

加载失败,请刷新页面

加载更多

Jenkins World 贡献者峰会及专家答疑展位

本文首发于:Jenkins 中文社区 原文链接 作者:Marky Jackson 译者:shunw Jenkins World 贡献者峰会及专家答疑展位 本文为 Jenkins World 贡献者峰会活动期间的记录 Jenkins 15周岁啦!Jen...

Jenkins中文社区
31分钟前
8
0
杂谈:面向微服务的体系结构评审中需要问的三个问题

面向微服务的体系结构如今风靡全球。这是因为更快的部署节奏和更低的成本是面向微服务的体系结构的基本承诺。 然而,对于大多数试水的公司来说,开发活动更多的是将现有的单块应用程序转换为...

liululee
45分钟前
7
0
OSChina 周二乱弹 —— 我等饭呢,你是不是来错食堂了?

Osc乱弹歌单(2019)请戳(这里) 【今日歌曲】 @ 自行车丢了:给主编推荐首歌 《クリスマスの夜》- 岡村孝子 手机党少年们想听歌,请使劲儿戳(这里) @烽火燎原 :国庆快来,我需要长假! ...

小小编辑
今天
460
9
玩转 Springboot 2 之热部署(DevTools)

Devtools 介绍 SpringBoot 提供了热部署的功能,那啥是热部署累?SpringBoot官方是这样说的:只要类路径上的文件发生更改,就会自动重新启动应用程序。在IDE中工作时,这可能是一个有用的功能...

桌前明月
今天
6
0
CSS--列表

一、列表标识项 list-style-type none:去掉标识项 disc:默认实心圆 circle:空心圆 squire:矩形 二、列表项图片 list-style-img: 取值:url(路径) 三、列表项位置 list-style-position:...

wytao1995
今天
10
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部