排序算法-归并排序-详解

核心思想

归并排序实质是利用分治思想，先拆分，再合并。

拆分：将待排序数组从中间切分，并对切分后的子数组做同样的切分操作，直到子数组中只有一个元素为止，只有一个元素的数组一定是有序的。也就是说切分之后做到了局部有序。

合并：对两个局部有序的数组进行合并操作，使合并结果也是有序的。

合并过程涉及到三个循环不变量：

k：表示原数组中将要赋值的位置，边界为闭区间：所有参与比较的元素的最左边索引到最右边索引。

i：表示第一个数中要参与比较的元素的位置，边界为第一个数组的第一个元素到第一个数组的最后一个元素，如果i超出边界，对第二个数组中的元素进行一一复制即可。

j：表示第二个数组中要参与比较的元素的位置，边界为第二个数组的第一个元素到第二个数组的最后一个元素，如果j超出边界，对第一个数组中的元素一一赋值即可。

理解归并排序前，建议先理解合并两个有序数组的操作。

代码实现

package com.zw6688.al.sort;

import java.util.Arrays;

/**
 * @Author:
 * @Description: 归并排序
 * @Date: 2021/4/21 20:21
 */
public class MergeSort {

    public static void main(String[] args) {

        int[] nums = {6, 5, 2, 3, 8, 7, 9, 1};

        MergeSort mergeSort = new MergeSort();
        mergeSort.split(nums, 0, nums.length - 1);
        System.out.println(Arrays.toString(nums));
    }


    public void split(int[] nums, int left, int right) {
        if (left == right) {
            return;
        }
        int mid = left + (right - left) / 2;
        split(nums, left, mid);
        split(nums, mid + 1, right);

        merge(nums, left, mid, right);

    }


    public void merge(int[] nums, int left, int mid, int right) {
        int[] temp = new int[right - left + 1];
        for (int i = 0; i < right - left + 1; i++) {
            temp[i] = nums[left + i];
        }
//        int k = left;                 //表示要赋值的位置
        int i = 0;                      //左半部分的将要比较的元素
        int j = mid - left + 1;         //右半部分将要比较的元素

        for (int k = left; k <= right; k++) {
            if (i >= mid -left + 1) {
                nums[k] = temp[j];
                j++;
            } else if (j >= right - left + 1) {
                nums[k] = temp[i];
                i++;
            } else if (temp[i] > temp[j]) {
                nums[k] = temp[j];
                j++;
            } else {
                nums[k] = temp[i];
                i++;
            }
        }


    }


}