归并排序
所用方法和基本原理
归并排序是一种基于分治思想的排序算法。其基本原理如下：
- 分解：将一个长度为 (n) 的数组不断地二分，直到每个子数组只包含一个元素（因为单个元素的数组天然是有序的）。例如，对于长度为 (n) 的数组，先找到中间位置 (mid)，将数组分为左半部分 ([l, mid]) 和右半部分 ([mid + 1, r])。
- 解决：递归地对左右两个子数组进行归并排序，使得左右子数组各自有序。
- 合并：将两个已经有序的子数组合并成一个有序的数组。通过比较两个子数组的当前元素，将较小的元素依次放入一个临时数组，最后将临时数组的内容复制回原数组对应的位置。
代码及注释
public class MergeSort {
// 归并排序主函数，对数组arr的[l, r]区间进行排序
public static void mergeSort(int[] arr, int l, int r) {
// 如果l等于r，说明只有一个元素，已经有序，直接返回
if (l == r) return;
// 计算中间位置mid
int mid = l + (r - l >> 1);
// 递归对左半部分数组进行归并排序
mergeSort(arr, l, mid);
// 递归对右半部分数组进行归并排序
mergeSort(arr, mid + 1, r);
// 计算当前需要合并的数组长度
int len = r - l + 1;
// 创建一个临时数组temp，用于存储合并过程中的数据
int[] temp = new int[len];
// 左半部分数组的起始索引
int i = l;
// 右半部分数组的起始索引
int j = mid + 1;
// 临时数组的索引
int k = 0;
// 比较左右两个子数组的元素，将较小的元素放入临时数组
while (i <= mid && j <= r) {
if (arr[i] <= arr[j]) {
temp[k++] = arr[i++];
} else {
temp[k++] = arr[j++];
}
}
// 将左半部分数组剩余的元素放入临时数组
while (i <= mid) {
temp[k++] = arr[i++];
}
// 将右半部分数组剩余的元素放入临时数组
while (j <= r) {
temp[k++] = arr[j++];
}
// 将临时数组中的元素复制回原数组对应的位置
for (int t = 0; t < len; t++) {
arr[l + t] = temp[t];
}
}
}
举例说明
假设有数组 arr = [38, 27, 43, 3, 9, 82, 10]。
- 分解阶段：
- 初始数组长度为 7，
l = 0，r = 6，计算mid = 0 + (6 - 0 >> 1) = 3。 - 递归对左半部分
[38, 27, 43, 3]进行排序，再次二分，mid = 0 + (3 - 0 >> 1) = 1，继续递归直到每个子数组只有一个元素。 - 同样对右半部分
[9, 82, 10]进行类似的二分操作。
- 初始数组长度为 7，
- 合并阶段：
- 以最底层的合并为例，假设要合并
[3]和[27]，比较3和27，将3放入临时数组，再将27放入，得到[3, 27]。 - 继续合并，比如将
[3, 27]和[38, 43]合并。i指向3，j指向38，比较3和38，将3放入临时数组，i后移，比较27和38，将27放入，以此类推，最终得到[3, 27, 38, 43]。 - 对右半部分也进行类似合并，最后将左右两个有序的子数组合并，得到整个有序的数组
[3, 9, 10, 27, 38, 43, 82]。
- 以最底层的合并为例，假设要合并
方法的优劣
- 时间复杂度：
- 归并排序的时间复杂度在最好、最坏和平均情况下均为 (O(n \log n))。这是因为每次分解都将数组分成两部分，共需要 (\log n) 层递归，而每层递归中合并操作的时间复杂度为 (O(n))，所以总的时间复杂度为 (O(n \log n))。
- 空间复杂度：
- 空间复杂度为 (O(n))，主要是因为在合并过程中需要一个与原数组长度相同的临时数组来存储合并的结果。
优点：
- 时间复杂度稳定为 (O(n \log n))，适用于对稳定性有要求的排序场景，因为归并排序是稳定排序算法，即相等元素的相对顺序在排序前后保持不变。
缺点： - 空间复杂度较高，需要额外的 (O(n)) 空间用于临时数组。在处理大规模数据且内存紧张的情况下可能不太适用。