深刻理解归并排序

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
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。