运用分治法将数组分成一些小的片段然后递归，再将分的阶段得到的答案"修补"在一起，即分而治之。
代码如下：
/**
* 归并排序
* 时间复杂度 一次排序时间复杂度为n,进行logn次 --O(nlogn)
*/
public class MergeSort {
public static void main(String[] args) {
int[] nums = new int[10];
Random random = new Random();
for (int i = 0; i < 10; i++) {
nums[i] = random.nextInt(100);
}
System.out.println(Arrays.toString(nums));
System.out.println("------------");
mergeSort(nums, 0, nums.length-1); //调用方法
System.out.println(Arrays.toString(nums));
}
private static void mergeSort(int[] nums, int l, int r) {
//分
if (l < r) {
//拆半分组
int mid = (l + r) / 2;
mergeSort(nums, l, mid);//左
mergeSort(nums, mid + 1, r);//右
//治
merge(nums, l, mid, r);
}
}
private static void merge(int[] nums, int l, int mid, int r) {
int[] temp = new int[r - l + 1]; //临时数组
int i = l; //左序列指针
int j = mid+1; //右序列指针
int k = 0; //temp指针
while (i <= mid && j <= r) {
if (nums[i] <= nums[j]) {
temp[k++] = nums[i++];
} else {
temp[k++] = nums[j++];
}
}
//将剩余元素填充入temp
while (i <= mid) {
temp[k++] = nums[i++];
}
while (j <= r) {
temp[k++] = nums[j++];
}
//取出temp元素填入原数组
k = 0;
while (l <= r) {
nums[l++] = temp[k++];
}
}
}
