什么是归并排序?归并排序是利用递归与分治的技术将数据序列划分为越来越小的半子表,再对半子表排序,最后再用递归方法将排好序的半子表合并成越来越大的有序序列。核心思想将两个有序的数列合并成一个大的有序的序列。通过递归,层层合并,即为归并。(推荐
什么是归并排序?
归并排序是利用递归与分治的技术将数据序列划分为越来越小的半子表,再对半子表排序,最后再用递归方法将排好序的半子表合并成越来越大的有序序列。
核心思想
将两个有序的数列合并成一个大的有序的序列。通过递归,层层合并,即为归并。
实现代码:
import java.util.Arrays;
//归并排序,时间复杂度为O(N*logN),空间复杂度为O(N)
public class MergeSort {
public static void MergeSort(int[] arr, int start, int end) {
//分治的结束条件
if (start >= end) {
return;
}
//保证不溢出取start和end的中位数
int mid = start + ((end - start) >> 1);
//递归排序并且合并
MergeSort(arr, start, mid);
MergeSort(arr, mid + 1, end);
Merge(arr, start, mid, end);
}
//合并
public static void Merge(int[] arr, int start, int mid, int end) {
int[] temp = new int[end - start + 1];
int p1 = start;
int p2 = mid + 1;
int p = 0;
while (p1 <= mid && p2 <= end) {
if (arr[p1] > arr[p2]) {
temp[p++] = arr[p2++];
} else {
temp[p++] = arr[p1++];
}
}
while (p1 <= mid) {
temp[p++] = arr[p1++];
}
while (p2 <= end) {
temp[p++] = arr[p2++];
}
for (int i = 0; i < temp.length; i++) {
arr[i + start] = temp[i];
}
}
public static void main(String[] args) {
int[] a = {2, 4, 6, 1, 3, 7, 9, 8, 5};
MergeSort(a, 0, a.length - 1);
System.out.println(Arrays.toString(a));
}
}
运行结果:
相关视频教程推荐:java视频教程
--结束END--
本文标题: 如何利用java实现归并排序
本文链接: https://www.lsjlt.com/news/2351.html(转载时请注明来源链接)
有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341
下载Word文档到电脑,方便收藏和打印~
2024-04-01
2024-04-03
2024-04-03
2024-01-21
2024-01-21
2024-01-21
2024-01-21
2023-12-23
回答
回答
回答
回答
回答
回答
回答
回答
回答
回答
0