排序算法-归并排序

归并排序是一种分治算法（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;
    }


}

时间复杂度分析

空间复杂度分析