数据结构-归并排序笔记

【数据结构】八大排序(超详解+附动图+源码)_数据结构排序-CSDN博客

看这个学思路

一归并排序介绍:

归并排序(MERGE-SORT)是利用归并的思想实现的排序方法，该算法采用经典的分治(divide-and-conquer)策略(分治法将问题分(divide)成一些小的问题然后递归求解，而治(conquer)的阶段则将分的阶段得到的各答案"修补"在一起，即分而治之)。

二实现思路

分解（Divide）：
- 将待排序的序列分割成若干个子序列，这些子序列可以是顺序的，也可以是随机的。
- 分解的标准通常是按照序列的中间位置或者某个特定的划分点来划分序列。
解决（Conquer）：
- 递归地对每个子序列进行排序。
- 递归的基本情况是当子序列足够小，可以直接排序或者已经有序，不需要进一步分解。
合并（Combine）：
- 将排序好的子序列合并成一个有序的完整序列。
- 合并操作的复杂度通常取决于具体的算法，例如归并排序中的合并操作需要将两个有序序列合并成一个有序序列。

三代码实现

public class Main {

    public static void main(String[] args) {
        int[] arr = {11, 44, 23, 67, 88, 65, 34, 48, 9, 12}; // 待排序数组
        int[] tmp = new int[arr.length]; // 新建一个临时数组，用于在归并过程中存放元素
        
        mergeSort(arr, 0, arr.length - 1, tmp); // 调用归并排序方法，传入数组、起始索引、结束索引和临时数组

        // 输出排序后的数组
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
    }

    // 归并排序方法，采用递归实现
    private static void mergeSort(int[] arr, int left, int right, int[] tmp) {
        if (left < right) { // 如果左索引小于右索引，说明当前区间内有多个元素，需要排序
            int mid = (left + right) / 2; // 计算中间索引，将当前区间分为两半

            // 对左边序列进行归并排序
            mergeSort(arr, left, mid, tmp);
            // 对右边序列进行归并排序
            mergeSort(arr, mid + 1, right, tmp);

            // 合并两个有序序列
            merge(arr, left, mid, right, tmp);
        }
    }

    // 归并方法，用于合并两个有序序列
    private static void merge(int[] arr, int left, int mid, int right, int[] temp) {
        int tempBeginIndex = 0; // 临时数组的起始索引
        int i = left; // 左边序列的起始索引
        int j = mid + 1; // 右边序列的起始索引

        // 合并两个有序序列到临时数组temp中
        while (i <= mid && j <= right) { // 当左右序列都还有元素时
            if (arr[i] <= arr[j]) { // 如果左边序列的元素小于等于右边序列的元素
                temp[tempBeginIndex++] = arr[i++]; // 将左边序列的元素加入临时数组，并移动索引
            } else {
                temp[tempBeginIndex++] = arr[j++]; // 将右边序列的元素加入临时数组，并移动索引
            }
        }

        // 拷贝左边序列剩余的元素到temp
        while (i <= mid) {
            temp[tempBeginIndex++] = arr[i++];
        }

        // 拷贝右边序列剩余的元素到temp
        while (j <= right) {
            temp[tempBeginIndex++] = arr[j++];
        }

        // 将temp中的元素拷贝回原数组arr，完成合并
        for (int k = 0; k < tempBeginIndex; k++) {
            arr[left + k] = temp[k];
        }
    }
}