概念
归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用，归并排序将两个已排序的表合并成一个表。
归并排序基本原理
通过对若干个有序结点序列的归并来实现排序。 所谓归并是指将若干个已排好序的部分合并成一个有序的部分。
单链表实现归并排序
找到中间点拆分链表
public ListNode
getMiddle(ListNode head) {
if (head ==
null) {
return head;
}
ListNode slow, fast;
slow = fast = head;
while (fast.next !=
null && fast.next.next !=
null) {
slow = slow.next;
fast = fast.next.next;
}
return slow;
}
合并排好序的链表
public ListNode
merge(ListNode a, ListNode b) {
ListNode dummyHead, curr;
dummyHead =
new ListNode(
0);
curr = dummyHead;
while (a !=
null && b !=
null) {
if (a.val <= b.val) {
curr.next = a;
a = a.next;
}
else {
curr.next = b;
b = b.next;
}
curr = curr.next;
}
curr.next = (a ==
null) ? b : a;
return dummyHead.next;
}
单链表的归并排序
public ListNode
merge_sort(ListNode head) {
if (head ==
null || head.next ==
null) {
return head;
}
ListNode middle = getMiddle(head);
ListNode sHalf = middle.next;
middle.next =
null;
return merge(merge_sort(head), merge_sort(sHalf));
}
Application.java
public static void main(
String[] args) {
ListNode head =
new ListNode(
0);
ListNode l1 =
new ListNode(
2);
ListNode l2 =
new ListNode(
5);
ListNode l3 =
new ListNode(
3);
ListNode l4 =
new ListNode(
8);
ListNode l5 =
new ListNode(
4);
ListNode l6 =
new ListNode(
2);
ListNode l7 =
new ListNode(
1);
head.
next = l1;
l1.
next = l2;
l2.
next = l3;
l3.
next = l4;
l4.
next = l5;
l5.
next = l6;
l6.
next = l7;
l7.
next =
null;
ListNode p = head;
while (p.
next !=
null) {
System.out.print(p.val);
p = p.
next;
}
System.out.print(p.val);
System.out.println();
new MergeSort().merge_sort(head);
p = head;
while (p !=
null) {
System.out.print(p.val);
p = p.
next;
}
}
执行效果图
