算法设计 - 归并排序（Java & JS & Python & C & C++）

合并两个有序的子数组

在讨论归并排序之前，我们需要先讨论一个小问题：

如果存在一个数组 nums，它的前半部分和后半部分都是一个有序子数组，但是nums本身不是有序的，比如 nums = [1, 3, 5, 7, 9, 2, 4, 6, 8]，我们该如何将这个数组变的有序呢？

其实这个问题就是下面这道题的变种：

LeetCode - 88 合并两个有序数组（Java & JS & Python & C & C++）-CSDN博客https://fcqian.blog.csdn.net/article/details/141188181?spm=1001.2014.3001.5502因此，参考上面题目，本问题解法如下：

Java源码实现

import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        int[] nums = {1, 3, 5, 7, 9, 2, 4, 6, 8};

        mergeTwoOrderedArray(nums, 0, nums.length - 1);

        System.out.println(Arrays.toString(nums));
    }

    public static void mergeTwoOrderedArray(int[] nums, int l, int r) {
        int n = r - l + 1;
        int mid = (l + r) / 2;

        int i = l; // 左半部分有序子数组起始位置
        int j = mid + 1; // 右半部分有序子数组起始位置

        int[] tmp = new int[n]; // 临时数组

        for (int k = 0; k < n; k++) {
            if (i == mid + 1) {
                tmp[k] = nums[j++];
            } else if (j == r + 1) {
                tmp[k] = nums[i++];
            } else if (nums[i] <= nums[j]) {
                tmp[k] = nums[i++];
            } else {
                tmp[k] = nums[j++];
            }
        }

        System.arraycopy(tmp, 0, nums, l, n);
    }
}

JavaScript源码

function mergeTwoOrderedArray(nums, l, r) {
  const n = r - l + 1;
  const mid = (l + r) >> 1;

  let i = l;
  let j = mid + 1;

  const tmp = new Array(n);

  for (let k = 0; k < n; k++) {
    if (i == mid + 1) {
      tmp[k] = nums[j++];
    } else if (j == r + 1) {
      tmp[k] = nums[i++];
    } else if (nums[i] <= nums[j]) {
      tmp[k] = nums[i++];
    } else {
      tmp[k] = nums[j++];
    }
  }

  for (let k = 0; k < n; k++) {
    nums[l + k] = tmp[k];
  }
}

// 测试
const nums = [1, 3, 5, 7, 9, 2, 4, 6, 8];

mergeTwoOrderedArray(nums, 0, nums.length - 1);
console.log(nums);

Python源码

def mergeTwoOrderedArray(nums, l, r):
    n = r - l + 1
    mid = (l + r) // 2

    i = l
    j = mid + 1

    tmp = [0] * n

    for k in range(n):
        if i == mid + 1:
            tmp[k] = nums[j]
            j += 1
        elif j == r + 1:
            tmp[k] = nums[i]
            i += 1
        elif nums[i] <= nums[j]:
            tmp[k] = nums[i]
            i += 1
        else:
            tmp[k] = nums[j]
            j += 1

    for k in range(n):
        nums[l + k] = tmp[k]


if __name__ == '__main__':
    nums = [1, 3, 5, 7, 9, 2, 4, 6, 8]

    mergeTwoOrderedArray(nums, 0, len(nums) - 1)
    print(nums)

C源码

#include <stdio.h>

void mergeTwoOrderedArray(int nums[], int l, int r) {
    int n = r - l + 1;
    int mid = (l + r) / 2;

    int i = l;
    int j = mid + 1;

    int tmp[n];

    for (int k = 0; k < n; k++) {
        if (i == mid + 1) {
            tmp[k] = nums[j++];
        } else if (j == r + 1) {
            tmp[k] = nums[i++];
        } else if (nums[i] <= nums[j]) {
            tmp[k] = nums[i++];
        } else {
            tmp[k] = nums[j++];
        }
    }

    for (int k = 0; k < n; k++) {
        nums[l + k] = tmp[k];
    }
}

int main() {
    int nums[] = {1, 3, 5, 7, 9, 2, 4, 6, 8};
    int nums_size = 9;

    mergeTwoOrderedArray(nums, 0, nums_size - 1);

    for (int i = 0; i < 9; i++) {
        printf("%d ", nums[i]);
    }
}

C++源码

#include <bits/stdc++.h>

using namespace std;

