归并排序 (Merge Sort) 介绍
核心思想
归并排序是基于 分治法 的一种经典排序算法，它的基本思想是将数组分成两个子数组，分别排序后再合并。这种“分而治之”的策略使得归并排序在任何情况下都能保持较好的性能。
形象类比
想象你有一堆纸牌要按大小排序：
1. 将纸牌分成两堆。
2. 每堆再分成更小的两堆，直到每堆只有一张牌。
3. 将小堆的牌按顺序合并成一个更大的有序堆，直到所有牌都排好。
步骤
- 分割：将数组分成两半，递归地对两部分进行排序。
- 合并：将两个有序数组合并为一个有序数组。
归并排序的执行流程
对数组 [8, 3, 5, 2, 7, 4] 进行归并排序的过程如下：
-
分割阶段：
- 初始数组
[8, 3, 5, 2, 7, 4]分为两部分[8, 3, 5]和[2, 7, 4]。 - 再分割为
[8],[3, 5]和[2],[7, 4]。 [3, 5]分为[3],[5]；[7, 4]分为[7],[4]。
- 初始数组
-
合并阶段：
- 合并
[3]和[5]得到[3, 5]；合并[7]和[4]得到[4, 7]。 - 合并
[8]和[3, 5]得到[3, 5, 8]；合并[2]和[4, 7]得到[2, 4, 7]。 - 最后合并
[3, 5, 8]和[2, 4, 7]得到[2, 3, 4, 5, 7, 8]。
- 合并
归并排序代码实现
Java代码示例
public class MergeSortUtil {
// 主方法
public static void mergeSort(int[] arr) {
if (arr.length < 2) {
return;
}
int mid = arr.length / 2;
int[] left = new int[mid];
int[] right = new int[arr.length - mid];
// 拆分数组
System.arraycopy(arr, 0, left, 0, mid);
System.arraycopy(arr, mid, right, 0, arr.length - mid);
// 递归排序左右两部分
mergeSort(left);
mergeSort(right);
// 合并两个有序数组
merge(arr, left, right);
}
// 合并两个有序数组
private static void merge(int[] arr, int[] left, int[] right) {
int i = 0, j = 0, k = 0;
while (i < left.length && j < right.length) {
if (left[i] <= right[j]) {
arr[k++] = left[i++];
} else {
arr[k++] = right[j++];
}
}
// 将剩余元素复制到数组中
while (i < left.length) {
arr[k++] = left[i++];
}
while (j < right.length) {
arr[k++] = right[j++];
}
}
// 测试
public static void main(String[] args) {
int[] arr = {8, 3, 5, 2, 7, 4};
mergeSort(arr);
for (int num : arr) {
System.out.print(num + " ");
}
// 输出：2 3 4 5 7 8
}
}
时间复杂度和空间复杂度
时间复杂度
归并排序的时间复杂度分析基于其 分割 和 合并 的过程：
1. 分割：
- 每次将数组分为两半，分割需要 (O(\log n)) 次。
2. 合并：
- 每一层的合并需要 (O(n)) 次操作。
总时间复杂度为：
[
T(n) = O(n \log n)
]
空间复杂度
归并排序需要额外的空间来存储子数组：
- 每次递归会创建两个子数组，空间复杂度为 (O(n))。
总空间复杂度为：
[
O(n)
]
归并排序在 Android 开发中的应用场景
归并排序的稳定性和高效性使其适用于以下场景：
1. 需要稳定排序
- 稳定排序意味着相同元素的相对顺序保持不变。
- 例如，在电商应用中对商品按照价格排序，但相同价格的商品需要保持初始顺序。
2. 大规模数据排序
- 在后台线程中对大量数据进行排序（如处理从服务器拉取的大列表）。
- 可用于 后台服务，如对数据库中的记录排序。
3. 多关键字排序
- 归并排序适合对多字段进行联合排序，例如对联系人列表按照姓氏和名字的顺序排序。
4. 文件排序
- 在内存有限但需要对大文件排序的场景中，可结合 外部归并排序 分阶段排序。
归并排序与其他排序算法对比
| 排序算法 | 时间复杂度 | 空间复杂度 | 是否稳定 | 适用场景 |
|---|---|---|---|---|
| 冒泡排序 | (O(n^2)) | (O(1)) | 是 | 小规模数据排序 |
| 插入排序 | (O(n^2))，(O(n)) | (O(1)) | 是 | 小规模或接近有序数据 |
| 快速排序 | (O(n \log n))，最坏 (O(n^2)) | (O(\log n)) | 否 | 大规模数据排序，性能优越 |
| 归并排序 | (O(n \log n)) | (O(n)) | 是 | 稳定排序需求，大规模数据 |
| 堆排序 | (O(n \log n)) | (O(1)) | 否 | 内存受限的大数据排序 |
总结
归并排序在 Android 开发中有以下重要价值：
1. 稳定性好：适合有稳定性要求的排序任务。
2. 适合大规模数据：性能稳定，适用于后台任务或大数据集合的排序。
3. 内存充足时的首选：虽然空间复杂度较高，但在内存充足的场景下，其效率非常优异。
归并排序通常用于对复杂的数据结构（如对象列表）进行排序，是性能和稳定性兼备的选择。
当前文章价值6.64元，扫一扫支付后添加微信提供帮助！（如不能解决您的问题，可以申请退款）
评论已关闭！