一、归并排序的基本概念
咱先来说说归并排序是个啥。归并排序是一种很经典的排序算法，它的核心思想就是分治和合并。啥是分治呢？简单来说，就是把一个大问题拆分成一个个小问题，等把这些小问题都解决了，大问题也就解决了。合并呢，就是把解决好的小问题的结果整合起来。
比如说，你有一堆杂乱无章的扑克牌，要把它们按顺序排好。归并排序会先把这堆牌分成两堆，然后再把每堆继续分，一直分到每堆只有一张牌为止。这就是分治的过程。然后呢，再把这些单张的牌两两合并，合并的时候按顺序排好，接着再把合并后的小堆继续合并，直到最后又变成一堆排好序的牌。这就是合并的过程。
二、归并排序的具体实现步骤
1. 分治阶段
分治阶段就是不断地把数组或链表分成两半，直到每一部分只有一个元素或者为空。下面是用 Java 实现的分治阶段的代码示例：
// Java 技术栈
// 分治函数，对数组进行分割
public static void mergeSort(int[] arr, int left, int right) {
if (left < right) {
// 计算中间位置
int mid = left + (right - left) / 2;
// 递归分割左半部分
mergeSort(arr, left, mid);
// 递归分割右半部分
mergeSort(arr, mid + 1, right);
// 合并左右两部分
merge(arr, left, mid, right);
}
}
2. 合并阶段
合并阶段就是把两个已经排好序的子数组合并成一个有序的数组。下面是 Java 实现的合并阶段的代码示例：
// Java 技术栈
// 合并函数，将两个有序数组合并成一个有序数组
public 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 中
for (int i = 0; i < n1; ++i) {
L[i] = arr[left + i];
}
// 将右半部分元素复制到临时数组 R 中
for (int j = 0; j < n2; ++j) {
R[j] = arr[mid + 1 + j];
}
// 初始化索引变量
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++;
}
// 将左半部分剩余元素复制到原数组
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}
// 将右半部分剩余元素复制到原数组
while (j < n2) {
arr[k] = R[j];
j++;
k++;
}
}
3. 完整的归并排序代码
把分治和合并阶段的代码结合起来，就得到了完整的归并排序代码：
// Java 技术栈
public class MergeSort {
// 分治函数，对数组进行分割
public static void mergeSort(int[] arr, int left, int right) {
if (left < right) {
// 计算中间位置
int mid = left + (right - left) / 2;
// 递归分割左半部分
mergeSort(arr, left, mid);
// 递归分割右半部分
mergeSort(arr, mid + 1, right);
// 合并左右两部分
merge(arr, left, mid, right);
}
}
// 合并函数，将两个有序数组合并成一个有序数组
public 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 中
for (int i = 0; i < n1; ++i) {
L[i] = arr[left + i];
}
// 将右半部分元素复制到临时数组 R 中
for (int j = 0; j < n2; ++j) {
R[j] = arr[mid + 1 + j];
}
// 初始化索引变量
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++;
}
// 将左半部分剩余元素复制到原数组
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}
// 将右半部分剩余元素复制到原数组
while (j < n2) {
arr[k] = R[j];
j++;
k++;
}
}
public static void main(String[] args) {
int[] arr = {12, 11, 13, 5, 6, 7};
System.out.println("排序前的数组: ");
for (int num : arr) {
System.out.print(num + " ");
}
mergeSort(arr, 0, arr.length - 1);
System.out.println("\n排序后的数组: ");
for (int num : arr) {
System.out.print(num + " ");
}
}
}
在这个代码中，mergeSort 函数负责分治，merge 函数负责合并。在 main 函数中，我们创建了一个数组，然后调用 mergeSort 函数对其进行排序，并输出排序前后的数组。
三、归并排序在链表排序中的应用
链表排序和数组排序有点不一样，因为链表不能像数组那样直接通过索引访问元素。但是归并排序同样适用于链表。下面是用 Java 实现的链表归并排序的代码示例：
// Java 技术栈
// 定义链表节点类
class ListNode {
int val;
ListNode next;
ListNode(int x) { val = x; }
}
public class LinkedListMergeSort {
// 对链表进行归并排序
public ListNode sortList(ListNode head) {
if (head == null || head.next == null) {
return head;
}
// 找到链表的中间节点
ListNode mid = getMiddle(head);
ListNode right = mid.next;
mid.next = null;
// 递归排序左右两部分
ListNode leftSorted = sortList(head);
ListNode rightSorted = sortList(right);
// 合并左右两部分
return mergeLists(leftSorted, rightSorted);
}
// 找到链表的中间节点
private ListNode getMiddle(ListNode head) {
if (head == null) {
return null;
}
ListNode slow = head;
ListNode fast = head.next;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
return slow;
}
// 合并两个有序链表
private ListNode mergeLists(ListNode l1, ListNode l2) {
ListNode dummy = new ListNode(0);
ListNode tail = dummy;
while (l1 != null && l2 != null) {
if (l1.val < l2.val) {
tail.next = l1;
l1 = l1.next;
} else {
tail.next = l2;
l2 = l2.next;
}
tail = tail.next;
}
if (l1 != null) {
tail.next = l1;
}
if (l2 != null) {
tail.next = l2;
}
return dummy.next;
}
public static void main(String[] args) {
// 创建链表 4 -> 2 -> 1 -> 3
ListNode head = new ListNode(4);
head.next = new ListNode(2);
head.next.next = new ListNode(1);
head.next.next.next = new ListNode(3);
LinkedListMergeSort sorter = new LinkedListMergeSort();
ListNode sortedHead = sorter.sortList(head);
// 输出排序后的链表
ListNode current = sortedHead;
while (current != null) {
System.out.print(current.val + " ");
current = current.next;
}
}
}
在这个代码中，sortList 函数负责对链表进行归并排序，getMiddle 函数用于找到链表的中间节点，mergeLists 函数用于合并两个有序链表。在 main 函数中，我们创建了一个链表，然后调用 sortList 函数对其进行排序，并输出排序后的链表。
四、归并排序的应用场景
1. 大规模数据排序
当需要对大规模数据进行排序时，归并排序是一个不错的选择。因为它的时间复杂度是 $O(n log n)$，在处理大规模数据时效率比较高。比如说，在处理电商平台的商品价格排序、数据库中的数据排序等场景中，归并排序都能发挥很好的作用。
2. 外部排序
外部排序是指数据量太大，无法一次性全部加载到内存中进行排序的情况。归并排序可以通过分块和合并的方式，将数据分成多个小块进行排序，然后再将这些小块合并成一个有序的整体。这在处理大数据集时非常有用，比如处理日志文件、大型数据库备份等。
3. 链表排序
就像前面我们看到的，归并排序在链表排序中也有很好的应用。因为链表的特性，不能像数组那样随机访问元素，而归并排序只需要顺序访问链表节点，非常适合链表排序。
五、归并排序的技术优缺点
1. 优点
- 稳定性：归并排序是一种稳定的排序算法，即相等元素的相对顺序在排序前后不会改变。这在一些对元素相对顺序有要求的场景中非常重要，比如在对学生成绩进行排序时，如果有多个学生成绩相同，我们希望他们的顺序在排序后保持不变。
- 时间复杂度：归并排序的时间复杂度始终是 $O(n log n)$，无论数据的初始状态如何。这使得它在处理大规模数据时具有较好的性能。
- 适用性：归并排序不仅适用于数组，还适用于链表等数据结构，具有很强的适用性。
2. 缺点
- 空间复杂度：归并排序需要额外的空间来存储临时数组或链表，空间复杂度为 $O(n)$。这在处理大规模数据时可能会占用较多的内存。
- 常数因子：虽然归并排序的时间复杂度是 $O(n log n)$，但它的常数因子相对较大，在处理小规模数据时，可能不如一些简单的排序算法（如插入排序）效率高。
六、归并排序的注意事项
1. 空间使用
由于归并排序需要额外的空间来存储临时数据，所以在处理大规模数据时，要注意内存的使用情况。可以考虑使用一些优化方法，如原地归并排序，来减少空间的使用。
2. 递归深度
归并排序是通过递归实现的，递归深度为 $O(log n)$。在处理大规模数据时，递归深度可能会比较大，这可能会导致栈溢出的问题。可以考虑使用迭代的方式来实现归并排序，避免递归带来的问题。
3. 数据类型
归并排序适用于各种数据类型，只要这些数据类型可以进行比较。在使用时，要确保数据类型支持比较操作，否则需要自定义比较函数。
七、文章总结
归并排序是一种非常实用的排序算法，它的核心思想是分治和合并。通过不断地将数据分成小问题，然后解决这些小问题，最后将结果合并起来，实现对数据的排序。归并排序具有稳定性、时间复杂度低等优点，适用于大规模数据排序、外部排序和链表排序等场景。但它也有空间复杂度高、常数因子大等缺点。在使用归并排序时，要注意空间使用、递归深度和数据类型等问题。
评论