文档章节

MergeSort -- 归并排序

gackey
 gackey
发布于 2017/09/07 23:47
字数 204
阅读 17
收藏 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++];
		}
	}
}

 

本文转载自网络

gackey

gackey

粉丝 4
博文 77
码字总数 22015
作品 0
昌平
程序员
私信 提问
加载中

评论(0)

今天会是有Offer的一天么:面试时你真的会写归并排序么

UP打算把八大排序算法中最难理解的几种整理一下,分别是归并排序、快排和堆排序。今天先介绍归并排序。 先说一下归并排序的图解 所谓的归并,是将两个或两个以上的有序文件合并成为一个新的有...

今天会是有offfer的一天么
04/19
0
0
归并排序(递归、非递归、以及自然归并排序)算法总结

注:本文所指归并排序指 二路归并排序。 归并排序是平均情况、最坏情况、最好情况时间复杂度都为O(Nlog2N)的稳定的排序算法。最近梳理了下归并排序的递归、非递归、以及自然归并排序算法。...

osc_0zs17uxd
2018/05/28
1
0
归并排序(merge sort)

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

itgangan
2014/02/23
101
0
js算法:Merge Sort 归并排序

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

深山猎人
2016/06/15
137
0
关与归并排序的一个小问题

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

llwwzz
2014/08/29
48
1

没有更多内容

加载失败,请刷新页面

加载更多

Apache Jmeter 入门

Jmeter是一款优秀的开源测试工具, 是每个资深测试工程师,必须掌握的测试工具,熟练使用Jmeter能大大提高工作效率。 本文将通过一个实际的测试例子, 来讲解Jmeter的基本用法。 Jmeter 介绍...

JEECG开源社区
33分钟前
21
0
Spring Cloud 系列之 Apollo 配置中心(二)

本篇文章为系列文章,未读第一集的同学请猛戳这里:Spring Cloud 系列之 Apollo 配置中心(一) 本篇文章讲解 Apollo 部门管理、用户管理、配置管理、集群管理。      点击链接观看:Apo...

哈喽沃德先生
34分钟前
20
0
原生ES-Module

首先是各大浏览器从何时开始支持module的: Safari 10.1 Chrome 61 Firefox 54 (有可能需要你在about:config页面设置启用dom.moduleScripts.enabled) Edge 16 使用方式 首先在使用上,唯一的...

东东笔记
35分钟前
10
0
DevExpress Winforms使用技巧与窍门集合(2020年5月汇总)

下载DevExpress v20.1完整版 DevExpress Winforms Controls 内置140多个UI控件和库,完美构建流畅、美观且易于使用的应用程序。想要体验?点击下载>> 本文中包含一些示例和调整WinForms UI组...

FILA6666
36分钟前
18
0
SwitchGlass for mac 1.4(331) 系统应用快速启动

mac系统应用怎么才能快速启动?这时候你需要一款mac系统应用快速启动软件!SwitchGlass Mac版是Mac电脑上的一款系统应用快速启动工具。SwitchGlass Mac版为你的Mac应用增加了一个专用的应用程...

麦克W
39分钟前
16
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部