我的Java开发学习之旅------>Java经典排序算法之归并排序

简介: 一、归并排序 归并排序是建立在归并操作上的一种有效的排序算法,该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。
一、归并排序
归并排序是建立在归并操作上的一种有效的排序算法,该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为二路归并
归并过程为:比较a[i]和a[j]的大小,若a[i]≤a[j],则将第一个有序表中的元素a[i]复制到r[k]中,并令i和k分别加上1;否则将第二个有序表中的元素a[j]复制到r[k]中,并令j和k分别加上1,如此循环下去,直到其中一个有序表取完,然后再将另一个有序表中剩余的元素复制到r中从下标k到下标t的单元。归并排序的算法我们通常用递归实现,先把待排序区间[s,t]以中点二分,接着把左边子区间排序,再把右边子区间排序,最后把左区间和右区间用一次归并操作合并成有序的区间[s,t]。
二、归并操作

三、两路归并算法
1、算法基本思路
     设两个有序的子文件(相当于输入堆)放在同一向量中相邻的位置上:R[low..m],R[m+1..high],先将它们合并到一个局部的暂存向量R1(相当于输出堆)中,待合并完成后将R1复制回R[low..high]中。

(1)合并过程
     合并过程中,设置i,j和p三个指针,其初值分别指向这三个记录区的起始位置。合并时依次比较R[i]和R[j]的关键字,取关键字较小的记录复制到R1[p]中,然后将被复制记录的指针i或j加1,以及指向复制位置的指针p加1。
     重复这一过程直至两个输入的子文件有一个已全部复制完毕(不妨称其为空),此时将另一非空的子文件中剩余记录依次复制到R1中即可。

(2)动态申请R1
     实现时,R1是动态申请的,因为申请的空间可能很大,故须加入申请空间是否成功的处理。


 2、归并算法
 
 void Merge(SeqList R,int low,int m,int high)
    {//将两个有序的子文件R[low..m)和R[m+1..high]归并成一个有序的
     //子文件R[low..high]
     int i=low,j=m+1,p=0; //置初始值
     RecType *R1; //R1是局部向量,若p定义为此类型指针速度更快
     R1=(ReeType *)malloc((high-low+1)*sizeof(RecType));
     if(! R1) //申请空间失败
       Error("Insufficient memory available!");
     while(i<=m&&j<=high) //两子文件非空时取其小者输出到R1[p]上
       R1[p++]=(R[i].key<=R[j].key)?R[i++]:R[j++];
     while(i<=m) //若第1个子文件非空,则复制剩余记录到R1中
       R1[p++]=R[i++];
     while(j<=high) //若第2个子文件非空,则复制剩余记录到R1中
       R1[p++]=R[j++];
     for(p=0,i=low;i<=high;p++,i++)
       R[i]=R1[p];//归并完成后将结果复制回R[low..high]
    } //Merge


四、归并排序
归并排序有两种实现方法:自底向上和自顶向下。下面说说 自顶向下的方法     
(1)分治法的三个步骤
     设归并排序的当前区间是R[low..high],分治法的三个步骤是:
①分解:将当前区间一分为二,即求分裂点         
②求解:递归地对两个子区间R[low..mid]和R[mid+1..high]进行归并排序;
③组合:将已排序的两个子区间R[low..mid]和R[mid+1..high]归并为一个有序的区间R[low..high]。
  递归的终结条件:子区间长度为1(一个记录自然有序)。


 (2)具体算法
    
void MergeSortDC(SeqList R,int low,int high)
     {//用分治法对R[low..high]进行二路归并排序
       int mid;
       if(low<high){//区间长度大于1
          mid=(low+high)/2; //分解
          MergeSortDC(R,low,mid); //递归地对R[low..mid]排序
          MergeSortDC(R,mid+1,high); //递归地对R[mid+1..high]排序
          Merge(R,low,mid,high); //组合,将两个有序区归并为一个有序区
        }
     }//MergeSortDC

 (3)算法MergeSortDC的执行过程
     算法MergeSortDC的执行过程如下图所示的递归树。


五、算法分析


1、稳定性
      归并排序是一种稳定的排序。

2、存储结构要求
     可用顺序存储结构。也易于在链表上实现。

3、时间复杂度
     对长度为n的文件,需进行 趟二路归并,每趟归并的时间为O(n),故其时间复杂度无论是在最好情况下还是在最坏情况下均是O(nlgn)。

