文档章节

MergeSort -- 归并排序

NinjaFrog
 NinjaFrog
发布于 2017/09/07 23:47
字数 204
阅读 0
收藏 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
博文 64
码字总数 11574
作品 0
昌平
程序员
私信 提问
归并排序(merge sort)

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

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

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

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

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

llwwzz
2014/08/29
25
1
分治算法-归并,快排,快速选择

前言 大家好,感谢大家对前两篇博客的支持。今天我准备提供归并,快排,快速选择的笔记,这三个是分治算法的典型例子。这次有利用叠缩证明算法的时间界限哦!,另外代码已经放到码云上啦。 ...

温安适
2016/12/12
1K
5
几种常见排序算法

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

brianway
2016/05/08
133
2

没有更多内容

加载失败,请刷新页面

加载更多

Pycharm上Django的使用 Day8

1.添加新条目 1>编写用于添加新条目的表单 在forms.py中创建一个与模型Entry相关联的表单 1处给字段'text'指定一个空标签 2处定义小部件widgets,widgets是一个HTML表单元素 2>定义new_entry...

不会TC的猫
20分钟前
2
0
MongoDB副本集

MongoDB介绍 早期版本使用master-slave,一主一从和MySQL类似,但slave在此架构中为只读,当主库宕机后,从库不能自动切换为主 目前已经淘汰master-slave模式,改为副本集,这种模式下有一个...

chencheng-linux
33分钟前
1
0
WebService 客户端记录

https://blog.csdn.net/qiuhan/article/details/49487009

呼呼南风
33分钟前
0
0
七牛云彭垚:智能平台的创新和发展

2018 年 11 月 14 日至 11 月 18 日,第二十届中国国际高新技术成果交易会(简称高交会)在深圳成功举办,七牛云作为国内领先的以数据智能和视觉智能为核心的企业级云计算服务商受邀参展。 ...

七牛云
40分钟前
0
0
Java内存模型原理,你真的理解透彻了吗?

内存模型产生背景 在介绍 Java 内存模型之前,我们先了解一下物理计算机中的并发问题,理解这些问题可以搞清楚内存模型产生的背景。 物理机遇到的并发问题与虚拟机中的情况有不少相似之处,物...

小刀爱编程
45分钟前
2
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部