文档章节

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

haoran_10
 haoran_10
发布于 2016/07/15 16:39
字数 859
阅读 4
收藏 0
点赞 0
评论 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
8个常用算法的超常剖析

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

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

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

小数点
2017/12/04
0
0
排序算法总结(一)---- 直接插入排序,希尔排序(java实现)

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

ljheee
2017/04/08
0
0
算法系列【希尔排序】篇

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

湖南小影
2017/05/18
0
0
算法系列【希尔排序】篇

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

湖南小影
2017/05/18
0
0
算法系列【希尔排序】篇

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

湖南小影
2017/05/18
0
0
算法系列【希尔排序】篇

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

湖南小影
2017/05/18
0
0
算法系列【希尔排序】篇

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

湖南小影
2017/05/18
0
0
java排序之快速排序、归并排序、基数排序

前两篇说了Java排序中的冒泡、选择、插入、希尔等排序算法,今天就探讨一下剩下的三种常用排序。 快速排序: 当要求时间最快时,就可以用快速排序算法。 选择第一个数为p,小于p的数放在左边...

野小疯
06/05
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

NNS域名系统之域名竞拍

0x00 前言 其实在官方文档中已经对域名竞拍的过程有详细的描述,感兴趣的可以移步http://doc.neons.name/zh_CN/latest/nns_protocol.html#id30 此处查阅。 我这里主要对轻钱包开发中会用到的...

暖冰
今天
0
0
32.filter表案例 nat表应用 (iptables)

10.15 iptables filter表案例 10.16/10.17/10.18 iptables nat表应用 10.15 iptables filter表案例: ~1. 写一个具体的iptables小案例,需求是把80端口、22端口、21 端口放行。但是,22端口我...

王鑫linux
今天
0
0
shell中的函数&shell中的数组&告警系统需求分析

20.16/20.17 shell中的函数 20.18 shell中的数组 20.19 告警系统需求分析

影夜Linux
今天
0
0
Linux网络基础、Linux防火墙

Linux网络基础 ip addr 命令 :查看网口信息 ifconfig命令:查看网口信息,要比ip addr更明了一些 centos 7默认没安装ifconfig命令,可以使用yum install -y net-tools命令来安装。 ifconfig...

李超小牛子
今天
1
0
[机器学习]回归--Decision Tree Regression

CART决策树又称分类回归树,当数据集的因变量为连续性数值时,该树算法就是一个回归树,可以用叶节点观察的均值作为预测值;当数据集的因变量为离散型数值时,该树算法就是一个分类树,可以很...

wangxuwei
昨天
1
0
Redis做分布式无锁CAS的问题

因为Redis本身是单线程的,具备原子性,所以可以用来做分布式无锁的操作,但会有一点小问题。 public interface OrderService { public String getOrderNo();} public class OrderRe...

算法之名
昨天
10
0
143. Reorder List - LeetCode

Question 143. Reorder List Solution 题目大意:给一个链表,将这个列表分成前后两部分,后半部分反转,再将这两分链表的节点交替连接成一个新的链表 思路 :先将链表分成前后两部分,将后部...

yysue
昨天
1
0
数据结构与算法1

第一个代码,描述一个被称为BankAccount的类,该类模拟了银行中的账户操作。程序建立了一个开户金额,显示金额,存款,取款并显示余额。 主要的知识点联系为类的含义,构造函数,公有和私有。...

沉迷于编程的小菜菜
昨天
1
0
从为什么别的队伍总比你的快说起

在机场候检排队的时候,大多数情况下,别的队伍都要比自己所在的队伍快,并常常懊悔当初怎么没去那个队。 其实,最快的队伍只能有一个,而排队之前并不知道那个队快。所以,如果有六个队伍你...

我是菜鸟我骄傲
昨天
1
0
分布式事务常见的解决方案

随着互联网的发展,越来越多的多服务相互之间的调用,这时候就产生了一个问题,在单项目情况下很容易实现的事务控制(通过数据库的acid控制),变得不那么容易。 这时候就产生了多种方案: ...

小海bug
昨天
3
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部