深刻理解归并排序
2023-12-28 06:34:42
「归并排序」核心就是每个数组「两两比较」并合并,直至只剩下一个数组。
我们通过图片的方式,来排序一个数组为例:
这里有六个数字,我们第一步先将一个数组视为一组,并对相邻的两组进行「两两比较」。可以得到如下:
再进行两两比较,如下:
最后进行一次两两比较结束,如下:
附上 Java 代码:
public class MyMegerSort {
// 归并排序
public int[] sortArray(int[] nums) {
int length = nums.length;
// src 代表将要排序的数组,dst 表示将排序结果暂存的数组
int[] src = nums;
int[] dst = new int[length];
// base 代表一个单位的数组的大小,并且每次增大一倍
// * 「归并排序」核心就是每个数组「两两比较」并合并,直至只剩下一个数组
// base 的大小是已排序好的数组大小
for (int base = 1; base < length; base += base) {
for (int start = 0; start < length; start += base * 2) {
int mid = Math.min(start + base, length);
int end = Math.min(start + base * 2, length);
// index1、index2 分别代表着将要对比的两个数组的头节点。分别为左数组头节点和右数组头节点
// k 用于表示 dst 的下标,含义为排序到的下标位置
int index1 = start, index2 = mid, k = start;
// 归并排序核心代码。遍历这两个排好序的数组,每次将一个最小的节点插入 dst 数组
while (index1 < mid || index2 < end) {
if (index2 == end || (index1 < mid && src[index1] < src[index2])) {
dst[k++] = src[index1++];
} else {
dst[k++] = src[index2++];
}
}
}
// 交换两个数组 或 为 dst 数组开辟新的数组空间
int[] temp = src;
src = dst;
dst = temp;
}
return src;
}
}
最后附上图片来源:「数据结构——三分钟搞定归并排序」
文章来源:https://blog.csdn.net/sora_2021/article/details/135251190
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!