## 歸并排序 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))); } } ~~~