乐趣区

关于算法:理解归并排序

jiezi

归并排序就是对数组的左半边和右半边别离排序，而后再合并两个有序数组。

  • 归并排序的过程能够在逻辑上形象成一棵二叉树，树上的每个节点的值能够认为是 nums[lo..hi]，叶子节点的值就是数组中的单个元素
  • 而后，在每个节点的后序地位（左右子节点曾经被排好序）的时候执行 merge 函数，合并两个子节点上的子数组
  • 这个 merge 操作会在二叉树的每个节点上都执行一遍，执行程序是二叉树后序遍历的程序

一句话总结，归并排序实际上就是先对数组一直进行二分，分到只有一个元素为止，此时 merge 办法开始发挥作用，将两个元素为一组，合并为长度为 2 的有序数组，再将两个长度为 2 的有序数组为一组，合并为长度为 4 的有序数组，以此类推 

class Merge {

  // 用于辅助合并有序数组（不能原地合并，须要借助额定空间）private static int[] temp;

  public static void sort(int[] nums) {
    // 防止递归中频繁调配和开释内存可能产生的性能问题
    // 提前给辅助数组开拓内存空间
    temp = new int[nums.length];
    // 原地批改的形式对整个数组进行排序
    sort(nums, 0, nums.length - 1);
  }

  // 定义：将子数组 nums[lo..hi] 进行排序
  private static void sort(int[] nums, int lo, int hi) {if (lo == hi) {
      // 单个元素不必排序
      return;
    }
    // 这样写是为了避免溢出，成果等同于 (hi + lo) / 2
    // 留神：对于无奈整除的状况，Java 中 int 类型会主动向下取整
    int mid = lo + (hi - lo) / 2;
    // 先对左半局部数组 nums[lo..mid] 排序
    sort(nums, lo, mid);
    // 再对右半局部数组 nums[mid+1..hi] 排序
    sort(nums, mid + 1, hi);
    // 将两局部有序数组合并成一个有序数组
    merge(nums, lo, mid, hi);
  }

  // 将 nums[lo..mid] 和 nums[mid+1..hi] 这两个有序数组合并成一个有序数组
  private static void merge(int[] nums, int lo, int mid, int hi) {// 先把 nums[lo..hi] 复制到辅助数组中
    // 以便合并后的后果可能间接存入 nums
    for (int i = lo; i <= hi; i++) {temp[i] = nums[i];
    }

    // 数组双指针技巧，合并两个有序数组
    // i => 左半边数组起始下标
    // j => 右半边数组起始下标
    int i = lo, j = mid + 1;
    for (int p = lo; p <= hi; p++) {if (i == mid + 1) {
        // 左半边数组已全副被合并，只需把右半边数组合并过去即可
        nums[p] = temp[j++];
      } else if (j == hi + 1) {
        // 右半边数组已全副被合并，只需把左半边数组合并过去即可
        nums[p] = temp[i++];
      } else if (temp[i] > temp[j]) {
        // 将较小的元素合入，同时下标后退一位，此时是升序
        // 只有将 > 改为 < 就能够把后果改为降序
        nums[p] = temp[j++];
      } else {nums[p] = temp[i++];
      }
    }
  }
}

归并排序工夫复杂度为 O(nlogn)

退出移动版