排序算法——归并排序
将两个有序数列合并为一个有序数列，我们称之为“归并”；
归并排序（Merge Sort）是利用归并思想对数列进行排序。我们也可以分为两部分理解，归即递归，对数列进行递归分解，直到单个的一个元素。并即合并，对数列进行合并，直至有序。
1. 数组的递归排序
明确分解的主体：
方法的参数是数组元素的下标！
public static void mergeSort(int[] arr) {
if (arr == null || arr.length == 0) {
return;
}
//对元素的下标进行分解
mergeSort(arr, 0, arr.length - 1);
}
递归分解：
- 明确递归出口，参数为null或者数组长度为1时，直接返回；
- 将数组一直划分，直到数组长度为1时，直接返回，执行合并操作；
private static void mergeSort(int[] arr, int left, int right) {
//递归出口，如果相等，不对数组进行操作性，原数组还是本身
if (left >= right) {
return;
}
//left和right是数组下标
int mod = (left + right) / 2;
mergeSort(arr, left, mod);
mergeSort(arr, mod + 1, right);
//当一个元素的时候，返回空，我拿到的left和right是2个元素
mergeSort(arr, left, mod, right);
}
两个有序数组合并：
- 我们的参数均是数组的下标，而不是长度；
- 声明临时数组，保存两个数组中比较小的元素；
- 将剩余元素直接放入到临时数组中；
- 临时数组迁移到原数组中；
/**
* 合并逻辑
*
* @param arr
* @param left 数组A最左得知
* @param mod 数组A最右下标
* @param right 数组B的最右下标
*/
private static void mergeSort(int[] arr, int left, int mod, int right) {
int i = left; //数组A指针
int j = mod + 1; //数组B指针
int k = 0;
int[] temp = new int[right - left + 1]; //数组初始化长度
while (i <= mod && j <= right) { //小于等于下标
if (arr[i] < arr[j]) {
temp[k++] = arr[i++];
} else {
temp[k++] = arr[j++];
}
}
while (i <= mod) {
temp[k++] = arr[i++];
}
//分别将剩余元素放入到数组中
while (j <= right) {
temp[k++] = arr[j++];
}
//数据复制完毕
for (int len = 0; len < temp.length; len++) {
arr[left + len] = temp[len];
}
}
2. 链表的排序
对链表的排序，本质上也是可以使用归并排序。我们想一下，归并思想在于将数列找到中点一直切分，直至数列长度是1，然后在合并。本质上就是有序数列的合并。
好的，按照这个思维，咱们开始吧。
我们对这个方法着重的讲述一下，毕竟第三步已经写文章讲过了。
快慢指针找寻链表中点：我们声明2个指针，fast指针每次走2步，slow指针每次走1步。当fast指针到达终点的时候，slow指针到达中点，于是我们得到了中点位置，然后将breakNode指针断开，就实现了链表的中间切分。
//分解链表
private ListNode resolveList(ListNode head) {
//只有一个元素，或是null,返回自己
if (head == null || head.next == null) {
return head;
}
//快慢指针找中点
ListNode fast = head; //快指针
ListNode slow = head; //慢指针
ListNode breakNode = head; //断开的位置
while (fast != null && fast.next != null) {
fast = fast.next.next; //快指针走两步
breakNode = slow; //慢指针前一个元素
slow = slow.next; //慢指针走异步
}
//快指针到终点，慢指针到中点
breakNode.next = null; //链表断开
//继续分解，直至一个元素
ListNode list1 = resolveList(head); //前链表
ListNode list2 = resolveList(slow); //后链表
return mergeList(list1, list2);
}
源码：
//如何对链表进行排序——归并排序
//（1）快慢指针找中点，链表断开
//（2）链表节点递归分解
//（3）有序合并排序
public ListNode sortList(ListNode head) {
if (head == null) {
return head;
}
return resolveList(head);
}
//分解链表
private ListNode resolveList(ListNode head) {
//只有一个元素，或是null,返回自己
if (head == null || head.next == null) {
return head;
}
//快慢指针找中点
ListNode fast = head; //快指针
ListNode slow = head; //慢指针
ListNode breakNode = head; //断开的位置
while (fast != null && fast.next != null) {
fast = fast.next.next; //快指针走两步
breakNode = slow; //慢指针前一个元素
slow = slow.next; //慢指针走异步
}
//快指针到终点，慢指针到中点
breakNode.next = null; //链表断开
//继续分解，直至一个元素
ListNode list1 = resolveList(head); //前链表
ListNode list2 = resolveList(slow); //后链表
return mergeList(list1, list2);
}
private ListNode mergeList(ListNode list1, ListNode list2) {
if (list1 == null)
return list2;
if (list2 == null)
return list1;
if (list1.val < list2.val) {
list1.next = mergeList(list1.next, list2);
return list1;
} else {
list2.next = mergeList(list1, list2.next);
return list2;
}
}
