文档章节

排序算法(4)--归并排序

haoran_10
 haoran_10
发布于 2016/07/15 16:39
字数 859
阅读 4
收藏 0

简介:归并排序是建立在归并操作上的一种有效的排序算法,该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。

将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为二路归并

 

一、主要步骤

将待排序数组[0...n-1]看成是n个长度为1的有序序列,将相邻的有序表成对归并,得到n/2个长度为2的有序表;将这些有序序列再次归并,得到n/4个长度为4的有序序列;如此反复进行下去,最后得到一个长度为n的有序序列。

综上可知:

归并排序其实要做两件事:

(1)“分解”——将序列每次折半划分

(2)“合并”——将划分后的序列段两两合并后排序

 

二、演示过程

1、先看合并

(1)、两端相邻的有序子数组,arr[start]~arr[mid] 称为数组A和arr[mid+1]~arr[end] 称为数组B

(2)、每次各从数组A和数组B中取出一个值相比较,小的一个放到临时数组C

(3)、最后数组A和数组B中的数据取完时,数组C就是一个有序的合并后的数组。

(4)、最后在临时数组复制到原数组中

2、在看分解

(1)、先把数组分成最细,gap=1,然后把相邻的两个数据合并排序

(2)、然后设置gap=2,继续把相邻的两个数组合并。若子表个数为奇数,则最后一个子表无须和其他子表归并(即本趟处理轮空);

            若子表个数为偶数,则要注意到最后一对子表中后一个子表区间的上限为n-1。

(3)、直到gap等于数组的长度,数组合并完成

 

如图所示:



 

 

 

三、代码实现

@Override
public void sort(int[] arr) {
	mergeSort(arr);
}

private void merge(int[] array,int start,int mid,int end){
	int temp[] = new int[end-start+1];//临时数组
	
	int firstArrIndex = start;//第一段数组序列的下标
	int secondArrIndex = mid+1;//第二段数组序列的下标
	int tempArrIndex = 0;//临时存放数组的下标
	
	//1.扫描第一个数组序列和第二个数组序列
	while(firstArrIndex <=mid && secondArrIndex<=end){
		//1.1 当第一段数组小于第二段数组 未排序的首个元素时
		if(array[firstArrIndex] <=array[secondArrIndex]){
			temp[tempArrIndex] = array[firstArrIndex];
			firstArrIndex++;
		}else{//1.2 当第二段数组小于第一段数组 未排序的首个元素时
			temp[tempArrIndex] = array[secondArrIndex];
			secondArrIndex++;
		}
		
		tempArrIndex++;
	}
	
	//2.当第一段没有复制完全时,将剩余的数组全部复制到临时数组
	while(firstArrIndex<=mid){
		temp[tempArrIndex] = array[firstArrIndex];
		firstArrIndex++;
		tempArrIndex++;
	}
	
	
	//3.当第二段没有复制完全时,讲剩余的数组全部复制到临时数组
	while(secondArrIndex<=end){
		temp[tempArrIndex] = array[secondArrIndex];
		secondArrIndex++;
		tempArrIndex++;
	}
	
	//4.将临时数组复制到原始数组
	for(tempArrIndex=0,firstArrIndex=start;firstArrIndex<=end;tempArrIndex++,firstArrIndex++){
		array[firstArrIndex] = temp[tempArrIndex];
	}
}

private void mergeSort(int[] arr){
	for (int gap = 1; gap < arr.length; gap = 2 * gap) {
		int i=0;
		//归并gap长度的两个相邻子数组
		for(i=0; i+2*gap-1< arr.length; i = i + 2*gap) {
			merge(arr, i, i+gap-1, i+2*gap-1);
		}
		
		// 余下不足两个合并的子数组。保证第一个数组gap存在。
		if(i + gap - 1 < arr.length){
			merge(arr, i, i + gap - 1, arr.length - 1);
		}
	}
}

 

 

© 著作权归作者所有

共有 人打赏支持
haoran_10
粉丝 25
博文 88
码字总数 80846
作品 0
杭州
程序员
线程基础:多任务处理(16)——Fork/Join框架(排序算法性能补充)

1、概述 在之前的一篇文章《线程基础:多任务处理(13)——Fork/Join框架(解决排序问题)》中,我们使用了fork/join框架提高归并排序的性 能。那篇文章发布后,有的读者联系我,觉得单就归...

yinwenjie
2017/06/06
0
0
排序算法总结(一)---- 直接插入排序,希尔排序(java实现)

一、概述 排序有内部排序和外部排序,内部排序是数据记录在内存中进行排序,而外部排序是因排序的数据很大,一次不能容纳全部的排序记录,在排序过程中需要访问外存。 二、稳定性,时间复杂度...

ljheee
2017/04/08
0
0
8个常用算法的超常剖析

本文来自作者 jack 在 GitChat 上分享「最常用的 8 个排序算法:从原理到改进,再到代码兑现透彻解析」,「阅读原文」查看交流实录 「文末高能」 「更多同类话题」 「查看全部话题」 编辑 | ...

gitchat
2017/11/30
0
0
最常用的 8 个排序算法:从原理到改进,再到代码兑现透彻解析

作者:jack 1. 关于排序 很高兴与大家一起探讨计算机科学中的基础算法之排序算法。排序算法是非常基础同时又应用非常广泛的算法,无论在工作还是在生活中,比如: 数据库脚本,如MSSql, MySq...

小数点
2017/12/04
0
0
算法系列【希尔排序】篇

常见的内部排序算法有:插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等。用一张图概括: 关于时间复杂度: 1. 平方阶 (O(n2)) 排序各类简单排序:直接插入...

湖南小影
2017/05/18
0
0

没有更多内容

加载失败,请刷新页面

加载更多

Mac OS X下Maven的安装与配置

Mac OS X 安装Maven: 下载 Maven, 并解压到某个目录。例如/Users/robbie/apache-maven-3.3.3 打开Terminal,输入以下命令,设置Maven classpath $ vi ~/.bash_profile 添加下列两行代码,之后...

TonyStarkSir
今天
3
0
关于编程,你的练习是不是有效的?

最近由于工作及Solution项目的影响,我在重新学习DDD和领域建模的一些知识。然后,我突然就想到了这个问题,以及我是怎么做的? 对于我来说,提升技能的项目会有四种: 纯兴趣驱动的项目。即...

问题终结者
今天
3
0
打开eclipse出现an error has occurred see the log file

解决方法: 1,打开eclipse安装目录下的eclipse.ini文件; 2,打开的文本文件最后添加一行 --add-modules=ALL-SYSTEM 3,保存重新打开Eclipse。...

任梁荣
昨天
4
0
搞定Northwind示例数据库,无论哪个版本的SQLServer都受用

Northwind数据库 从这里可以找到突破口: http://social.msdn.microsoft.com/Forums/zh-CN/Vsexpressvb/thread/8490a1c6-9018-40c9-aafb-df9f79d29cde 下面是MSDN: http://msdn2.microsoft......

QQZZFT
昨天
1
0
mysql主从同步,安装配置操作

准备 两台mysql服务,我这里准备了如下: 主库:192.168.176.128 从库:192.168.176.131 如何在Linux上安装mysql服务,请看https://blog.csdn.net/qq_18860653/article/details/80250499 操作...

小致dad
昨天
5
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部