归并排序
归并排序（Merge Sort）是一种经典的排序算法，采用分治策略来对数组进行排序。它的基本思想是将数组分成两半，分别对每一半进行排序，然后再将两个有序的子数组合并成一个整体有序的数组。归并排序具有稳定的排序性质，并且在最坏情况下都能保证
基本思想
归并排序可以分为两个主要步骤：
- 分解：将数组分成越来越小的子数组，直到每个子数组只有一个元素。
- 合并：将这些子数组合并回一个大的数组，同时保证合并后的数组是有序的。
归并排序的步骤
- 递归分解：如果数组长度大于1，则将数组分为两半，递归地对这两半分别进行归并排序。
- 合并：将两个已排序的子数组合并成一个有序数组。
代码实现
递归版本
查看代码
java
public class MergeSort {
// 合并两个子数组的辅助方法
private static void merge(int[] arr, int left, int mid, int right) {
int n1 = mid - left + 1;
int n2 = right - mid;
// 创建临时数组
int[] L = new int[n1];
int[] R = new int[n2];
// 复制数据到临时数组 L[] 和 R[]
for (int i = 0; i < n1; ++i)
L[i] = arr[left + i];
for (int j = 0; j < n2; ++j)
R[j] = arr[mid + 1 + j];
// 合并临时数组回到 arr[l..r]
int i = 0, j = 0;
int k = left;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k] = L[i];
i++;
} else {
arr[k] = R[j];
j++;
}
k++;
}
// 复制 L[] 的剩余元素
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}
// 复制 R[] 的剩余元素
while (j < n2) {
arr[k] = R[j];
j++;
k++;
}
}
// 主要的归并排序方法
public static void sort(int[] arr, int left, int right) {
if (left < right) {
// 找到中间点
int mid = (left + right) / 2;
// 对左右两半分别进行归并排序
sort(arr, left, mid);
sort(arr, mid + 1, right);
// 合并两个子数组
merge(arr, left, mid, right);
}
}
// 打印数组的方法
public static void printArray(int[] arr) {
for (int value : arr) {
System.out.print(value + " ");
}
System.out.println();
}
public static void main(String[] args) {
int[] arr = {12, 11, 13, 5, 6, 7};
System.out.println("原始数组:");
printArray(arr);
sort(arr, 0, arr.length - 1);
System.out.println("排序后的数组:");
printArray(arr);
}
}代码解释
- merge 方法：此方法用于合并两个已排序的子数组。它首先复制两个子数组到临时数组
L和R中，然后比较这两个数组中的元素，将较小的元素放入原数组中，直到其中一个数组的元素全部放入原数组。最后将另一个数组中剩余的元素也放入原数组。 - sort 方法：此方法是归并排序的主要递归函数。它首先检查数组的左右边界，如果左边界小于右边界，则继续递归地对数组进行分割。递归的基线条件是当
left >= right时，即数组只剩下一个元素时，不再需要排序。 - main 方法：测试归并排序的主程序入口。
迭代版本
迭代版本的归并排序通过逐步增加子数组的大小来合并相邻的子数组。开始时，将数组划分为大小为1的子数组（每个元素自己就是一个子数组），然后逐步合并相邻的子数组，直到整个数组变得有序。
查看代码
java
public class IterativeMergeSort {
// 合并两个子数组的辅助方法
private static void merge(int[] arr, int left, int mid, int right) {
int n1 = mid - left + 1;
int n2 = right - mid;
// 创建临时数组
int[] L = new int[n1];
int[] R = new int[n2];
// 复制数据到临时数组 L[] 和 R[]
System.arraycopy(arr, left, L, 0, n1);
System.arraycopy(arr, mid + 1, R, 0, n2);
// 合并临时数组回到 arr[l..r]
int i = 0, j = 0;
int k = left;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k] = L[i];
i++;
} else {
arr[k] = R[j];
j++;
}
k++;
}
// 复制 L[] 的剩余元素
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}
// 复制 R[] 的剩余元素
while (j < n2) {
arr[k] = R[j];
j++;
k++;
}
}
// 主要的迭代归并排序方法
public static void sort(int[] arr) {
int n = arr.length;
// 逐步增加子数组的大小
for (int currentSize = 1; currentSize <= n - 1; currentSize = 2 * currentSize) {
for (int leftStart = 0; leftStart < n - 1; leftStart += 2 * currentSize) {
int mid = Math.min(leftStart + currentSize - 1, n - 1);
int rightEnd = Math.min(leftStart + 2 * currentSize - 1, n - 1);
merge(arr, leftStart, mid, rightEnd);
}
}
}
// 打印数组的方法
public static void printArray(int[] arr) {
for (int value : arr) {
System.out.print(value + " ");
}
System.out.println();
}
public static void main(String[] args) {
int[] arr = {12, 11, 13, 5, 6, 7};
System.out.println("原始数组:");
printArray(arr);
sort(arr);
System.out.println("排序后的数组:");
printArray(arr);
}
}代码解释
- merge 方法：这个方法与递归版本中的
merge方法相同，用于合并两个已排序的子数组。 - sort 方法：这是迭代版本的核心方法。它通过逐步增加子数组的大小来合并子数组。具体步骤如下：
- 初始化
currentSize为 1，表示最开始每个子数组的大小。 - 在每一轮循环中，将
currentSize增加一倍，直到currentSize大于等于数组长度。 - 内部循环用于处理每个子数组的合并。它首先确定左侧子数组的起始位置
leftStart，然后计算出中间位置mid和右侧子数组的结束位置rightEnd。 - 调用
merge方法来合并这些子数组。
- 初始化
时间复杂度
归并排序的时间复杂度为
空间复杂度
归并排序的空间复杂度为