文档章节

归并排序

妹子快加微信
 妹子快加微信
发布于 2017/07/20 18:55
字数 949
阅读 11
收藏 0

归并排序:

          归并排序(MERGE-SORT)是利用归并的思想实现的排序方法,该算法采用经典的分治(divide-and-conquer)策略(分治法将问题(divide)成一些小的问题然后递归求解,而治(conquer)的阶段则将分的阶段得到的各答案"修补"在一起,即分而治之)。

-----------------------------------------------------------------------------------------------------

其实就是将数组分成一个个的数组,当无法拆分的时候(即数组只剩下一个),就是已经排好的顺序了。

当分到无法拆分的时候,就开始合并,即 2个数组进行合成排序。

ps:由于拆分到最小单位,成为1个数组只有1个 数字 的时候,合并,两个数字的合并。

这就是分治法:拆分。 

经过拆分,合并后 就成为一个有序的数组。

至于怎么拆分 拆到 数组个数为1个数字呢?

这就用到递归了。--------------跟 快速排序一样都是分治+递归。

因此

-------------------------------------------------------------------------------------

递归核心理解:

递归是从 2个 有序数组 开始排序的。因此从2个有序 数组说起。

    首先贴出来核心代码:

public static void main(String[] args) {
		//准备两个排好顺序的数组
		int[] arr1={1,3,7,9,55,999};
		int[] arr2={2,5,11,33,44,100,1000};
		//放排序好的数组
		int[] arr3=new int[arr1.length+arr2.length];
		//控制arr1
		int i=0;
		//控制arr2
		int j=0;
		//控制arr3
		int n=0;
		while(i<arr1.length && j<arr2.length){
			if(arr1[i]<arr2[j]){
				//如果arr1 数组当前的数字小于arr2
				//就把arr1的当前数字 放入arr3中
				arr3[n++]=arr1[i++];
			}else{
				//如果arr2 数组当前的数字小于arr1
				//就把arr2的当前数字 放入arr3中
				arr3[n++]=arr2[j++];
			}
		}
		//由于可能数组长度不同,或者 某个数组还未将其余的放入arr3中
		//如果i没有循环到 结尾 ,就 将其余的放入 arr3 中 ,
		//无需担心排序,因为之前就已经有序。
		while(i<arr1.length){
			arr3[n++]=arr1[i++];
		}
		while(j<arr2.length){
			arr3[n++]=arr2[j++];
		}
		System.out.println(Arrays.toString(arr3));
	}

这就是核心 排序方法,

----------------------------------------------------------------------------------------

归并排序代码

要记住 归并排序 就是  递归 分治 合并 三部分构成。

上面的例子如果能够理解的话,下面的代码就会更容易理解。



import java.util.Arrays;
import java.util.Random;

public class guibing {
	public static void main(String[] args) {
		int[] arr = new int[10];
		for (int i = 0; i < arr.length; i++) {
			arr[i] = new Random().nextInt(100);
		}
		sort(arr);
		System.out.println(Arrays.toString(arr));
	}

	private static void sort(int[] arr) {
		int[] temp = new int[arr.length];
		sort(arr, 0, arr.length - 1, temp);
	}

	private static void sort(int[] arr, int left, int right, int[] temp) {
		//当数组拆分成1个的时候,就是 递归拆分结束。
        if (left < right) {
			// 将数组从中间分开 成为2个数组
			int mid = (left + right) / 2;
			// 递归拆分左边
			sort(arr, left, mid, temp);
			// 递归拆分右边边
			sort(arr, mid + 1, right, temp);
			// 合并两个数组
			hebing(arr, left, mid, right, temp);
		}

	}

	private static void hebing(int[] arr, int left, int mid, int right, int[] temp) {
		int i = left;
		int j = mid + 1;
		int n = 0;
		while (i <= mid && j <= right) {
			// 归并排序的核心
			if (arr[i] < arr[j]) {
				temp[n++] = arr[i++];
			} else {
				temp[n++] = arr[j++];
			}
		}
		// 如果某组还有剩余,将剩余的放入
		while (i <= mid) {
			temp[n++] = arr[i++];
		}
		while (j <= right) {
			temp[n++] = arr[j++];
		}
		// 将排序好的数组放回去
		n = 0;
		while (left <= right) {
			arr[left++] = temp[n++];
		}
	}
}

脑子想想一下 ,根据上面给的图, 首先是拆分,拆成1个的时候,开始合并,合并后就是已经排好的数组了,然后接着合并(递归跟栈类似,慢慢往外弹)。当整个程序执行完成, 就完成了排序。

--------------------------------------------------------------------

http://www.92to.com/bangong/2016/11-28/13707795.html 推荐只看图。

http://www.cnblogs.com/chengxiao/p/6194356.html  推荐全看。

----------------------------------------------------------------------

不保证代码完全正确,也不保证代码是最优。

仅仅是根据自己的理解,写出来直观的代码,方便理解。

错误请指出,感激不尽!

 

© 著作权归作者所有

妹子快加微信
粉丝 1
博文 18
码字总数 26224
作品 0
洛阳
私信 提问

暂无文章

新架构、新角色:TiDB Community Upgrade!

作者:Jian Zhang 经过几年的发展,TiDB 社区已经逐渐成熟,但是随着社区的发展壮大,我们逐渐感受到了现在社区架构上的一些不足。经过一系列的思考和总结,我们决定升级和调整目前社区组织架...

TiDB
19分钟前
5
0
jquery qrcode库提示not function

jquery qrcode 这个库能用,但是必须在初始化的时候,官方给的使用方法是 引入qrcode的库文件后,在js中写以下 html <div id="qrcode"></div> js jQuery('#qrcode').qrcode({ render: ......

shikamaru
24分钟前
9
0
MySQL数据库去重的简单方案

利用 distinct 对需要处理的字段进行去重 select distinct 字段名 from 表名 利用group by select * from 表名 group by 字段名 利用having select * from 表名 group by 字段名 having 字段...

FeanLau
26分钟前
9
0
字符串转换成整数

实现一个 atoi 函数,使其能将字符串转换成整数。 首先,该函数会根据需要丢弃无用的开头空格字符,直到寻找到第一个非空格的字符为止。 当我们寻找到的第一个非空字符为正或者负号时,则将该...

蔚蓝_晴天
37分钟前
8
0
Eureka客户端续约及服务端过期租约清理源码解析

在之前的文章:EurekaClient自动装配及启动流程解析中,我们提到了在构造DiscoveryClient时除了包含注册流程之外,还调度了一个心跳线程: scheduler.schedule( new Ti...

Java学习录
49分钟前
10
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部