void mergeTwoOrderedArray(vector<int> &nums, int l, int r) {
    int n = r - l + 1;
    int mid = (l + r) / 2;

    int i = l;
    int j = mid + 1;

    int tmp[n];

    for (int k = 0; k < n; k++) {
        if (i == mid + 1) {
            tmp[k] = nums[j++];
        } else if (j == r + 1) {
            tmp[k] = nums[i++];
        } else if (nums[i] <= nums[j]) {
            tmp[k] = nums[i++];
        } else {
            tmp[k] = nums[j++];
        }
    }

    for (int k = 0; k < n; k++) {
        nums[l + k] = tmp[k];
    }
}

int main() {
    vector<int> nums{1, 3, 5, 7, 9, 2, 4, 6, 8};

    mergeTwoOrderedArray(nums, 0, nums.size() - 1);
    for (const auto &num: nums) {
        cout << num << " ";
    }
}

归并排序的分治思想

归并排序，是基于分治思想实现的。

比如 nums = [7, 4, 6, 2, 3, 8, 1, 9, 5] 是一个乱序数组，那么我们可以使用分治思想将其划分为两部分，比如：

• L = 0；
• R = nums.length - 1；
• mid = (L+R)/2

那么可以将nums数组分为 [L, mid] 和 [mid + 1, R] 这两部分。

如果，[L, mid] 和 [mid + 1, R] 都是有序的，那么我们可以基于上一小节讨论的：合并两个有序子数组，求解出一个有序的大数组。

如果， [L, mid] 和 [mid + 1, R] 是无序的，则我们继续分治，比如将[L, mid]当成一个新数组，采用相同的策略，划分为两部分。

按此策略有图示如下：

从上图我们可以发现：

当分治到子数组长度为1时，即只有一个元素时，此时可以百分百确定对应的子数组是有序的。

比如 [7, 4] 分解为 [7] 和 [4]，此时[7]是有序的，[4]也是有序的。

我们按照 “合并两个有序子数组” 的策略来合并[7]，[4]，即可得到一个有序数组[4, 7]，然后覆盖到原数组中。

此时 [4, 7] 和 [6] 各自有序，我们按照 “合并两个有序子数组” 的策略来合并

按此逻辑我们依次回溯其他分支。

归并排序的代码实现

分治策略一般就是基于递归来实现的

Java源码

import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        int[] nums = {7, 4, 6, 2, 3, 8, 1, 9, 5};

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

    public static void mergeSort(int[] nums, int l, int r) {
        if (l == r) return; // 当划分到只有一个元素的子数组时，该子数组必然有序

        int mid = (l + r) / 2;

        mergeSort(nums, l, mid); // 归并排序左半部分
        mergeSort(nums, mid + 1, r); // 归并排序右半部分

        mergeTwoOrderedArray(nums, l, r); // 合并两个有序子数组，得到一个有序大数组
    }

    public static void mergeTwoOrderedArray(int[] nums, int l, int r) {
        int n = r - l + 1;
        int mid = (l + r) / 2;

        int i = l; // 左半部分有序子数组起始位置
        int j = mid + 1; // 右半部分有序子数组起始位置

        int[] tmp = new int[n]; // 临时数组

        for (int k = 0; k < n; k++) {
            if (i == mid + 1) {
                tmp[k] = nums[j++];
            } else if (j == r + 1) {
                tmp[k] = nums[i++];
            } else if (nums[i] <= nums[j]) {
                tmp[k] = nums[i++];
            } else {
                tmp[k] = nums[j++];
            }
        }

        System.arraycopy(tmp, 0, nums, l, n);
    }
}

JavaScript源码

function mergeSort(nums, l, r) {
  if (l == r) return; // 当划分到只有一个元素的子数组时，该子数组必然有序

  const mid = (l + r) >> 1;

  mergeSort(nums, l, mid); // 归并排序左半部分
  mergeSort(nums, mid + 1, r); // 归并排序右半部分

  mergeTwoOrderedArray(nums, l, r); // 合并两个有序子数组，得到一个有序大数组
}

function mergeTwoOrderedArray(nums, l, r) {
  const n = r - l + 1;
  const mid = (l + r) >> 1;

  let i = l; // 左半部分有序子数组起始位置
  let j = mid + 1; // 右半部分有序子数组起始位置

  const tmp = new Array(n); // 临时数组

  for (let k = 0; k < n; k++) {
    if (i == mid + 1) {
      tmp[k] = nums[j++];
    } else if (j == r + 1) {
      tmp[k] = nums[i++];
    } else if (nums[i] <= nums[j]) {
      tmp[k] = nums[i++];
    } else {
      tmp[k] = nums[j++];
    }
  }

  for (let k = 0; k < n; k++) {
    nums[l + k] = tmp[k];
  }
}

