排序算法-归并排序

归并排序是一种分治算法（Divide and Conquer）。对于给定的一组数据，利用递归与分治技术将数据序列划分成为越来越小的半子表，在对半子表排序后，再用递归方法将排好序的半子表合并成为越来越大的有序序列。

核心思想

1. 分解（Divide）：将数组递归地分成两半，直到子数组长度为 1。

2. 合并（Merge）：将两个已排序的子数组合并成一个有序数组。

合并的过程

 代码实现

package Sort;import java.util.Arrays;public class MergeSort {public static void main(String[] args) {int[] res = getMergeSort(new int[]{8,5,7,9,1,6,3,4,2});for (int i = 0; i < res.length; i++) {System.out.print(res[i]+" ");}}//使用递归实现归并排序,升序public static int[] getMergeSort(int[] nums){if (nums.length<2) return nums;//切分数组，然后递归排序，并用merge合并int mid = nums.length/2;int[] leftNums = Arrays.copyOfRange(nums,0,mid);int[] rightNums = Arrays.copyOfRange(nums,mid,nums.length);return merge(getMergeSort(leftNums),getMergeSort(rightNums));}public static int[] merge(int[] leftNums,int[] rightNums){int[] result = new int[leftNums.length + rightNums.length];for (int index = 0, i = 0, j = 0; index < result.length ; index ++) {if (i>=leftNums.length){// 左边数组已经取完，那就完全取右边数组即可result[index] = rightNums[j++];} else if (j>=rightNums.length) { // 右边数组已经取完，那就完全取左边即可result[index] = leftNums[i++];} else if (rightNums[j] < leftNums[i]) { // 升序：右边数组的元素小于左边数组，取右边数组的值result[index] = rightNums[j++];}else { // 升序：左边数组的元素小于右边数组，取左边数组的值result[index] = leftNums[i++];}}return result;}}

时间复杂度分析

空间复杂度分析