归并排序的原理及java代码实现
作者:hebedich 时间:2021-11-18 13:51:10
概述
归并(Merge)排序法是将两个(或两个以上)有序表合并成一个新的有序表,即把待排序序列分为若干个子序列,每个子序列是有序的。然后再把有序子序列合并为整体有序序列。
归并排序采用的是递归来实现,属于“分而治之”,将目标数组从中间一分为二,之后分别对这两个数组进行排序,排序完毕之后再将排好序的两个数组“归并”到一起,归并排序最重要的也就是这个“归并”的过程,归并的过程中需要额外的跟需要归并的两个数组长度一致的空间。
效果图:
步骤
申请空间,使其大小为两个已经排序序列之和,该空间用来存放合并后的序列
设定两个指针,最初位置分别为两个已经排序序列的起始位置
比较两个指针所指向的元素,选择相对小的元素放入到合并空间,并移动指针到下一位置
重复步骤3直到某一指针达到序列尾
将另一序列剩下的所有元素直接复制到合并序列尾
实例
原始数据:
3 5 2 6 2
归并的前提是将数组分开,一分为二,再一分为二,分到不能再分,进行归并。
第一轮分隔,索引2 ((0+4)/2=2) 为中间
[3 5 2] [6 2]
第二轮分隔,对[3 5 2]进行分隔
[3 5] [2] [6 2]
第三轮分隔,对[3 5]进行分隔
[3] [5] [2] [6 2]
合并[3] [5]
[3 5] [2] [6 2]
合并[3 5] [2]
[2 3 5] [6 2]
第四轮分隔,对[6 2]进行分隔
[2 3 5] [6] [2]
合并[6] [2]
[2 3 5] [2 6]
合并[2 3 5] [2 6]
[2 2 3 5 6]
代码实现(Java)
package com.coder4j.main.arithmetic.sorting;
public class Merge {
private static int mark = 0;
/**
* 归并排序
*
* @param array
* @param low
* @param high
* @return
*/
private static int[] sort(int[] array, int low, int high) {
int mid = (low + high) / 2;
if (low < high) {
mark++;
System.out.println("正在进行第" + mark + "次分隔,得到");
System.out.println("[" + low + "-" + mid + "] [" + (mid + 1) + "-" + high + "]");
// 左边数组
sort(array, low, mid);
// 右边数组
sort(array, mid + 1, high);
// 左右归并
merge(array, low, mid, high);
}
return array;
}
/**
* 对数组进行归并
*
* @param array
* @param low
* @param mid
* @param high
*/
private static void merge(int[] array, int low, int mid, int high) {
System.out.println("合并:[" + low + "-" + mid + "] 和 [" + (mid + 1) + "-" + high + "]");
int[] temp = new int[high - low + 1];
int i = low;// 左指针
int j = mid + 1;// 右指针
int k = 0;
// 把较小的数先移到新数组中
while (i <= mid && j <= high) {
if (array[i] < array[j]) {
temp[k++] = array[i++];
} else {
temp[k++] = array[j++];
}
}
// 两个数组之一可能存在剩余的元素
// 把左边剩余的数移入数组
while (i <= mid) {
temp[k++] = array[i++];
}
// 把右边边剩余的数移入数组
while (j <= high) {
temp[k++] = array[j++];
}
// 把新数组中的数覆盖array数组
for (int m = 0; m < temp.length; m++) {
array[m + low] = temp[m];
}
}
/**
* 归并排序
*
* @param array
* @return
*/
public static int[] sort(int[] array) {
return sort(array, 0, array.length - 1);
}
public static void main(String[] args) {
int[] array = { 3, 5, 2, 6, 2 };
int[] sorted = sort(array);
System.out.println("最终结果");
for (int i : sorted) {
System.out.print(i + " ");
}
}
}
测试输出结果:
正在进行第1次分隔,得到
[0-2] [3-4]
正在进行第2次分隔,得到
[0-1] [2-2]
正在进行第3次分隔,得到
[0-0] [1-1]
合并:[0-0] 和 [1-1]
合并:[0-1] 和 [2-2]
正在进行第4次分隔,得到
[3-3] [4-4]
合并:[3-3] 和 [4-4]
合并:[0-2] 和 [3-4]
最终结果
2 2 3 5 6
经测试,与实例中结果一致。
标签:java归并排序
0
投稿
猜你喜欢
Java 使用IO流实现大文件的分割与合并实例详解
2023-08-23 09:33:33
Java中接收键盘输入的三种方法
2023-11-13 16:11:29
Java递归实现斐波那契数列
2022-05-03 19:00:11
深入解析Java中的Classloader的运行机制
2023-07-16 11:47:59
java实现简单登录界面的实战过程
2022-02-07 20:19:51
如何在springboot中实现页面的国际化
2021-08-13 03:33:07
浅谈springboot的三种启动方式
2022-07-31 10:57:47
深入讲解Java Maven配置
2022-07-01 05:09:21
Spring运行时动态注册bean的方法
2023-11-25 04:16:58
IDEA 2020.1 搜索不到Chinese (Simplified) Language Pack EAP,无法安装的问题
2023-11-10 23:54:01
Spring Boot教程之提高开发效率必备工具lombok
2021-08-23 11:12:43
java面试题——详解HashMap和Hashtable 的区别
2023-08-06 16:38:25
JDK源码之Vector与HashSet解析
2021-09-06 10:47:23
SpringMVC请求流程源码解析
2021-08-07 03:35:11
详解SpringBoot项目整合Vue做一个完整的用户注册功能
2022-02-13 21:46:35
Hadoop1.2中配置伪分布式的实例
2023-01-26 12:20:56
IDEA中设置代码自动提示为Alt+/的具体做法
2022-07-06 14:58:32
详细了解JAVA NIO之Buffer(缓冲区)
2022-08-18 00:59:28
SpringBoot 在项目启动之后执行自定义方法的两种方式小结
2021-05-25 15:46:36
Spring @Conditional通过条件控制bean注册过程
2023-08-06 10:00:11