基础5归并排序
【基础5】归并排序
核心思路
归并排序基本思想是将一个数组分成两个子数组,分别对这两个子数组进行排序,然后将排好序的子数组合并成一个最终的有序数组,即分治法:
- 分:将数组递归拆分成左右两半,直到每个子数组只剩1个元素(天然有序)。
- 治:将两个有序子数组合并为一个有序数组,直到合并成完整数组。
优缺点
优点 | 缺点 |
---|---|
✅ 稳定排序(相等元素顺序不变) | ❌ 额外空间(需O(n)临时数组) |
✅ 时间复杂度稳定O(n logn) | ❌ 递归可能栈溢出(极大数据量时) |
✅ 适合大数据量、外排序 | ❌ 对小数据量效率不如插入排序 |
适用范围
- 大数据量
- 稳定性高要求 (多次排序顺序必须相同)
- 外排序 (处理无法一次性装入内存的数据,如大文件拆散排序)
- 链表排序 (归并排序是链表排序的最佳选择之一)
复杂度
时间复杂度:O(n logn),空间复杂度:O(n)
代码实现(Java)
public class MergeSort { public static void sort(int[] arr) { if (arr == null || arr.length <= 1) return; //通用临时数组 int[] temp = new int[arr.length]; mergeSort(arr, 0, arr.length - 1, temp); } private static void mergeSort(int[] arr, int left, int right, int[] temp) { //递归终止条件:只剩1个元素 if (left >= right){ return; } //分成左右子区间递归排序(逻辑分开,没有物理分开) int mid = left + (right - left)/2; mergeSort(arr, left, mid, temp); mergeSort(arr, mid + 1, right, temp); //合并左右两部分 merge(arr, left, mid, right, temp); } private static void merge(int[] arr, int left, int mid, int right, int[] temp) { //左半部分起始 int i = left; //右半部分起始 int j = mid + 1; //临时数组索引 int t = 0; //左右两部分按大小顺序合并到临时数组 while (i <= mid && j <= right) { //强稳定性关键:相等时也取左区间元素 if (arr[i] <= arr[j]) { temp[t++] = arr[i++]; }else { temp[t++] = arr[j++]; } } //剩余元素拷贝到临时数组 while (i <= mid) temp[t++] = arr[i++]; while (j <= right) temp[t++] = arr[j++]; //将临时数组数据拷贝回原数组 t = 0; while (left <= right){ arr[left++] = temp[t++]; } } }
流程示例
1.原始数组: [8,3,5,1,7,4] 2.第一次分解 → [8,3,5] 和 [1,7,4] 3.继续分解左半部分:[8,3,5] → [8,3] 和 [5],[8,3] → [8] 和 [3] 继续分解右半部分:[1,7,4] → [1,7] 和 [4] [1,7] → [1] 和 [7] 4.合并 [8] 和 [3] → [3,8] 5.合并 [3,8] 和 [5] → [3,5,8](左半部分完成) 6.合并 [1] 和 [7] → [1,7] 7.合并 [1,7] 和 [4] → [1,4,7](右半部分完成) 8.合并左右两部分 [3,5,8] 和 [1,4,7] → [1,3,4,5,7,8]