归并排序（Merge Sort）是一种典型的分治算法，它将一个大问题分解成多个小问题，逐步解决，再合并结果，最终得到排序后的序列。
归并排序的思路：
- 分解（Divide）：将待排序的数组分成两半，递归地对这两半分别进行归并排序。
- 解决（Conquer）：对分解出的子数组继续进行排序，直到每个子数组只有一个元素（因为一个元素自然是有序的）。
- 合并（Combine）：将排序后的子数组合并成一个有序的大数组。合并是归并排序的核心步骤。
归并排序的时间复杂度与空间复杂度：
- 时间复杂度：
- 归并排序的时间复杂度是 O(nlogn)，无论是最坏情况、最佳情况还是平均情况。这里的 n 是待排序元素的数量，logn 是因为每次递归将数组分成两半，直到数组大小为1。
- 每一层递归的合并操作是线性时间复杂度O(n)，递归深度是logn，所以总的时间复杂度是 O(nlogn)。
- 空间复杂度：
- 归并排序需要额外的空间来存储合并过程中的中间结果，空间复杂度为O(n)。
- 在递归调用过程中，每次递归调用栈的深度是logn，但归并过程中需要额外的存储空间来存储中间的合并结果，所以总空间复杂度是O(n)。
归并排序的Java实现：
public class MergeSort {
// 归并排序函数
public static void mergeSort(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
// 调用辅助函数进行递归排序
mergeSortHelper(arr, 0, arr.length - 1);
}
// 递归的归并排序方法
private static void mergeSortHelper(int[] arr, int left, int right) {
if (left < right) {
int mid = left + (right - left) / 2; // 防止溢出
mergeSortHelper(arr, left, mid); // 排序左半部分
mergeSortHelper(arr, mid + 1, right); // 排序右半部分
merge(arr, left, mid, right); // 合并两部分
}
}
// 合并两个有序子数组
private static void merge(int[] arr, int left, int mid, int right) {
// 创建临时数组存储合并结果
int[] temp = new int[right - left + 1];
int i = left, j = mid + 1, k = 0;
// 合并两个有序子数组
while (i <= mid && j <= right) {
if (arr[i] <= arr[j]) {
temp[k++] = arr[i++];
} else {
temp[k++] = arr[j++];
}
}
// 如果左半部分有剩余元素，直接复制到temp数组
while (i <= mid) {
temp[k++] = arr[i++];
}
// 如果右半部分有剩余元素，直接复制到temp数组
while (j <= right) {
temp[k++] = arr[j++];
}
// 将临时数组的内容拷贝回原数组
System.arraycopy(temp, 0, arr, left, temp.length);
}
// 测试归并排序
public static void main(String[] args) {
int[] arr = {38, 27, 43, 3, 9, 82, 10};
System.out.println("排序前: ");
printArray(arr);
mergeSort(arr);
System.out.println("排序后: ");
printArray(arr);
}
// 打印数组
public static void printArray(int[] arr) {
for (int num : arr) {
System.out.print(num + " ");
}
System.out.println();
}
}
代码解析：
mergeSort 函数：是外部调用的接口，接收待排序的数组。首先检查数组的有效性（如果为空或长度小于2直接返回）。mergeSortHelper 函数：是递归的核心部分，负责将数组分成两部分，分别递归排序，直到分割到只有一个元素为止。merge 函数：这是合并的关键部分，它接受三个参数：left, mid, right，分别表示左部分的起始索引，右部分的结束索引。合并操作会创建一个临时数组，按顺序将两个已排序的子数组合并到这个临时数组中，然后再将其复制回原数组。printArray 函数：打印数组元素的辅助函数。
测试：
给定输入数组 {38, 27, 43, 3, 9, 82, 10}，归并排序后的输出应为：
排序前: 38 27 43 3 9 82 10
排序后: 3 9 10 27 38 43 82