归并排序采用分治的思想,通过不断的将数组一分为二,直到不可再分,然后对已排序的子数组递归合并,最后使得整个数组有序,归并排序的最好、最坏以及平均时间复杂度都是O(NlogN)。
算法的主要思路是
下面是数组[6, 5, 12, 10, 9, 1]
使用归并排序算法进行排序的过程。
归并排序算法实现
1import java.util.Arrays;
2
3public class Main {
4
5 public static void main(String[] args) {
6 int[] arr = {4, 5, 6, 1, 3, 2, 0};
7 mergeSort(arr, 0, arr.length - 1);
8 System.out.println(Arrays.toString(arr));
9 }
10
11 public static void mergeSort(int[] arr, int left, int right) {
12 if (left == right) {
13 return;
14 }
15 int mid = (left + right) / 2;
16 mergeSort(arr, left, mid);
17 mergeSort(arr, mid + 1, right);
18 merge(arr, left, mid, right);
19 }
20
21 public static void merge(int[] arr, int left, int mid, int right) {
22 /**
23 * 建议放到全局,这样可以减少递归分配的内存
24 */
25 int[] sortedArray = new int[right - left + 1];
26 int i = left, j = mid + 1, k = 0;
27 while (i <= mid && j <= right) {
28 if (arr[i] <= arr[j]) {
29 sortedArray[k++] = arr[i++];
30 } else {
31 sortedArray[k++] = arr[j++];
32 }
33 }
34 while (i <= mid) {
35 sortedArray[k++] = arr[i++];
36 }
37 while (j <= right) {
38 sortedArray[k++] = arr[j++];
39 }
40 for (i = left; i <= right; i++) {
41 arr[i] = sortedArray[i - left];
42 }
43 }
44}
45
归并排序虽然在数组排序上效率低于快速排序,但是对链表进行排序时,归并排序通常是最佳选择,因为链表无法通过索引访问,如果使用快速排序效率会低很多,而归并排序对随机访问依赖较小,所以能够高效的完成链表的排序。
另外由于归并排序在排序过程中,左右子数组的排序并无依赖关系,所以可以并行提高效率。
下面是使用归并排序算法对链表进行排序的实现。
1/**
2 * 链表归并排序算法实现
3 */
4class Node {
5 int val;
6 Node next;
7
8 Node() {
9 }
10
11 Node(int val) {
12 this.val = val;
13 }
14}
15
16class Main {
17
18 public static void main(String[] args) {
19 Node head = buildList(new int[]{4, 2, 1, 3, 7, 6, 5});
20 Node sortedHead = mergeSort(head);
21 printList(sortedHead);
22 }
23
24 /**
25 * 链表归并排序
26 *
27 * @param head 待排序链表
28 * @return 排序好的链表
29 */
30 public static Node mergeSort(Node head) {
31 if (head == null || head.next == null)
32 return head;
33 /**
34 * 1. 获取链表的中间位置
35 */
36 Node middle = getMiddle(head);
37 /**
38 * 2. 递归对左右两边的子链表进行归并排序
39 */
40 Node left = mergeSort(head);
41 Node right = mergeSort(middle);
42 /**
43 * 3. 合并已排序的链表
44 */
45 return merge(left, right);
46 }
47
48
49 /**
50 * 合并有序链表
51 *
52 * @param list1 待合并的有序链表1
53 * @param list2 待合并的有序链表2
54 * @return 合并好的有序链表
55 */
56 private static Node merge(Node list1, Node list2) {
57 /**
58 * 辅助节点
59 */
60 Node dummyHead = new Node();
61 Node tail = dummyHead;
62 while (list1 != null && list2 != null) {
63 if (list1.val < list2.val) {
64 tail.next = list1;
65 list1 = list1.next;
66 } else {
67 tail.next = list2;
68 list2 = list2.next;
69 }
70 tail = tail.next;
71 }
72 tail.next = (list1 != null) ? list1 : list2;
73 return dummyHead.next;
74 }
75
76 /**
77 * 通过快慢指针获取链表中间节点
78 *
79 * @param head 链表
80 * @return 中间节点
81 */
82 private static Node getMiddle(Node head) {
83 Node slow = null;
84 while (head != null && head.next != null) {
85 slow = (slow == null) ? head : slow.next;
86 head = head.next.next;
87 }
88 Node middle = slow.next;
89 slow.next = null;
90 return middle;
91 }
92
93 /**
94 * 通过数组构建链表
95 *
96 * @param arr 数组
97 * @return 链表
98 */
99 public static Node buildList(int[] arr) {
100 Node head = null, previous = null;
101 for (int i : arr) {
102 Node node = new Node(i);
103 if (head == null) {
104 head = node;
105 } else {
106 previous.next = node;
107 }
108 previous = node;
109 }
110 return head;
111 }
112
113 /**
114 * 打印链表
115 *
116 * @param head 链表
117 */
118 public static void printList(Node head) {
119 StringBuilder sb = new StringBuilder();
120 while (head != null) {
121 sb.append(head.val).append(" ");
122 head = head.next;
123 }
124 System.out.println(sb);
125 }
126}
127