Loading... ## 简介 归并排序（Merge Sort）是建立在归并操作上的一种有效，稳定的排序算法，该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。 --- ## 一般步骤 #### 1. 二分递归法-分治法  #### 2. 线性迭代  --- ## 示例代码 链表排序，采用二分递归 ```java // 采用归并排序 public ListNode sortList(ListNode head) { // 递归基！！！ // 若head 为空 或者为 单个节点则返回自身。 if(head == null || head.next == null){ return head; } // 找中点 ListNode middle = findMiddle(head); ListNode tail = middle.next; // 分隔成两个链表 middle.next = null; // 分而治之！！！ ListNode left = sortList(head); ListNode right = sortList(tail); // 合并子问题 将两个升序链表合并成一个升序链表 ListNode res = mergeTwoLists(left, right); return res; } ``` ```java private ListNode findMiddle( ListNode head){ // 采用快慢指针 ListNode slow = head; ListNode fast = head.next; while (fast != null && fast.next != null){ fast = fast.next.next; slow = slow.next; } return slow; } ``` ```java private ListNode mergeTwoLists(ListNode l1, ListNode l2){ ListNode dummy = new ListNode(-1); ListNode node = dummy; while (l1 != null && l2 != null){ if(l1.val <= l2.val){ node.next = l1; l1 = l1.next; }else{ node.next = l2; l2 = l2.next; } node = node.next; } // 若l1剩余 if(l1 != null){ node.next = l1; return dummy.next; } // 若l2剩余 if(l2 != null){ node.next = l2; return dummy.next; } // 若 l1 和l2 同时为空, 则 只会在初始输入两者均为空时发生。 // 所以直接返回为空 return null; } ``` 最后修改：2020 年 07 月 24 日 10 : 27 AM © 允许规范转载
