java实现归并排序算法
作者:hebedich 时间:2023-02-09 07:34:01
归并排序算法思想:
分而治之(divide - conquer);每个递归过程涉及三个步骤
第一, 分解: 把待排序的 n 个元素的序列分解成两个子序列, 每个子序列包括 n/2 个元素.
第二, 治理: 对每个子序列分别调用归并排序MergeSort, 进行递归操作
第三, 合并: 合并两个排好序的子序列,生成排序结果.
public static void mergeSort(int[] a, int[] tmp, int left, int right) {
if (left < right) {
int mid = left + (right - left) / 2;
mergeSort(a, tmp, left, mid);// 左排序
mergeSort(a, tmp, mid + 1, right);// 右排序
merge(a, tmp, left, mid + 1, right);// 左右合并
}
}
public static void merge(int[] a, int[] tmp, int left, int rightPos,
int right) {
int leftEnd = rightPos - 1;
int tmpPos = left;
int num = right - left + 1;
while (left <= leftEnd && rightPos <= right) {
if (a[left] < a[rightPos]) {
tmp[tmpPos++] = a[left++];
} else {
tmp[tmpPos++] = a[rightPos++];
}
}
while (left <= leftEnd) {
tmp[tmpPos++] = a[left++];
}
while (rightPos <= right) {
tmp[tmpPos++] = a[rightPos++];
}
for (int i = 0; i < num; i++, right--) {
a[right] = tmp[right];
}
}
归并算法示意图:
以上所述就是本文的全部内容了,希望大家能够喜欢。
标签:java,归并排序,算法
![](/images/zang.png)
![](/images/jiucuo.png)
猜你喜欢
Java实现TCP/IP协议的收发数据(服务端)代码实例
2023-08-11 08:44:51
![](https://img.aspxhome.com/file/2023/3/58063_0s.jpg)
Java取整与四舍五入
2021-07-25 01:07:32
Android开发简易音乐播放器
2023-12-26 01:07:03
![](https://img.aspxhome.com/file/2023/9/86749_0s.jpg)
浅谈java的接口和C++虚类的相同和不同之处
2023-08-05 12:01:51
android使用PullToRefresh实现下拉刷新和上拉加载
2023-08-06 11:06:58
![](https://img.aspxhome.com/file/2023/5/85455_0s.png)
Intellij IDEA 配置Subversion插件实现步骤详解
2023-11-03 10:09:04
![](https://img.aspxhome.com/file/2023/6/76606_0s.jpg)
java @Value(
2023-10-05 02:54:47
![](https://img.aspxhome.com/file/2023/7/63017_0s.png)
Android MaterialAlertDialogBuilder修改按钮属性
2021-12-20 06:56:19
![](https://img.aspxhome.com/file/2023/8/105988_0s.png)
Java抽象类和抽象方法定义与用法实例详解
2023-10-02 14:30:13
Java——对象初始化顺序使用详解
2023-11-01 01:08:46
Java 深入浅出掌握Collection单列集合Set
2023-10-07 18:49:32
![](https://img.aspxhome.com/file/2023/5/58545_0s.gif)
Spring MVC结合Spring Data JPA实现按条件查询和分页
2023-03-04 07:24:36
![](https://img.aspxhome.com/file/2023/6/89596_0s.jpg)
Java 并发编程之ThreadLocal详解及实例
2023-09-05 13:48:02
![](https://img.aspxhome.com/file/2023/4/119114_0s.png)
详解feign调用session丢失解决方案
2021-08-29 20:38:20
![](https://img.aspxhome.com/file/2023/1/82001_0s.png)
C#中异步和多线程的区别介绍
2021-08-23 07:06:49
利用Android封装一个有趣的Loading组件
2023-01-07 16:25:28
![](https://img.aspxhome.com/file/2023/9/98659_0s.png)
java中断线程的正确姿势完整示例
2023-01-27 06:33:58
![](https://img.aspxhome.com/file/2023/8/67648_0s.jpg)
Java 判断字符为中文实例代码(超管用)
2021-08-24 13:18:31
jdk动态代理源码分析过程
2023-03-01 05:05:59
![](https://img.aspxhome.com/file/2023/7/68157_0s.png)
RocketMQ事务消息保证消息的可靠性和一致性
2022-09-05 00:25:26