java实现归并排序算法
更新时间：2016年01月20日 10:50:47 投稿：hebedich
在学习算法的过程中，我们难免会接触很多和排序相关的算法。总而言之，对于任何编程人员来说，基本的排序算法是必须要掌握的。那么现在我们将要进行基本的归并排序算法的讲解
（福利推荐：【腾讯云】服务器最新限时优惠活动，云服务器1核2G仅99元/年、2核4G仅768元/3年，立即抢购>>>：9i0i.cn/qcloud）
（福利推荐：你还在原价购买阿里云服务器？现在阿里云0.8折限时抢购活动来啦！4核8G企业云服务器仅2998元/3年，立即抢购>>>：9i0i.cn/aliyun）
归并排序就是将未排序的数组进行对半划分成两个数组，划分后的数组只有原来数组的一半数量的元素。然后在对划分的两个数组再继续划分，循环此操作，直到划分的数组中只有一个元素时停止划分，然后对于划分完成的数组进行归并排序操作。将两个已经划分完成的数组合并成一个有序的数组，直到最后合并成一个包含所有元素的数组，合并排序操作完成。下面以图形来演示下归并排序的过程。
假设有一个未排序数组：｛3，2，4，1｝，下面为数组的划分过程，先将数组对半划分为｛3，2｝和｛4，1｝两个数组。然后在对这两个数组进行划分最后得到｛3｝，｛2｝，｛4｝，｛1｝四个数组，划分完成。
接下来对数组进行归并，先将｛3｝和｛2｝这两个数组合并成一个有序的数组｛2，3｝，同理对4，1进行相同的操作，得到｛1，4｝，然后在将合并好的这两个有序数组进行合并，最后合并成｛1，2，3，4｝，归并完成。
归并排序算法用java代码实现如下：
public static void MergeSort(int[] array,int head,int tail){
// 判断数组的头部索引是否小于尾部索引
if(head < tail){
int middle = (head+tail)/2;
MergeSort(array,head,middle);
MergeSort(array,middle+1,tail);
Merge(array,head,middle,tail);
}
}
public static void Merge(int[] array, int head, int middle, int tail) {
// TODO Auto-generated method stub
int[] temp = new int[tail - head + 1];
int a = head;
int b = middle + 1;
int i = 0;
// 对于两个数组中的数进行比较，将较小的值存放在临时数组中
while(a <= middle && b <=tail){
if(array[a] < array[b]){
temp[i++] = array[a++];
}
else{
temp[i++] = array[b++];
}
}
// 将未参与比较的数组中的数添加到临时数组中
while(a <= middle){
temp[i++] = array[a++];
}
while(b <= tail){
temp[i++] = array[b++];
}
// 将排好序的数组放回到array数组中
System.arraycopy(temp,0,array,head,tail - head + 1);
}
相关文章
这篇文章主要介绍了Java之springcloud Sentinel案例讲解,本篇文章通过简要的案例,讲解了该项技术的了解与使用,以下就是详细内容,需要的朋友可以参考下2021-08-08
这篇文章主要介绍了SpringCloud中的灰度路由使用详解,在微服务中,?通常为了高可用,?同一个服务往往采用集群方式部署,?即同时存在几个相同的服务,而灰度的核心就?是路由,?通过我们特定的策略去调用目标服务线路,需要的朋友可以参考下2023-08-08
这篇文章主要介绍了Mybatis的resultMap返回map问题，具有很好的参考价值，希望对大家有所帮助。如有错误或未考虑完全的地方，望不吝赐教2022-02-02
Java里的各种日志框架，相信大家都不陌生。Log4j/Log4j2/Logback/jboss logging等等，其实这些日志框架核心结构没什么区别，只是细节实现上和其性能上有所不同。本文带你从零开始，一步一步的设计一个日志框架2021-02-02
Java中使用print、printf、println的示例及区别
Java?的输出方式一般有这三种，print、println、printf，它们都是?java.long?包里的System类中的方法，本文重点给大家介绍Java中使用print、printf、println的示例,需要的朋友可以参考下2023-05-05
jpa多条件查询重写Specification的toPredicate方法
这篇文章主要介绍了多条件查询重写Specification的toPredicate方法，具有很好的参考价值，希望对大家有所帮助。如有错误或未考虑完全的地方，望不吝赐教2021-11-11
java获取本地ip，获取多网卡本地ip在项目中经常会用到，下面小编把代码分享到程序员之家平台，供大家参考2016-03-03
这篇文章主要为大家详细介绍了Java之String字符串，重新带大家认识String字符串，具有一定的参考价值，感兴趣的小伙伴们可以参考一下2017-07-07
mybatis?mapper.xml中如何根据数据库类型选择对应SQL语句
这篇文章主要介绍了mybatis?mapper.xml中如何根据数据库类型选择对应SQL语句，具有很好的参考价值，希望对大家有所帮助。如有错误或未考虑完全的地方，望不吝赐教2022-01-01
解决Spring boot整合mybatis,xml资源文件放置及路径配置问题
这篇文章主要介绍了解决Spring boot整合mybatis,xml资源文件放置及路径配置问题，具有很好的参考价值，希望对大家有所帮助。一起跟随小编过来看看吧2020-12-12
最新评论