文档章节

MergeSort -- 归并排序

ninjaFrog
 ninjaFrog
发布于 2017/09/07 23:47
字数 204
阅读 1
收藏 0

/*
 * 归并操作(merge),也叫归并算法,指的是将两个已经排序的序列合并成一个序列的操作。
 * 如设有数列{6,202,100,301,38,8,1}
 * 初始状态: [6] [202] [100] [301] [38] [8] [1] 比较次数
 * i=1 [6 202 ] [ 100 301] [ 8 38] [ 1 ]         3
 * i=2 [ 6 100 202 301 ] [ 1 8 38 ]              4
 * i=3 [ 1 6 8 38 100 202 301 ]             4
 */

public class MergeSort {
	public static void sort(int[] data) {
		int[] temp = new int[data.length];
		mergeSort(data, temp, 0, data.length - 1);
	}

	private static void mergeSort(int[] data, int[] temp, int l, int r) {
		int mid = (l + r) / 2;
		if (l == r)
			return;
		mergeSort(data, temp, l, mid);
		mergeSort(data, temp, mid + 1, r);

		for (int i = l; i <= r; i++) {
			temp[i] = data[i];
		}
		int i1 = l;
		int i2 = mid + 1;
		for (int cur = l; cur <= r; cur++) {
			if (i1 == mid + 1)
				data[cur] = temp[i2++];
			else if (i2 > r)
				data[cur] = temp[i1++];
			else if (temp[i1] < temp[i2])
				data[cur] = temp[i1++];
			else

				data[cur] = temp[i2++];
		}
	}
}

 

本文转载自:

共有 人打赏支持
ninjaFrog
粉丝 3
博文 66
码字总数 17262
作品 0
昌平
程序员
私信 提问
归并排序(merge sort)

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

itgangan
2014/02/23
0
0
关与归并排序的一个小问题

第四行的if换成while为什么会死循环?脑子都大了 void MergeSort(int arr[],int low,int high) {//用递归应用二路归并函数实现排序——分治法 if(low...

llwwzz
2014/08/29
27
1
js算法:Merge Sort 归并排序

Merge Sort : 归并排序,把一个大问题分解成若干相同的小问题,解决小问题后,合并小问题结果,最终把大问题解决.例如要排序数组 originArr = [2, 5, 3, 8, 9, 6, 3, 4, 2]先把问题分解为排序...

深山猎人
2016/06/15
56
0
几种常见排序算法

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

brianway
2016/05/08
133
2
白话经典算法系列之五 归并排序的实现

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

长平狐
2012/12/10
45
0

没有更多内容

加载失败,请刷新页面

加载更多

vue 对对象的属性进行修改时,不能渲染页面 vue.$set()

我在vue里的方法里给一个对象添加某个属性时,我console.log出来的是已经更改的object ,但是页面始终没有变化 原因如下: **受现代 JavaScript 的限制 (而且 Object.observe 也已经被废弃),...

Js_Mei
今天
2
0
开始看《Java学习笔记》

虽然书买了很久,但一直没看。这其中也写过一些Java程序,但都是基于IDE的帮助和对C#的理解来写的,感觉不踏实。 林信良的书写得蛮好的,能够帮助打好基础,看得出作者是比较用心的。 第1章概...

max佩恩
昨天
12
0
Redux 三大原则

1.单一数据源 在传统的MVC架构中,我们可以根据需要创建无数个Model,而Model之间可以互相监听、触发事件甚至循环或嵌套触发事件,这些在Redux中都是不被允许的。 因为在Redux的思想里,一个...

wenxingjun
昨天
8
0
跟我学Spring Cloud(Finchley版)-12-微服务容错三板斧

至此,我们已实现服务发现、负载均衡,同时,使用Feign也实现了良好的远程调用——我们的代码是可读、可维护的。理论上,我们现在已经能构建一个不错的分布式应用了,但微服务之间是通过网络...

周立_ITMuch
昨天
5
0
XML

学习目标  能够说出XML的作用  能够编写XML文档声明  能够编写符合语法的XML  能够通过DTD约束编写XML文档  能够通过Schema约束编写XML文档  能够通过Dom4j解析XML文档 第1章 xm...

stars永恒
昨天
2
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部