14-归并排序算法

归并排序算法

public class MergeSort {
    public static void sort(int[] nums) {
        int[] temp = new int[nums.length];
        mergeSort(nums, temp, 0, nums.length - 1);
    }

    private static void mergeSort(int[] nums, int[] temp, int left, int right) {
        if (left >= right) {
            return;
        }

        int mid = left + (right - left) / 2;
        mergeSort(nums, temp, left, mid);
        mergeSort(nums, temp, mid + 1, right);
        merge(nums, temp, left, mid, right);
    }

    private static void merge(int[] nums, int[] temp, int left, int mid, int right) {
        // 将左右两个有序子数组归并成一个有序子数组
        int i = left, j = mid + 1, k = 0;
        while (i <= mid && j <= right) {
            if (nums[i] <= nums[j]) {
                temp[k++] = nums[i++];
            } else {
                temp[k++] = nums[j++];
            }
        }
        while (i <= mid) {
            temp[k++] = nums[i++];
        }
        while (j <= right) {
            temp[k++] = nums[j++];
        }

        // 将临时数组中的元素复制回原数组
        for (i = 0; i < k; i++) {
            nums[left + i] = temp[i];
        }
    }
}

采用了递归方式来实现归并排序算法。具体而言，我们将待排序数组划分为两个子数组，并对每个子数组进行排序。然后，将排序后的两个子数组归并成一个有序数组。

在实现过程中，我们还需要定义一个临时数组 temp，用于临时存储归并操作的结果。具体步骤如下：

1. 在 mergeSort() 方法中，首先检查当前子数组的大小是否小于 2，如果是，则直接返回；
2. 然后计算出子数组的中间位置 mid，并递归地调用 mergeSort() 方法来分别对左右两个子数组进行排序；
3. 最后调用 merge() 方法，将排序后的左右两个子数组归并成一个有序子数组。
4. 在 merge() 方法中，我们使用三个指针 i、j 和 k 来遍历左右两个子数组和临时数组。比较 nums[i] 和 nums[j] 的大小，将较小的值存入 temp[k] 中，同时将相应的指针向前移动一位。当其中一个指针到达了子数组的末尾时，我们将另一个子数组中剩余的元素全部复制到临时数组中。最后，将临时数组中的元素复制回原数组。

验证：

import cn.hutool.core.util.ArrayUtil;

public class Test {
    public static void main(String[] args) {
        int[] nums = {4, 2, 5, 7, 1, 3, 6};
        MergeSort.sort(nums);
        System.out.println(ArrayUtil.toString(nums));  //[1, 2, 3, 4, 5, 6, 7]
    }
}