## 归并排序 MergeSort * 空间复杂度：O(n) * 时间复杂度：O(nLogN) ## 思路描述 1. 取数组中间的下标mid 2. 先排左边部分sort(0,mid) 3. 再排右边部分sort(mid+1,len) 4. 如果left>=right,则退出 5. 合并数组，保证顺序 如下图：   ## 例子 ``` old:[13, 7, 4, 6, 9, 24, 12] merge:[13] + [7] = [7, 13] merge:[4] + [6] = [4, 6] merge:[7, 13] + [4, 6] = [4, 6, 7, 13] merge:[9] + [24] = [9, 24] merge:[9, 24] + [12] = [9, 12, 24] merge:[4, 6, 7, 13] + [9, 12, 24] = [4, 6, 7, 9, 12, 13, 24] result:[4, 6, 7, 9, 12, 13, 24]耗时:1ms ``` ## java实现 ~~~ public class MergeSort { public static void main(String[] args) { Stopwatch sw = Stopwatch.createStarted(); int[] nums = {13,7,4,6,9,24,12,5,5,6,3,4,7}; System.out.println("old:"+Arrays.toString(nums)); System.out.println("result:"+Arrays.toString(sort(nums))+"耗时:"+sw.elapsed(TimeUnit.MILLISECONDS)+"ms"); } public static int[] sort(int[] nums){ sort(nums,0,nums.length-1); return nums; } // 归并排序 public static void sort(int[] nums,int left,int right){ if (left >= right) { return; } // 取左右的中间下标 int mid = (left + right) / 2; // 先排左边的一半 sort(nums,left,mid); // 再排右边的一半 sort(nums,mid+1,right); // 如果中间的大于右边的才合并，本来就是小于的是满足顺序的，不需要做合并 //if(nums[mid] > nums[mid+1]){ // 合并左右2个数组 merge(nums,left,mid,right); //} } // 将arr[left...mid]和arr[mid+1...right]两部分进行归并 private static void merge(int[] nums,int left,int mid,int right){ int[] leftArr = Arrays.copyOfRange(nums,left,mid+1); int[] rightArr = Arrays.copyOfRange(nums,mid+1,right+1); int l = 0; int r = 0; int index = left; while(l <leftArr.length && r < rightArr.length){ nums[index++] = leftArr[l] <= rightArr[r] ? leftArr[l++] : rightArr[r++]; } while(l<leftArr.length){ nums[index++] = leftArr[l++]; } while (r<rightArr.length){ nums[index++] = rightArr[r++]; } System.out.println("merge:"+Arrays.toString(leftArr)+" + "+Arrays.toString(rightArr) + " = " + Arrays.toString(Arrays.copyOfRange(nums,left,right+1))); } } ~~~