归并排序：数组和链表的多种实现
- 2021 年 11 月 11 日
- 筆記
思想
将数组进行分割，形成多个组合并继续分割，一直到每一组只有一个元素时，此时可以看作每一组都是有序的
然后逐渐合并相邻的有序组合（合并之后也是有序的），分组个数呈倍数减少，每一组的元素个数呈倍数增长
一直到只剩下一个组合包含所有元素，将代表着数组排序完毕
归并排序是一种类似二叉树遍历的实现，所以时间复杂度与二叉树遍历一样：o(n*log2n)
本来画了个图，但是因为太丑了，所以放在最下面
数组的归并排序实现
自顶向下
使用递归不断往下遍历，一直到当前组合只有一个元素，开始回溯，将相邻的组合进行合并，直到最后只剩下一个组合，数组即有序。
比如
44,8,33,5,1,9,2这组数字使用归并排序的流程通过运行结果可以看到
首先递归到只有44一个元素的组合，然后回溯，等待相邻组合变成有序之后，与相邻组合8进行合并
44 ， 8 这个组合 又等待相邻组合 33 ， 5 变成有序之后，进行合并，一直到合并完毕
每次合并的相邻组合拥有的元素个数，必须与当前组合相等或者不足
实现代码
1 import java.util.Arrays; 2 3 public class MergeSortDemo { 4 5 public static void main(String[] args) { 6 7 int[] arr = new int[]{44,8,33,5,1,9,2}; 8 9 System.out.println(Arrays.toString(arr)); 10 11 mergeSort(arr,0,arr.length-1); 12 13 System.out.println(Arrays.toString(arr)); 14 15 } 16 17 18 public static void mergeSort(int[] arr,int left,int right){ 19 20 if(left >= right){ 21 return; 22 } 23 int mid = (right - left)/2 + left; 24 25 mergeSort(arr,left,mid); 26 27 mergeSort(arr,mid+1,right); 28 29 merge(arr,left,mid,right); 30 } 31 public static void merge(int[] arr,int left,int mid,int right){ 32 33 int len = right - left + 1; 34 35 36 //分别记录两组元素的起始位置和结束位置 37 int s1 = left, e1 = mid,s2 = mid+1 , e2 = right; 38 39 int[] newArr = new int[len]; 40 int index = 0; 41 42 //将两组元素进行合并 43 while (s1 <= e1 && s2 <= e2){ 44 45 if(arr[s1] > arr[s2]){ 46 newArr[index++] = arr[s2++]; 47 }else { 48 newArr[index++] = arr[s1++]; 49 } 50 } 51 52 while (s1 <= e1){ 53 newArr[index++] = arr[s1++]; 54 } 55 56 while (s2 <= e2){ 57 newArr[index++] = arr[s2++]; 58 } 59 //将排序好的结果复制回原数组 60 //新数组的下标[0...index] 对应 原数组[left...right] 61 for (int i = left; i <= right; i++) { 62 arr[i] = newArr[i - left]; 63 } 64 } 65 }
View Code
自底向上
自底向上没有使用递归的方式，而是使用循环修改数组
首先设置一个分割值gap进行分组，每个组合的元素数量为gap，从1开始，呈倍数增长，一直到等于数组长度n
在gap每次增长之前，都将相邻的组合进行合并，由n个组合并为1个组
通过运行结果可以看出，运行中有两层循环
第一层循环不断增长gap的值
第二层循环，根据gap的值，沿着数组每次找出两个组合，进行合并，一直到找不到为止
合并过程与上面的做法类似
实现代码
1 public class MergeSortDemo { 2 3 public static void main(String[] args) { 4 5 int[] arr = new int[]{44,8,33,5,1,9,2}; 6 7 System.out.println(Arrays.toString(arr)); 8 9 merge1(arr); 10 11 System.out.println(Arrays.toString(arr)); 12 13 } 14 15 public static void merge1(int[] arr){ 16 17 18 int gap = 1 , len = arr.length; 19 20 while (gap < len){ 21 22 int start = 0; 23 24 while (start < len){ 25 //两个组合的起点 26 int s1 = start , s2 = start + gap ; 27 //终点 28 int e1 = s2 -1,e2 = s2 + gap - 1; 29 30 //数组长度不足，没有第二个组合了 31 if(s2 >= len){ 32 break; 33 } 34 35 //第二个组合长度小于第一个组合 36 if(e2 >= len){ 37 e2 = len - 1; 38 } 39 40 int left = start,right = e2; 41 42 int index = 0; 43 44 int size = right - left + 1; 45 int[] tmpArr = new int[size]; 46 47 while (s1 <= e1 && s2 <= e2){ 48 if(arr[s1] < arr[s2]){ 49 tmpArr[index] = arr[s1++]; 50 }else { 51 tmpArr[index] = arr[s2++]; 52 } 53 54 index++; 55 } 56 57 while (s1 <= e1){ 58 tmpArr[index++] = arr[s1++]; 59 } 60 61 while (s2 <= e2){ 62 tmpArr[index++] = arr[s2++]; 63 } 64 65 for (int i = left; i <= right ; i++) { 66 arr[i] = tmpArr[i - left]; 67 } 68 69 start = e2 + 1; 70 } 71 72 gap *= 2; 73 } 74 } 75 }
View Code
链表的归并排序实现
链表的数据结构
public class ListNode { int val; ListNode next; ListNode() { } ListNode(int val) { this.val = val; } ListNode(int val, ListNode next) { this.val = val; this.next = next; } }
链表跟数组相比，不能用下标访问，不知道长度，不能立即分割。
链表的赋值使用一个不存储数据的头节点，将数据往后插入。
跟数组不一样的是，链表需要真正的把节点一个个分割，在合并时再将节点连接起来。
自顶向下
不断使用快慢指针得出链表中间节点，将整个链表进行分割，一直分割到每个链表都只有一个节点时再合并
代码实现
1 public class ListNode { 2 int val; 3 ListNode next; 4 5 ListNode() { 6 } 7 8 ListNode(int val) { 9 this.val = val; 10 } 11 12 ListNode(int val, ListNode next) { 13 this.val = val; 14 this.next = next; 15 } 16 17 18 public static void main(String[] args) { 19 //头节点不存储数据 20 ListNode tou = new ListNode(); 21 ListNode tmp = tou; 22 int[] arr = new int[]{44,8,33,5,1,9,2}; 23 24 //借助临时节点扩充链表 25 for (int i = 0; i < 7; i++) { 26 tmp.next = new ListNode(); 27 tmp = tmp.next; 28 tmp.val = arr[i]; 29 } 30 31 ListNode sortedHead = sortList(tou.next); 32 33 while (sortedHead != null){ 34 System.out.print(sortedHead.val + ","); 35 sortedHead = sortedHead.next; 36 } 37 } 38 39 public static ListNode sortList(ListNode head) { 40 41 if(head == null || head.next == null){ 42 return head; 43 } 44 45 ListNode fast = head,slow = head; 46 47 //快指针走的步数 = 慢指针 * 2 48 /* 49 链表长度为偶数时，快指针到倒数第二个节点，慢指针到中间两个节点中的前一个 50 奇数时，快指针到最后一个节点，慢指针到中间节点 51 */ 52 //当快指针没法走下去时，说明慢指针已经到达了链表的中间节点 53 while (fast.next != null && fast.next.next != null){ 54 slow = slow.next; 55 fast = fast.next.next; 56 } 57 //第二部分的开始节点 58 ListNode mid = slow.next; 59 //分割出第一部分 60 slow.next = null; 61 62 //当链表的节点数量超过一个时，继续分割 63 if(head.next != null){ 64 head = sortList(head); 65 } 66 67 if(mid.next != null){ 68 mid = sortList(mid); 69 } 70 71 return merge(head,mid); 72 } 73 74 public static ListNode merge(ListNode l1,ListNode l2){ 75 76 ListNode pre = new ListNode(); 77 ListNode tou = pre; 78 while (l1 != null && l2 != null){ 79 pre.next = new ListNode(); 80 pre = pre.next; 81 82 if(l1.val > l2.val){ 83 pre.val = l2.val; 84 l2 = l2.next; 85 86 }else { 87 pre.val = l1.val; 88 l1 = l1.next; 89 } 90 } 91 //将剩余的节点在后面插入 92 pre.next = l1 == null ? l2 : l1; 93 94 return tou.next; 95 } 96 }
View Code
自底向上
要使用gap对链表分组，需要先计算链表的长度
与数组一样是两层循环，第一层gap不断倍增
第二层循环使用h作为不断遍历原链表的辅助节点，h1,h2确定两个要合并的链表，i1,i2确定链表的长度，然后合并
代码实现
1 package node; 2 3 public class ListNode { 4 int val; 5 ListNode next; 6 7 ListNode() { 8 } 9 10 ListNode(int val) { 11 this.val = val; 12 } 13 14 ListNode(int val, ListNode next) { 15 this.val = val; 16 this.next = next; 17 } 18 19 20 public static void main(String[] args) { 21 //头节点不存储数据 22 ListNode tou = new ListNode(); 23 ListNode tmp = tou; 24 int[] arr = new int[]{44,8,33,5,1,9,2}; 25 26 //借助临时节点扩充链表 27 for (int i = 0; i < 7; i++) { 28 tmp.next = new ListNode(); 29 tmp = tmp.next; 30 tmp.val = arr[i]; 31 } 32 33 34 ListNode sortedHead = merge1(tou.next); 35 36 while (sortedHead != null){ 37 System.out.print(sortedHead.val + ","); 38 sortedHead = sortedHead.next; 39 } 40 } 41 42 //自底向上的归并排序 43 public static ListNode merge1(ListNode head){ 44 45 int len = 0 , gap = 1; 46 ListNode tmp = head; 47 while (tmp != null){ 48 tmp = tmp.next; 49 len++; 50 } 51 52 ListNode pre,h,h1,h2 ; 53 ListNode tou = new ListNode(); 54 tou.next = head; 55 56 /* 57 每次循环指定一个头节点，从该节点开始根据gap去获取要比较的两部分的头节点 58 将两个部分的节点按顺序加入该节点 59 该节点指向还没排序的后续节点 60 */ 61 while (gap < len){ 62 pre = tou; 63 64 h = pre.next; 65 while (h != null){ 66 int i1 = gap; 67 h1 = h; 68 while (i1 > 0 && h != null){ 69 i1--; 70 h = h.next; 71 } 72 //第一部分已经到链表的终点 73 if(i1 > 0){ 74 break; 75 } 76 h2 = h; 77 int i2 = gap; 78 while (i2 > 0 && h != null){ 79 i2--; 80 h = h.next; 81 } 82 83 int l1 = gap; 84 //第二部分的长度 85 int l2 = gap - i2; 86 87 /* 88 不用新创建节点的方式 89 而是将现有节点插入到头节点后面 90 */ 91 while (l1 > 0 && l2 > 0){ 92 if(h1.val > h2.val){ 93 pre.next = h2; 94 h2 = h2.next; 95 l2--; 96 }else { 97 pre.next = h1; 98 h1 = h1.next; 99 l1--; 100 } 101 pre = pre.next; 102 } 103 104 pre.next = l1 == 0 ? h2 : h1; 105 //需要遍历完已经合并的两个链表，才能合并的后续链表 106 while (l1 > 0 || l2 > 0){ 107 pre = pre.next; 108 l1--; 109 l2--; 110 } 111 //将未排序的链表接在后面 112 pre.next = h; 113 } 114 115 gap *= 2; 116 } 117 return tou.next; 118 } 119 }
View Code
图
