归并排序

简介

通过找到中间值，然后递归分别从左区间和右区间找中间值，最终将所给的值划分为单个块，然后进行一步一步回溯，分块由两个单个分区排序后合成一个，以此类推，最后实现有序排序

时间复杂度

最优 nlogn
最差 nlogn

空间复杂度

O(n)

优点

归并排序是一种稳定的排序算法，且适用于各种数据情况。它的主要优点是具有稳定的时间复杂度和良好的性能。尤其是在对链表等非随机访问的数据结构进行排序时，归并排序是一种常用的选择。

解题模版

		public void mergeSort(int[] nums) {if (nums == null || nums.length <= 1) {return;}mergeSort(nums, 0, nums.length - 1);}private void mergeSort(int[] nums, int left, int right) {if (left >= right) {return;}int mid = left + (right - left) / 2;mergeSort(nums, left, mid);mergeSort(nums, mid + 1, right);merge(nums, left, mid, right);}private void merge(int[] nums, int left, int mid, int right) {int[] temp = new int[right - left + 1];int i = left, j = mid + 1, k = 0;while (i <= mid && j <= right) {if (nums[i] <= nums[j]) {temp[k++] = nums[i++];} else {temp[k++] = nums[j++];}}while (i <= mid) {temp[k++] = nums[i++];}while (j <= right) {temp[k++] = nums[j++];}System.arraycopy(temp, 0, nums, left, temp.length);}

练习题

88. 合并两个有序数组

模版的后半部分，使用三个指针分别指向nums1，nums2，nums1的尾部，从而进行比较赋值，换位

class Solution {public void merge(int[] nums1, int m, int[] nums2, int n) {int p1 = m-1;int p2 = n-1;int p = m+n-1;while(p1>=0 && p2 >= 0){if(nums1[p1] >nums2[p2]){nums1[p] = nums1[p1];p1--;}else{nums1[p] = nums2[p2];p2--;}p--;}while(p2>=0){nums1[p] = nums2[p2];p2--;p--;}}
}

148. 排序链表
     同样的思路放在链表中，通过找到中间值，然后将其中间值下一个指向空值，将链表分成两个，以此类推，分成n份，之后在重新连接，最终形成一个新的排序好的链表

class Solution {public ListNode sortList(ListNode head) {if(head == null || head.next == null){return head;}ListNode mid = findMiddle(head);ListNode midNext = mid.next;mid.next = null;ListNode left = sortList(head);ListNode right = sortList(midNext);return merge(left,right);}private ListNode findMiddle(ListNode head){ListNode slow = head;ListNode fast = head.next;while(fast!= null && fast.next != null){slow = slow.next;fast = fast.next.next;}return slow;}private ListNode merge(ListNode l1,ListNode l2){ListNode dummy = new ListNode(-1);ListNode curr = dummy;while(l1 != null && l2 != null){if(l1.val <l2.val){curr.next = l1;l1 = l1.next;}else{curr.next  = l2;l2 = l2.next;}curr = curr.next;}if(l1 != null){curr.next = l1;}if(l2 != null){curr.next = l2;}return dummy.next;}
}

颜色分类
这个题可以i当做所有排序算法的练习题，使用归并排序，直接套用模版即可

public void sortColors(int []nums){if(nums == null || nums.length <=1){return;}mergeSort(nums,0,nums.length-1);}public void mergeSort(int [] nums,int left,int right){if(left>=right){return;}int mid = left+(right-left)/2;mergeSort(nums,left,mid);mergeSort(nums,mid+1,right);merge(nums,left,mid,right);}private void merge(int []nums,int left,int mid ,int right){int []temp = new int[right-left+1];int i = left,j = mid+1,k=0;while(i<=mid && j<= right){if(nums[i]<=nums[j]){temp[k++] = nums[i++];}else{temp[k++] = nums[j++];}}while(i<=mid){temp[k++] = nums[i++];}while(j<= right){temp[k++] = nums[j++];}System.arraycopy(temp,0,nums,left,temp.length);}
}