归并排序
：
归并排序：
思路：分而治之
采用的是递归
主要是两步，先把数组分成两半（merge），再把这两半合并成有序的数组（mergeTwoSortedArrays）。
temp参数的作用是接收排序后的数组，然后再把值一一付给原数组，如果不加这个参数，我们就需要重复开辟空间，或者使用static。
这里有一个小窍门，如果两数组分别排序后nums[mid] <= nums[mid + 1]，那么就不需要执行mergeTwoSortedArrays。
public static int[] sortArray(int[] nums) {
//归并排序
int temp[] = new int[nums.length];
int start = 0;
int end = nums.length-1;
merge(nums, start, end, temp);
return nums;
}
public static void merge(int[] nums,int start,int end,int[] temp) {
if(start>=end) {
return;
}
int mid =(start+end)/2;
merge(nums,start,mid,temp);
merge(nums, mid+1, end, temp);
if (nums[mid] <= nums[mid + 1]) {
return;
}
mergeTwoSortedArrays(nums,start,end,temp);
}
private static void mergeTwoSortedArrays(int[] nums, int start, int end, int[] temp) {
// TODO Auto-generated method stub
int mid = (start+end)/2;
int i = start;
int j = mid+1;
int current = start;
while(i<=mid&&j<=end) {
if(nums[i]<=nums[j]) {
temp[current++] = nums[i++];
}else {
temp[current++] = nums[j++];
}
}
while(i<=mid) {
temp[current] = nums[i++];
current++;
}
while(j<=end) {
temp[current] = nums[j++];
current++;
}
for(int k=start;k<=end;k++){
nums[k]=temp[k];
}
}
作者：mengjiayuyongit
