合并法排序（Merge Sort）是一种基于分治思想的排序算法，其原理如下：
1.将待排序数组分成两个子数组，每个子数组包含大约相等数量的元素。
2.递归地对子数组进行排序，直到每个子数组的大小为1。
3.将已排序的子数组合并成一个新的排序数组，合并过程中按照从小到大的顺序逐个比较两个子数组中的元素，并将较小的元素放入新数组中，直到所有元素都被放入新数组中。
4.最终得到一个有序数组。
合并排序的时间复杂度是O(nlogn)，其中n是待排序数组的长度。它的空间复杂度是O(n)。由于它采用了递归的思想，所以其实现过程相对简单，且不受数据类型限制，可以适用于各种类型的数据排序。
一、C 实现合并法排序及代码详解
合并排序（Merge Sort）是一种稳定、时间复杂度为 O(nlogn) 的排序算法。
其基本思想是将待排序的序列分成若干个子序列，每个子序列都是有序的，然后再将这些有序的子序列合并成一个有序的序列。
具体实现分为两个步骤：
分割（Divide）：将待排序的序列从中间分成两部分，递归地对左半部分和右半部分分别进行归并排序，直到序列中只有一个元素。
合并（Merge）：将两个有序子序列合并成一个有序序列，称之为归并。
下面是 C 语言实现合并排序的完整代码及详细分析：
#include <stdio.h>
void Merge(int arr[], int left, int mid, int right) {
int i, j, k;
int n1 = mid - left + 1;
int n2 = right - mid;
// 创建临时数组
int L[n1], R[n2];
// 将数据拷贝到临时数组 L 和 R
for (i = 0; i < n1; i++) L[i] = arr[left + i];
for (j = 0; j < n2; j++) R[j] = arr[mid + 1 + j];
i = 0; // 左侧数组的索引
j = 0; // 右侧数组的索引
k = left; // 合并数组的索引
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k] = L[i];
i++;
}
else {
arr[k] = R[j];
j++;
}
k++;
}
// 将剩余的元素拷贝到合并数组中
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}
while (j < n2) {
arr[k] = R[j];
j++;
k++;
}
}
void MergeSort(int arr[], int left, int right) {
if (left < right) {
int mid = (left + right) / 2;
// 递归地将两个子数组排序
MergeSort(arr, left, mid);
MergeSort(arr, mid + 1, right);
// 合并已排序的两个子数组
Merge(arr, left, mid, right);
}
}
int main() {
int arr[] = { 10, 7, 8, 9, 1, 5 };
int n = sizeof(arr) / sizeof(arr[0]);
MergeSort(arr, 0, n - 1);
// 输出已排序的数组
for (int i = 0; i < n; i++) printf("%d ", arr[i]);
return 0;
}
函数 Merge() 实现了两个有序子序列的归并，它接受四个参数：
- arr[]：需要合并的目标数组。
- left：左侧子数组的起始索引。
- mid：左侧子数组的结束索引。
- right：右侧子数组的结束索引。
首先，我们计算出左右两个子数组的长度 n1 和 n2，并创建两个临时数组 L 和 R，用于存放子数组的数据。
接着，将原数组中左侧子数组的元素拷贝到临时数组 L 中，右侧子数组的元素拷贝到临时数组 R 中。
接下来按照归并排序算法的基本思想，对左右两个临时数组中的元素进行比较，并将较小的元素拷贝到原数组 arr 中。当其中一个临时数组中的元素全部被拷贝到原数组 arr 中时，将另一个未被拷贝的临时数组中剩余的元素直接拷贝到原数组 arr 中即可。
最后，函数 MergeSort() 是递归排序函数的实现，它接受三个参数：
- arr[]：需要排序的目标数组。
- left：子数组的起始索引。
- right：子数组的结束索引。
该函数首先检查条件 left < right，如果满足条件，则计算中间索引 mid，并将数组分成左右两部分。接着，递归调用 MergeSort() 函数，对左右两个子数组进行排序，并最终调用函数 Merge() 将已排序的左右子数组合并成一个有序数组。
最后，我们在主函数中测试 MergeSort() 函数是否正常工作，输出排序结果。
以上即为 C 语言实现合并排序的完整代码及详细分析。
二、C++ 实现合并法排序及代码详解
合并排序（Merge Sort）是一种基于分治算法的排序算法。它将待排序的序列分成若干个子序列，每个子序列都是有序的，然后再将子序列归并起来，使整个序列有序。下面给出 C++ 实现合并排序的代码及详解。
#include <iostream>
using namespace std;
void merge(int arr[], int l, int m, int r) { // 合并两个子序列
int left_size = m - l + 1;
int right_size = r - m;
int left[left_size], right[right_size];
for (int i = 0; i < left_size; i++) {
left[i] = arr[l + i];
}
for (int i = 0; i < right_size; i++) {
right[i] = arr[m + 1 + i];
}
int i = 0, j = 0, k = l;
while (i < left_size && j < right_size) {
if (left[i] <= right[j]) {
arr[k] = left[i];
i++;
} else {
arr[k] = right[j];
j++;
}
k++;
}
while (i < left_size) {
arr[k] = left[i];
i++;
k++;
}
while (j < right_size) {
arr[k] = right[j];
j++;
k++;
}
}
void merge_sort(int arr[], int l, int r) { // 排序主函数
if (l >= r) {
return;
}
int m = l + (r - l) / 2; // 中间位置
merge_sort(arr, l, m); // 左半部分排序
merge_sort(arr, m + 1, r); // 右半部分排序
merge(arr, l, m, r); // 合并两个已排序的子序列
}
int main() {
int arr[] = { 38, 27, 43, 3, 9, 82, 10 };
int n = sizeof(arr) / sizeof(arr[0]);
merge_sort(arr, 0, n - 1);
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
cout << endl;
return 0;
}
首先，我们定义了一个 merge 函数，用于合并两个有序的子序列。该函数接受一个整型数组 arr、两个整数 l 和 r，分别表示两个子序列的起点和终点。该函数的实现原理如下：
- 先计算两个子序列的长度，然后创建两个数组
left和right分别存储这两个子序列的元素。 - 对于左右两个子序列，使用两个
for循环将其元素复制到left和right数组中。 - 创建三个指针
i、j和k，分别指向left、right和arr数组中的位置。 - 在
while循环中，比较left和right数组中的元素，将较小的元素复制到arr数组中。 - 如果其中一个子序列已经全部复制到了
arr数组中，则将另外一个子序列的剩余元素复制到arr数组中。
接着，我们定义了一个 merge_sort 函数，用于对整个序列进行排序。该函数接受一个整型数组 arr，两个整数 l 和 r，分别代表序列的起点和终点。该函数的实现原理如下：
- 如果
l >= r，则说明序列只有一个元素或没有元素，直接返回。 - 计算序列的中间位置
m。 - 递归地对左半部分序列和右半部分序列进行排序。
- 调用
merge函数，将已排序的左半部分序列和右半部分序列合并起来。
最后，我们在 main 函数中创建一个整型数组 arr，并调用 merge_sort 函数对其进行排序。最后，我们输出排序后的结果。
三、Java 实现合并法排序及代码详解
合并排序（Merge Sort）是一种分而治之的排序算法，它将数组分成两个子数组，递归地排序子数组，然后将这两个已排序的子数组合并以得到最终的排序结果。它是一种稳定的排序算法，时间复杂度为 O(nlogn)。
下面是 Java 实现合并排序的代码，包括合并以及递归排序两个方法：
public class MergeSort {
/**
* 合并两个已排序的数组
*
* @param arr 待合并的数组
* @param l 左子数组的起始下标
* @param m 左子数组的结束下标
* @param r 右子数组的结束下标
*/
private static void merge(int[] arr, int l, int m, int r) {
// 计算左右子数组的长度
int n1 = m - l + 1;
int n2 = r - m;
// 创建两个临时数组
int[] L = new int[n1];
int[] R = new int[n2];
// 拷贝数据到临时数组中
for (int i = 0; i < n1; i++) {
L[i] = arr[l + i];
}
for (int j = 0; j < n2; j++) {
R[j] = arr[m + 1 + j];
}
// 合并临时数组
int i = 0, j = 0, k = l;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k] = L[i];
i++;
} else {
arr[k] = R[j];
j++;
}
k++;
}
// 将剩余的元素拷贝到数组中
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}
while (j < n2) {
arr[k] = R[j];
j++;
k++;
}
}
/**
* 合并排序算法的实现
*
* @param arr 待排序的数组
* @param l 左下标
* @param r 右下标
*/
public static void mergeSort(int[] arr, int l, int r) {
if (l < r) {
int m = (l + r) / 2;
mergeSort(arr, l, m);
mergeSort(arr, m + 1, r);
merge(arr, l, m, r);
}
}
public static void main(String[] args) {
int[] arr = {8, 4, 5, 7, 1, 3, 6, 2};
mergeSort(arr, 0, arr.length - 1);
System.out.println(Arrays.toString(arr)); // [1, 2, 3, 4, 5, 6, 7, 8]
}
}
在 merge() 方法中，我们首先计算左右子数组的长度，然后创建两个临时数组来存储左右子数组的元素。接着，我们分别将左右子数组的元素拷贝到临时数组中，并进行比较和合并操作，最后将剩余的元素拷贝到数组中。
在 mergeSort() 方法中，我们判断数组的左下标是否小于右下标。如果是，我们就计算中间下标，并递归地对左右子数组进行排序，最后合并这两个已排序的子数组。
在 main() 方法中，我们定义一个测试数组，然后调用 mergeSort() 方法进行排序，并打印输出结果。
这就是 Java 实现合并排序的代码和详解。