4、空间复杂度
     需要一个辅助向量来暂存两有序子文件归并的结果,故其辅助空间复杂度为O(n),显然它不是就地排序。
  注意:
     若用单链表做存储结构,很容易给出就地的归并排序。

5、比较操作的次数介于(nlogn) / 2和nlogn - n + 1。

6、赋值操作的次数是(2nlogn)。归并算法的空间复杂度为:0 (n)

7、归并排序比较占用内存,但却是一种效率高且稳定的算法。

六、代码实现
public class MergeSortTest {

	public static void main(String[] args) {
		int[] data = new int[] { 2, 4, 7, 5, 8, 1, 3, 6 };
		System.out.print("初始化:\t");
		print(data);
		System.out.println("");
	
		mergeSort(data, 0, data.length - 1);
		
		System.out.print("\n排序后:  \t");
		print(data);
	}

	public static void mergeSort(int[] data, int left, int right) {
		if (left >= right)
			return;
		//两路归并
		// 找出中间索引
		int center = (left + right) / 2;
		// 对左边数组进行递归
		mergeSort(data, left, center);
		// 对右边数组进行递归
		mergeSort(data, center + 1, right);
		// 合并
		merge(data, left, center, center + 1, right);
		System.out.print("排序中:\t");
		print(data);
	}

	/**
	 * 将两个数组进行归并,归并前面2个数组已有序,归并后依然有序
	 * 
	 * @param data
	 *            数组对象
	 * @param leftStart
	 *            左数组的第一个元素的索引
	 * @param leftEnd
	 *            左数组的最后一个元素的索引
	 * @param rightStart
	 *            右数组第一个元素的索引
	 * @param rightEnd
	 *            右数组最后一个元素的索引
	 */
	public static void merge(int[] data, int leftStart, int leftEnd,
			int rightStart, int rightEnd) {
		int i = leftStart;
		int j = rightStart;
		int k = 0;
		// 临时数组
		int[] temp = new int[rightEnd - leftStart + 1]; //创建一个临时的数组来存放临时排序的数组 
		// 确认分割后的两段数组是否都取到了最后一个元素
		while (i <= leftEnd && j <= rightEnd) {
			// 从两个数组中取出最小的放入临时数组
			if (data[i] > data[j]) {
				temp[k++] = data[j++];
			} else {
				temp[k++] = data[i++];
			}
		}
		// 剩余部分依次放入临时数组(实际上两个while只会执行其中一个)
		while (i <= leftEnd) {
			temp[k++] = data[i++];
		}
		while (j <= rightEnd) {
			temp[k++] = data[j++];
		}
		k = leftStart;
		// 将临时数组中的内容拷贝回原数组中 // (原left-right范围的内容被复制回原数组)
		for (int element : temp) {
			data[k++] = element;
		}
	}

	public static void print(int[] data) {
		for (int i = 0; i < data.length; i++) {
			System.out.print(data[i] + "\t");
		}
		System.out.println();
	}
}

七、运行结果

初始化:	2	4	7	5	8	1	3	6	

排序中:	2	4	7	5	8	1	3	6	
排序中:	2	4	5	7	8	1	3	6	
排序中:	2	4	5	7	8	1	3	6	
排序中:	2	4	5	7	1	8	3	6	
排序中:	2	4	5	7	1	8	3	6	
排序中:	2	4	5	7	1	3	6	8	
排序中:	1	2	3	4	5	6	7	8	

排序后:  	1	2	3	4	5	6	7	8	

==================================================================================================

  作者:欧阳鹏  欢迎转载,与人分享是进步的源泉!

  转载请保留原文地址http://blog.csdn.net/ouyang_peng

==================================================================================================



