排序之归并排序

前言

  由于工作原因,好一段时间没有更新博客了,这里表示抱歉了!

基本思想

  “归并”一词的中文含义就是合并、并入的意思,而在数据结构中的定义是将两个或两个以上的有序表组合成一个新的有序表。既然是归并、并入,那么必然就有子序列了,子序列从何而来,当然是目标序列拆分而来啦! 就是先拆分,在合并。 归并排序(Merging Sort)就是利用归并的思想实现的排序方法。它的原理是假设初始序列含有n个记录,则可以看成是n个有序的子序列,每个子序列的长度为1,然后两两归 并,得到⌈n/2⌉(⌈x⌉表示不小于x的最小整数)个长度为2或1的有序子序列;再两两归并,……,如此重复,直至得到一个长度为n的有序序列为止,这种排序方法称为2路归并排序。

其过程如图所示

代码实现

    public void mergeSort(int[] arr){
		mSort(arr,0,arr.length-1);
	}

	/**
	 * 先拆分,再归并
	 * @param arr
	 * @param min
	 * @param max
	 */
	private void mSort(int[] arr, int min, int max) {
		int mid = (min + max) / 2;
		if(min < max){
			mSort(arr,min,mid);			// 拆分arr[min...mid]
			mSort(arr,mid+1,max);		// 拆分arr[mid+1...max]
			merge(arr,min,mid,max);		// 归并有序序列arr[min...mid]和有序序列arr[mid+1...max]
		}
	}

	/**
	 * 归并arr[min...mid]和arr[mid+1...max]
	 * 此时arr[min...mid] arr[mid+1...max]分别有序
	 * @param arr
	 * @param min
	 * @param mid
	 * @param max
	 */
	private void merge(int[] arr, int min, int mid, int max) {
		int[] tarr = new int[max+1];
		int i=min,j=mid+1,tIndex=min;
		// 将arr[min...mid]与arr[mid+1...max]中元素从小到大逐个赋值到tarr数组中
		while(i<=mid && j<=max){
			if(arr[i] < arr[j]){
				tarr[tIndex++] = arr[i++];
			} else {
				tarr[tIndex++] = arr[j++];
			}
		}
		// arr[min...mid]中元素已经全部赋值到tarr中,将arr[mid+1...max]剩余的元素赋值到tarr中
		if(i>mid){
			while(j<=max){
				tarr[tIndex++] = arr[j++];
			}
		}
		// arr[mid+1...max]中元素已经全部赋值到tarr中,将arr[min...mid]剩余的元素赋值到tarr中
		if(j>max){
			while(i<=mid){
				tarr[tIndex++] = arr[i++];
			}
		}
		//将临时数组tarr中有序序列赋值到目标数组arr中,使之arr[min...max]有序
		for(int k=min; k<=max; k++){
			arr[k] = tarr[k];
		}
	}

执行过程模拟

  其实上图已经模拟出来整个程序的执行过程,先进行拆分,然后归并,代码中注释也已经写的很清楚了,具体的模拟过程就博主就不演示了,不清楚的就请自己根据代码进行模拟了。

总结

  其实思想是比较好理解的,实现也不是那么难,最难的其实是光说不练、不去实现,总认为理解思想就够了,可结果是当你真正去实现的时候你发现并不是那么的容易;理解别人的思路、融入自己的理解、付之实践(代码实现)、实践优化,最终完全理解!

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏编程

Python入门基础连载(2)数据结构

Python数据结构包括了列表(list),元组(tuple),字典(dict)和集合(set),这些也都可以称之为容器,下面Cooldog就和大家一起学习一下...

2037
来自专栏python学习之旅

Python笔记(七):字典、类、属性、对象实例、继承

(一)  简单说明    字典是Python的内置数据结构,将数据与键关联(例如:姓名:张三,姓名是键,张三就是数据)。例如:下面这个就是一个字典 {'姓名':...

3835
来自专栏非著名程序员

鸡蛋问题来了,是先有Class还是先有Object?

周末比较无聊,在浏览论坛的时候,偶然看到一个程序猿提问的问题,他时这样提问的:突然想到一个很菜的问题, 倒底先有Object还是先有Class?所有类都是Obj...

2036
来自专栏zhisheng

运算优先级、结合性、求值顺序、副作用和顺序点

标题中这几个概念,是很多C/C++程序员在表达式上容易出问题或不清楚的地方,虽然这些概念在很多语言都有体现,但C里面特别明显,所以就以C语言为例子总结下 运算...

4667
来自专栏PHP在线

php面试题(一)

1 <?php echo -10%3; ?> 答案:-1。 考查:优先级。 因为-的优先级比%求余的优先级低,也就是-(10%3)。 2 print (int...

3707
来自专栏ACM算法日常

简单计算器(栈的变种)- HDU 1237

测试输入包含若干测试用例,每个测试用例占一行,每行不超过200个字符,整数和运算符之间用一个空格分隔。没有非法表达式。当一行中只有0时输入结束,相应的结果不要输...

1211
来自专栏程序员的知识天地

Python里面这些点,据说80%的新手都会一脸懵逼

Python虽然语法简单,通俗易懂,但是再简单它也是一门语言,就像一棵大树,总有一些树枝是弯弯绕绕的,让新手看完之后一脸懵逼,今天我们就来说说这几个点,反正我学...

773
来自专栏程序员互动联盟

【专业知识】 Webkit智能指针用法

历史: 在WebKit中,许多对象采用了引用计数。这种模式是通过类的ref,deref成员函数来递增和递减对象的引用记数。调用一次ref必须调用一次der...

35715
来自专栏从流域到海域

《笨办法学Python》 第29课手记

《笨办法学Python》 第29课手记 本节课讲if语句。 本节内容比较简单,如果觉得你的代码没有错误,但运行时报错,那么你的代码肯定有错误。相信我解释器是已经...

1996
来自专栏一名合格java开发的自我修养

java或判断优化小技巧

写业务代码的时候,我们经常要做条件判断,有的时候条件判断的或判断长达20多个。reg.equals("1") || reg.equals("2") || reg...

621

扫码关注云+社区

领取腾讯云代金券