文档章节

排序-归并排序

一杯82年的JAVA
 一杯82年的JAVA
发布于 2016/05/04 20:45
字数 368
阅读 55
收藏 5

【推荐】2019 Java 开发者跳槽指南.pdf(吐血整理) >>>

主要内容:

分解:把序列按一定长度(1、2、4、8……)划分成若干部分

合并:将划分后的序列两两合并

(来源:http://www.cnblogs.com/jingmoxukong/p/4308823.html )


java代码:

public class MergeSort {

	public static void main(String[] args) {
		int[] array = { 2, 3, 5, 1, 4, 6, 8, 7 };
		mergeSort(array, 1);
		printArray(array);
	}

	// 每个分组有d个元素
	public static void mergeSort(int[] array, int d) {
		if (d == array.length)
			return;
		// 当数组长度不是2的整数次方时会导致无法完美分割,最后会有一个长序列和一个短序列,此时需要额外进行一次合并
		if (d > array.length) {
			System.out.print("d=" + d + "/2=" + d / 2 + ": ");
			merge(array, 0, d / 2 - 1, array.length - 1);
			return;
		}
		for (int i = 0; i + 2 * d - 1 < array.length; i = i + 2 * d) {
			merge(array, i, i + d - 1, i + 2 * d - 1);
		}
		System.out.print("d=" + d + ":  ");
		printArray(array);
		mergeSort(array, d * 2);
	}

	// 合并array[left,mid] 和 array[mid+1,right]两个区间,这两个区间已经是有序的了
	private static void merge(int[] array, int left, int mid, int right) {
		int[] temp = new int[right - left + 1];
		int l = left, r = mid + 1, t = 0;
		while (l <= mid && r <= right) {
			if (array[l] < array[r])
				temp[t++] = array[l++];
			else
				temp[t++] = array[r++];
		}
		while (l <= mid) {
			temp[t++] = array[l++];
		}
		while (r <= right) {
			temp[t++] = array[r++];
		}
		for (int i = left, j = 0; i <= right; i++, j++) {
			array[i] = temp[j];
		}
	}

	private static void printArray(int[] array) {
		for (int i = 0; i < array.length - 1; i++)
			System.out.print(array[i] + ",");
		System.out.println(array[array.length - 1]);
	}
}


测试:

int[] array = { 2, 3, 5, 1, 4, 6, 8, 7 };

输出:

d=1:  2,3,1,5,4,6,7,8

d=2:  1,2,3,5,4,6,7,8

d=4:  1,2,3,4,5,6,7,8

1,2,3,4,5,6,7,8

//

int[] array = { 2, 3, 5, 1, 4 };

输出:

d=1:  2,3,1,5,4

d=2:  1,2,3,5,4

d=4:  1,2,3,5,4

d=8/2=4: 1,2,3,4,5


© 著作权归作者所有

一杯82年的JAVA
粉丝 8
博文 76
码字总数 36575
作品 0
杭州
程序员
私信 提问

暂无文章

在C语言中“静态”是什么意思?

我已经在C代码的不同地方看到了static一词。 这就像C#中的静态函数/类(实现在对象之间共享)吗? #1楼 多文件变量作用域示例 在这里,我说明了静态如何影响多个文件中函数定义的范围。 交流...

javail
12分钟前
3
0
利用 FC + OSS 快速搭建 Serverless 实时按需图像处理服务

作者:泽尘 简介 随着具有不同屏幕尺寸和分辨率设备的爆炸式增长,开发人员经常需要提供各种尺寸的图像,从而确保良好的用户体验。目前比较常见的做法是预先为一份图像存放多份具有不同尺寸的...

阿里巴巴云原生
15分钟前
2
0
前端架构最佳实践

Folders-by-Feature Structure 胜过 Folders-by-Type Structure

lilugirl
25分钟前
3
0
Seata AT 模式启动源码分析

从上一篇文章「分布式事务中间件Seata的设计原理」讲了下 Seata AT 模式的一些设计原理,从中也知道了 AT 模式的三个角色(RM、TM、TC),接下来我会更新 Seata 源码分析系列文章。今天就来分...

后端进阶
26分钟前
4
0
Python中“自我”一词的目的是什么?

Python中self词的目的是什么? 我知道它是指从该类创建的特定对象,但是我看不到为什么要将它显式地作为参数添加到每个函数中。 为了说明这一点,在Ruby中,我可以这样做: class myClass ...

技术盛宴
28分钟前
3
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部