排序算法---归并排序 递归实现（Java）

排序算法---归并排序 递归实现（Java）

归并排序 递归实现 Java版
C/C++版本

递归拆分再合并

    private static void mergeSort(int[] nums, int start, int len) {
        if (len <= 1) return;     //只有1个元素就不用分割了
        int left = start;         //left为左半边起始下标
        int left_size = len / 2;  //左半边长度
        int right = left + left_size;       //右半边起始下标
        int right_size = len - left_size;   //右半边长度
        mergeSort(nums, left, left_size);   //递归分割左边
        mergeSort(nums, right, right_size); //递归分割右边
        merging(nums, left, left_size, right, right_size, len); //合并左右两边
    }

比较并排序

    private static void merging(int[] nums, int left, int left_size, int right, int right_size, int len) {
        int i = left;  //i为左半边指针
        int j = right; //j为右半边指针
        int k = 0;     //k为临时数组指针
        int[] temp = new int[len]; //临时数组，从小到大存储左右两边合并后的序列
        while (i < left + left_size && j < right + right_size) {
            if (nums[i] <= nums[j]) { //左小右大，将左边存入临时数组
                temp[k++] = nums[i++];
            } else {                  //左大右小，将右边存入临时数组
                temp[k++] = nums[j++];
            }
        }
        while (i < left + left_size) { //如果左边有剩余元素，按序添加到末尾
            temp[k++] = nums[i++];
        }
        while (j < right + right_size) { //如果右边有剩余元素，按序添加到末尾
            temp[k++] = nums[j++];
        }
        for (k = 0; k < len; k++) {
            nums[k + left] = temp[k]; //将排好序的临时数组替换nums的对应区间元素
        }
    }

测试

public static void main(String[] args) {
        int[] nums = {8, 5, 4, 2, 3, 9, 7, 6, 1, 0};
        System.out.println("排序前：" + Arrays.toString(nums));
        mergeSort(nums, 0, nums.length);
        System.out.println("排序后：" + Arrays.toString(nums));
    }

测试结果