相关文章
|
2月前
|
监控 算法 网络协议
Java 实现局域网电脑屏幕监控算法揭秘
在数字化办公环境中,局域网电脑屏幕监控至关重要。本文介绍用Java实现这一功能的算法,涵盖图像采集、数据传输和监控端显示三个关键环节。通过Java的AWT/Swing库和Robot类抓取屏幕图像,使用Socket进行TCP/IP通信传输图像数据,并利用ImageIO类在监控端展示图像。整个过程确保高效、实时和准确,为提升数字化管理提供了技术基础。
83 15
|
8天前
|
存储 算法 Java
解锁“分享文件”高效密码:探秘 Java 二叉搜索树算法
在信息爆炸的时代,文件分享至关重要。二叉搜索树(BST)以其高效的查找性能,为文件分享优化提供了新路径。本文聚焦Java环境下BST的应用,介绍其基础结构、实现示例及进阶优化。BST通过有序节点快速定位文件,结合自平衡树、多线程和权限管理,大幅提升文件分享效率与安全性。代码示例展示了文件插入与查找的基本操作,适用于大规模并发场景,确保分享过程流畅高效。掌握BST算法,助力文件分享创新发展。
|
30天前
|
负载均衡 算法
架构学习:7种负载均衡算法策略
四层负载均衡包括数据链路层、网络层和应用层负载均衡。数据链路层通过修改MAC地址转发帧;网络层通过改变IP地址实现数据包转发;应用层有多种策略,如轮循、权重轮循、随机、权重随机、一致性哈希、响应速度和最少连接数均衡,确保请求合理分配到服务器,提升性能与稳定性。
213 11
架构学习:7种负载均衡算法策略
|
21天前
|
存储 人工智能 算法
解锁分布式文件分享的 Java 一致性哈希算法密码
在数字化时代,文件分享成为信息传播与协同办公的关键环节。本文深入探讨基于Java的一致性哈希算法,该算法通过引入虚拟节点和环形哈希空间,解决了传统哈希算法在分布式存储中的“哈希雪崩”问题,确保文件分配稳定高效。文章还展示了Java实现代码,并展望了其在未来文件分享技术中的应用前景,如结合AI优化节点布局和区块链增强数据安全。
|
22天前
|
算法 安全 Java
Java线程调度揭秘:从算法到策略,让你面试稳赢!
在社招面试中,关于线程调度和同步的相关问题常常让人感到棘手。今天,我们将深入解析Java中的线程调度算法、调度策略,探讨线程调度器、时间分片的工作原理,并带你了解常见的线程同步方法。让我们一起破解这些面试难题,提升你的Java并发编程技能!
62 16
|
1月前
|
运维 监控 算法
企业局域网监控软件中 Java 优先队列算法的核心优势
企业局域网监控软件是数字化时代企业网络安全与高效运营的基石,犹如一位洞察秋毫的卫士。通过Java实现的优先队列算法,它能依据事件优先级排序,确保关键网络事件如异常流量、数据泄露等被优先处理,保障系统稳定与安全。代码示例展示了如何定义网络事件类并使用PriorityQueue处理高优先级事件,尤其在面对疑似风险时迅速启动应急措施。这一核心技术助力企业在复杂网络环境中稳健前行,护航业务腾飞。
65 32
|
22天前
|
Java 调度 开发者
Java线程池ExecutorService学习和使用
通过学习和使用Java中的 `ExecutorService`,可以显著提升并发编程的效率和代码的可维护性。合理配置线程池参数,结合实际应用场景,可以实现高效、可靠的并发处理。希望本文提供的示例和思路能够帮助开发者深入理解并应用 `ExecutorService`,实现更高效的并发程序。
32 10
|
28天前
|
存储 监控 算法
剖析基于Java算法驱动的智能局域网管控之道
本文探讨了基于Java语言的局域网控制方案,结合链表数据结构与令牌桶算法,解决设备管理和流量调度难题。通过链表灵活存储网络设备信息,实现高效设备管理;令牌桶算法则精准控制流量,确保网络平稳运行。二者相辅相成,为校园、企业等局域网提供稳固高效的控制体系,保障业务连续性和数据安全。
|
25天前
|
算法 搜索推荐 Java
【潜意识Java】深度解析黑马项目《苍穹外卖》与蓝桥杯算法的结合问题
本文探讨了如何将算法学习与实际项目相结合,以提升编程竞赛中的解题能力。通过《苍穹外卖》项目,介绍了订单配送路径规划(基于动态规划解决旅行商问题)和商品推荐系统(基于贪心算法)。这些实例不仅展示了算法在实际业务中的应用,还帮助读者更好地准备蓝桥杯等编程竞赛。结合具体代码实现和解析,文章详细说明了如何运用算法优化项目功能,提高解决问题的能力。
55 6
|
25天前
|
算法 Java C++
【潜意识Java】蓝桥杯算法有关的动态规划求解背包问题
本文介绍了经典的0/1背包问题及其动态规划解法。
45 5

热门文章

最新文章