// 测试
const nums = [7, 4, 6, 2, 3, 8, 1, 9, 5];
mergeSort(nums, 0, nums.length - 1);
console.log(nums);

Python源码

def mergeTwoOrderedArray(nums, l, r):
    n = r - l + 1
    mid = (l + r) // 2

    i = l  # 左半部分有序子数组起始位置
    j = mid + 1  # 右半部分有序子数组起始位置

    tmp = [0] * n  # 临时数组

    for k in range(n):
        if i == mid + 1:
            tmp[k] = nums[j]
            j += 1
        elif j == r + 1:
            tmp[k] = nums[i]
            i += 1
        elif nums[i] <= nums[j]:
            tmp[k] = nums[i]
            i += 1
        else:
            tmp[k] = nums[j]
            j += 1

    for k in range(n):
        nums[l + k] = tmp[k]


def mergeSort(nums, l, r):
    if l == r:  # 当划分到只有一个元素的子数组时，该子数组必然有序
        return

    mid = (l + r) // 2

    mergeSort(nums, l, mid)  # 归并排序左半部分
    mergeSort(nums, mid + 1, r)  # 归并排序右半部分

    mergeTwoOrderedArray(nums, l, r)  # 合并两个有序子数组，得到一个有序大数组


if __name__ == '__main__':
    nums = [7, 4, 6, 2, 3, 8, 1, 9, 5]

    mergeSort(nums, 0, len(nums) - 1)
    print(nums)

C源码

#include <stdio.h>

void mergeTwoOrderedArray(int nums[], int l, int r) {
    int n = r - l + 1;
    int mid = (l + r) / 2;

    int i = l; // 左半部分有序子数组起始位置
    int j = mid + 1; // 右半部分有序子数组起始位置

    int tmp[n]; // 临时数组

    for (int k = 0; k < n; k++) {
        if (i == mid + 1) {
            tmp[k] = nums[j++];
        } else if (j == r + 1) {
            tmp[k] = nums[i++];
        } else if (nums[i] <= nums[j]) {
            tmp[k] = nums[i++];
        } else {
            tmp[k] = nums[j++];
        }
    }

    for (int k = 0; k < n; k++) {
        nums[l + k] = tmp[k];
    }
}

void mergeSort(int nums[], int l, int r) {
    if (l == r) return; // 当划分到只有一个元素的子数组时，该子数组必然有序

    int mid = (l + r) / 2;

    mergeSort(nums, l, mid); // 归并排序左半部分
    mergeSort(nums, mid + 1, r);  // 归并排序右半部分

    mergeTwoOrderedArray(nums, l, r);  // 合并两个有序子数组，得到一个有序大数组
}

int main() {
    int nums[] = {7, 4, 6, 2, 3, 8, 1, 9, 5};
    int nums_size = 9;

    mergeSort(nums, 0, nums_size - 1);

    for (int i = 0; i < 9; i++) {
        printf("%d ", nums[i]);
    }
}

C++源码

#include <bits/stdc++.h>

using namespace std;

void mergeTwoOrderedArray(vector<int> &nums, int l, int r) {
    int n = r - l + 1;
    int mid = (l + r) / 2;

    int i = l;  // 左半部分有序子数组起始位置
    int j = mid + 1; // 右半部分有序子数组起始位置

    int tmp[n]; // 临时数组

    for (int k = 0; k < n; k++) {
        if (i == mid + 1) {
            tmp[k] = nums[j++];
        } else if (j == r + 1) {
            tmp[k] = nums[i++];
        } else if (nums[i] <= nums[j]) {
            tmp[k] = nums[i++];
        } else {
            tmp[k] = nums[j++];
        }
    }

    for (int k = 0; k < n; k++) {
        nums[l + k] = tmp[k];
    }
}

void mergeSort(vector<int> &nums, int l, int r) {
    if (l == r) return; // 当划分到只有一个元素的子数组时，该子数组必然有序

    int mid = (l + r) / 2;

    mergeSort(nums, l, mid); // 归并排序左半部分
    mergeSort(nums, mid + 1, r); // 归并排序右半部分

    mergeTwoOrderedArray(nums, l, r); // 合并两个有序子数组，得到一个有序大数组
}

int main() {
    vector<int> nums{7, 4, 6, 2, 3, 8, 1, 9, 5};

    mergeSort(nums, 0, nums.size() - 1);
    for (const auto &num: nums) {
        cout << num << " ";
    }
}