我是一个计算机专业研0的学生卡蒙Camel🐫🐫🐫（刚保研）
记录每天学习过程（主要学习Java、python、人工智能），总结知识点（内容来自：自我总结+网上借鉴）
希望大家能一起发现问题和补充，也欢迎讨论👏👏👏

归并排序

介绍

归并排序（Merge Sort）是一种基于分治法的排序算法。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。

1. ⭐基本思想：它的工作原理是将数组递归地分成两个子数组，对每个子数组分别进行排序，然后将已排序的子数组合并成一个完整的有序数组。归并排序的时间复杂度为 $O(nlogn)$ ，这使得它对于大型数据集非常有效。

2. ⏩步骤：归并排序是一个递归算法

3. 分解：将未排序的数组以中点为中心分为两个子数组。

4. 解决：递归地对这两个子数组进行归并排序。

5. 合并：将两个已经排序好的子数组合并成一个单一的有序数组。

Java代码实现

java">import java.util.Arrays;public class MergeSort {// 主函数，用于启动归并排序public static void mergeSort(int[] array) {if (array.length < 2) {return;}int mid = array.length / 2;int[] left = Arrays.copyOfRange(array, 0, mid);int[] right = Arrays.copyOfRange(array, mid, array.length);mergeSort(left); // 递归排序左半部分mergeSort(right); // 递归排序右半部分// 排序完后，左右两边都是有序的merge(array, left, right); // 合并左右两部分}// 合并两个已排序的子数组private static void merge(int[] result, int[] left, int[] right) {int i = 0, j = 0, k = 0;// 1. 比较两个数组的大小，将小的放入合并数组肿while (i < left.length && j < right.length) {if (left[i] <= right[j]) {result[k++] = left[i++];} else {result[k++] = right[j++];}}// 2. 比较完后，将其中一边剩余的数组全部添加到合并数组中while (i < left.length) {result[k++] = left[i++];}while (j < right.length) {result[k++] = right[j++];}}// 测试方法public static void main(String[] args) {int[] array = {38, 27, 43, 3, 9, 82, 10};System.out.println("原始数组: " + Arrays.toString(array));mergeSort(array);System.out.println("排序后的数组: " + Arrays.toString(array));}
}

算法分析

• 稳定性：稳定

• 时间复杂度：

• 最佳：$O(nlogn)$

• 最差：$O(nlogn)$

• 平均：$O(nlogn)$

• 空间复杂度：$O(n)$

实现图解🖌️

1. 根据上图可知，使用递归方法（递归出口是当数组长度为1的时候），然后逐渐左右两个数组合并，直到合并完成（先排序再合并）。

2. 合并过程：将两个已经有序的数组合并成一个有序数组

   2.1 初始化指针：

   • i：指向left数组的起始位置。

   • j：指向right数组的起始位置。

   • k：指向result数组的起始位置。

   2.2 比较与合并：

   • 比较left[i]和right[j]，将较小的那个复制到result[k]中，并向前移动相应数组的指针（i++或j++），同时更新k++以指向下一个待填充的位置。

   • 重复上述步骤直到其中一个子数组被完全遍历。

   2.3 处理剩余元素：

   • 如果left或right中的任意一个还有剩余元素，则直接将这些元素复制到result数组中，因为它们已经是有序的。

   • 注意，由于我们总是从两个子数组中选择较小的元素，所以当一个子数组被耗尽时，另一个子数组剩下的所有元素都比之前放入result的所有元素要大，因此可以直接添加到result的末尾。

   2.4 完成合并：

   • 当所有元素都被正确放置到result数组后，合并过程结束。

和快速排序对比(面试)

特性	归并排序 (Merge Sort)	快速排序 (Quick Sort)
时间复杂度	O(n log n)	平均情况：O(n log n) 最坏情况：O(n²)
空间复杂度	O(n) - 需要额外空间用于合并操作	O(log n) - 递归栈空间 最坏情况：O(n)
稳定性	稳定排序算法	不稳定排序算法
适应性	对任何输入数据分布都能保持一致性能	对几乎已排序的数据集特别有效但对有序数据可能退化到最坏情况
实现难度	实现较为直观，代码结构清晰	实现相对复杂，尤其是优化措施如随机基准选择等
应用场景	外部排序问题、大文件排序、需要维持元素相对顺序的应用	内存中的小到中等规模数据集的内部排序
原地排序	否 - 需要额外数组存储	是 - 在理想情况下只需要少量额外空间
分区策略	分而治之，将数组分成两半	选择一个基准元素，然后根据基准划分数组
递归深度	每次递归调用都减少一半，通常为 logn	取决于基准选择；最坏情况下可能是 n