图解Java中归并排序算法的原理与实现

什么是归并排序

归并排序是一种经典的排序算法，它的基本思想是通过将待排序序列不停地划分成两个子序列，将每个子序列排序后再将其合并，直到最终合并为一个有序的序列。

归并排序的原理

划分过程

首先将待排序序列分为两个长度相等的子序列，然后对每个子序列进行排序。

合并过程

合并两个有序的子序列，生成一个有序的子序列。重复此过程，直到最终生成一个有序的完整序列。

归并排序的步骤

1. 划分序列

首先需要在待排序序列中找到一个中间位置，将序列分为左右两个子序列，然后递归地将左右两个子序列再进行划分操作。

2. 合并有序序列

将排序后的两个有序子序列合并为一个有序序列。

/**
 * 合并两个有序数组
 *
 * @param nums1 第一个有序数组
 * @param nums2 第二个有序数组
 * @return 合并后的有序数组
 */
public static int[] merge(int[] nums1, int[] nums2) {
    int[] result = new int[nums1.length + nums2.length];
    int i = 0, j = 0, k = 0;
    while (i < nums1.length && j < nums2.length) {
        if (nums1[i] <= nums2[j]) {
            result[k++] = nums1[i++];
        } else {
            result[k++] = nums2[j++];
        }
    }
    while (i < nums1.length) {
        result[k++] = nums1[i++];
    }
    while (j < nums2.length) {
        result[k++] = nums2[j++];
    }
    return result;
}

3. 递归合并

循环将两个子序列进行合并操作，合并后得到一个更大的有序序列，递归执行直到最终得到一个有序的完整序列。

/**
 * 归并排序算法
 *
 * @param nums 待排序数组
 * @return 排序后的数组
 */
public static int[] mergeSort(int[] nums) {
    if (nums.length <= 1) {
        return nums;
    }
    int mid = nums.length / 2;
    int[] left = Arrays.copyOfRange(nums, 0, mid);
    int[] right = Arrays.copyOfRange(nums, mid, nums.length);
    return merge(mergeSort(left), mergeSort(right));
}

示例说明

示例一：对 5, 2, 3, 1, 8, 4 进行归并排序

1. 初始状态：5, 2, 3, 1, 8, 4
2. 划分序列：5, 2, 3, 1, 8, 4
   / \
   5, 2, 3 1, 8, 4
   / \ / \
   5 2, 3 1, 8 4
   / \ / \
   2 3 1 8
3. 对每个子序列进行排序，得到两个有序子序列：
   左子序列：2, 3, 5
   右子序列：1, 4, 8
4. 合并左右两个有序子序列，得到完整排好序的序列：1, 2, 3, 4, 5, 8

示例二：对 9, 8, 7, 6, 5 进行归并排序

1. 初始状态：9, 8, 7, 6, 5
2. 划分序列：9, 8, 7, 6, 5
   / \
   9, 8, 7 6, 5
   / \ / \
   9, 8 7 6 5
   / \ / \ / \ / \
   9 8 7 0 6 5 0 0
3. 对每个子序列进行排序，得到两个有序子序列：
   左子序列：8, 9
   右子序列：5, 6
4. 合并左右两个有序子序列，得到完整排好序的序列：5, 6, 8, 9, 7