1. 思想

将数组分割成一个一个有序的子数组,然后将子数组两两合并起来,形成一个新的有序数组

2. 算法

  1. 先写一个函数用于分割数组,直到数组不可再分
  2. 然后开始回溯合并子数组
  3. 合并时先将左子数组和右子数组分别保存出来
  4. 然后遍历整个左子数组和右子数组,判断四种情况:

    1. 左子数组遍历完,右子数组未遍历完
    2. 右子数组遍历完,左子数组未遍历完
    3. 左子数组头元素小于右子数组头元素,就将左子数组头元素放入外部数组
    4. 右子数组头元素小于等于左子数组头元素,就将右子数组头元素放入外部数组

3. 代码

参考视频:

private static void mergeSort(int[] array, int left, int right) {
    // 递归跳出条件
    if (left >= right) {
        return;
    }
    
    int middle = (left + right) >> 1;
    mergeSort(array, left, middle);
    mergeSort(array, middle + 1, right);
    merge(array, left, middle, right);
}

private static void merge(int[] array, int l, int m, int r) {
    
    int[] leftArray = new int[m - l + 1];
    int[] rightArray = new int[r - m];
    int leftHead = l;
    int rightHead = m + 1;
    
    // 填充左子数组
    for (int i = leftHead; i <= m; i++) {
        leftArray[i - leftHead] = array[i];
    }

    // 填充右子数组
    for (int i = rightHead; i <= r; i++) {
        rightArray[i - rightHead] = array[i];
    }

    // 注意要先判断子数组是否遍历完的情况
    for (int i = l; i <= r; i++) {
        // 左子数组遍历完,右子数组未遍历完
        if (leftHead > m && rightHead <= r) {
            array[i] = rightArray[rightHead - m - 1];
            rightHead++;
        // 右子数组遍历完,左子数组未遍历完
        } else if (rightHead > r && leftHead <= m) {
            array[i] = leftArray[leftHead - l];
            leftHead++;
        // 左子数组的头元素小于右子数组的头元素
        } else if (leftArray[leftHead - l] < rightArray[rightHead - m - 1]) {
            array[i] = leftArray[leftHead - l];
            leftHead++;
        // 右子数组的头元素小于左子数组的头元素
        } else if (rightArray[rightHead - m - 1] <= leftArray[leftHead - l]) {
            array[i] = rightArray[rightHead - m - 1];
            rightHead++;
        }
    }
}

未命名绘图-第 3 页

image-20200831154230489

Last modification:March 16th, 2021 at 09:25 am