算法设计 - 归并排序（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 + 1mid = (l + r) // 2i = lj = mid + 1tmp = [0] * nfor k in range(n):if i == mid + 1:tmp[k] = nums[j]j += 1elif j == r + 1:tmp[k] = nums[i]i += 1elif nums[i] <= nums[j]:tmp[k] = nums[i]i += 1else:tmp[k] = nums[j]j += 1for 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 + 1mid = (l + r) // 2i = l  # 左半部分有序子数组起始位置j = mid + 1  # 右半部分有序子数组起始位置tmp = [0] * n  # 临时数组for k in range(n):if i == mid + 1:tmp[k] = nums[j]j += 1elif j == r + 1:tmp[k] = nums[i]i += 1elif nums[i] <= nums[j]:tmp[k] = nums[i]i += 1else:tmp[k] = nums[j]j += 1for k in range(n):nums[l + k] = tmp[k]def mergeSort(nums, l, r):if l == r:  # 当划分到只有一个元素的子数组时，该子数组必然有序returnmid = (l + r) // 2mergeSort(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 << " ";}
}