归并排序（java）

介绍

归并排序采用的是分治法的思路。

使用递归将数组变成一个一个单一的数字，然后在不断合并。

合并的时候两个数组首先比较第一个那个比较小就放在合并后的数组中的第一个，然后+1继续比较下一个直到有一方已经结束，然后将另一方剩下的数字放入到合并后的数组。

如图所示(图摘自网络)

/***
	 * 归并排序（排序）O(n log n)
	 * @param nums
	 * @param low
	 * @param mid
	 * @param high
	 */
	 public  void merge(int[] nums, int low, int mid, int high) {  
	        int[] temp = new int[high - low + 1];  
	        int i = low;// 左指针  
	        int j = mid + 1;// 右指针  
	        int k = 0;  
	  
	        // 把较小的数先移到新数组中  
	        while (i <= mid && j <= high) {  
	            if (nums[i] < nums[j]) {  
	                temp[k++] = nums[i++];  
	            } else {  
	                temp[k++] = nums[j++];  
	            }  
	        }  
	  
	        // 把左边剩余的数移入数组  
	        while (i <= mid) {  
	            temp[k++] = nums[i++];  
	        }  
	  
	        // 把右边边剩余的数移入数组  
	        while (j <= high) {  
	            temp[k++] = nums[j++];  
	        }  
	  
	        // 把新数组中的数覆盖nums数组  
	        for (int k2 = 0; k2 < temp.length; k2++) {  
	            nums[k2 + low] = temp[k2];  
	        }  
	    }  
	/***
	 * 归并排序（递归）
	 * @param nums
	 * @param low
	 * @param high
	 * @return
	 */
	   public  int[] sort(int[] nums, int low, int high) {  
	        int mid = (low + high) / 2;  
	        if (low < high) {  
	            // 左边  
	            sort(nums, low, mid);  
	            // 右边  
	            sort(nums, mid + 1, high);  
	            // 左右归并  
	            merge(nums, low, mid, high);  
	        }  
	        return nums;  
	    }