image.png
image.png

代码实现

  1. package com.test.clickhouse.config;
  3. import java.util.Arrays;
  5. class Merge {
  7.     // 用于辅助合并有序数组
  8.     private static int[] temp;
  10.     public static void sort(int[] nums) {
  11.         // 先给辅助数组开辟内存空间
  12.         temp = new int[nums.length];
  13.         // 排序整个数组（原地修改）
  14.         sort(nums, 0, nums.length - 1);
  15.     }
  17.     // 定义：将子数组 nums[lo..hi] 进行排序
  18.     private static void sort(int[] nums, int lo, int hi) {
  19.         System.out.println("sort... nums is " + Arrays.toString(nums) + ",lo =" + lo + ",hi=" + hi);
  20.         if (lo == hi) {
  21.             // 单个元素不用排序
  22.             return;
  23.         }
  24.         // 这样写是为了防止溢出，效果等同于 (hi + lo) / 2
  25.         int mid = lo + (hi - lo) / 2;
  26.         // 先对左半部分数组 nums[lo..mid] 排序
  27.         sort(nums, lo, mid);
  28.         // 再对右半部分数组 nums[mid+1..hi] 排序
  29.         sort(nums, mid + 1, hi);
  30.         // 将两部分有序数组合并成一个有序数组
  31.         merge(nums, lo, mid, hi);
  32.     }
  34.     // 将 nums[lo..mid] 和 nums[mid+1..hi] 这两个有序数组合并成一个有序数组
  35.     private static void merge(int[] nums, int lo, int mid, int hi) {
  36.         System.out.println(
  37.                 "nums is " + Arrays.toString(nums) + ",temp is " + Arrays.toString(temp) + ",lo is " + lo + ",mid=" +
  38.                 mid + ",hi=" + hi);
  39.         int[] temp1 = new int[nums.length];
  40.         int i = lo;
  41.         int j = mid + 1;
  42.         int index = lo;
  43.         while (i <= mid && j <= hi) {
  44.             System.out.println(
  45.                     "whie ...nums is " + Arrays.toString(nums) + ",temp is " + Arrays.toString(temp1) + ",lo is " + lo +
  46.                     ",mid=" + mid + ",hi=" + hi + ",i=" + i + ",j=" + j);
  47.             if (nums[i] > nums[j]) {
  48.                 temp1[index] = nums[j];
  49.                 j++;
  50.             } else {
  51.                 temp1[index] = nums[i];
  52.                 i++;
  53.             }
  54.             index++;
  55.             System.out.println(
  56.                     "whie ...nums is " + Arrays.toString(nums) + ",temp is " + Arrays.toString(temp1) + ",lo is " + lo +
  57.                     ",mid=" + mid + ",hi=" + hi + ",i=" + i + ",j=" + j);
  58.             System.out.println("************************************************");
  59.         }
  60.         while (i <= mid) {
  61.             temp1[index] = nums[i];
  62.             i++;
  63.             index++;
  64.         }
  65.         while (j <= hi) {
  66.             temp1[index] = nums[j];
  67.             j++;
  68.             index++;
  69.         }
  70.         System.out.println(
  71.                 "whie ...nums is " + Arrays.toString(nums) + ",temp is " + Arrays.toString(temp1) + ",lo is " + lo +
  72.                 ",mid=" + mid + ",hi=" + hi + ",i=" + i + ",j=" + j);
  73.         System.out.println("====================");
  74.         for (int k = lo; k <= hi; k++) {
  75.             nums[k] = temp1[k];
  76.         }
  77.     }
  79.     public static void main(String[] args) {
  80.         // int[] ints = {5, 2, 3, 1};
  81.         int[] ints = {8, 4, 9, 10, 11, 12, 5, 7, 1, 3, 6, 2};
  82.         // int[] ints = {8,4,5,7,1,3,6,2};
  83.         // int[] ints = {5, 1, 1, 2,0,0};
  84.         sort(ints);
  85.         System.out.println(Arrays.toString(ints));
  86.     }
  87. }

参考

https://blog.csdn.net/weixin_45857153/article/details/110474615