题目描述

请你实现归并排序

思路

分而治之

先分，把整个数组分成长度为1的子数组 —— 递归实现

然后再把子数组合并，两者比较，谁小先放谁，放完了就把没放完的放入结果数组

代码实现

// 合并排序

// 输入

var __readline = require("readline-sync");
__readline.setDefaultOptions({ prompt: "" });
var readline = __readline.prompt;

console.log("请输入数组nums: ");
const nums = readline()
  .split(" ")
  .map((item) => parseInt(item));

const merge = (nums, leftIndex, rightIndex) => {
  // 分
  // 递归终止
  // 返回只包含有一个元素的数组
  if (leftIndex === rightIndex) {
    return [nums[leftIndex]];
  }

  let mid = leftIndex + Math.floor((rightIndex - leftIndex) / 2);
  // 左数组包含中间元素
  let left = merge(nums, leftIndex, mid);
  let right = merge(nums, mid + 1, rightIndex);

  // 存储结果的数组
  let arr = new Array(rightIndex - leftIndex + 1).fill(0);

  // 合
  let cur = 0,
    l = 0,
    r = 0;
  while (l < left.length && r < right.length) {
    if (left[l] <= right[r]) {
      arr[cur] = left[l];
      cur++;
      l++;
    } else {
      arr[cur] = right[r];
      cur++;
      r++;
    }
  }
  // 放没放完的
  while (l < left.length) {
    arr[cur] = left[l];
    cur++;
    l++;
  }
  while (r < right.length) {
    arr[cur] = right[r];
    cur++;
    r++;
  }
  return arr;
};

const res = merge(nums, 0, nums.length - 1);
console.log("排序后的数组为: ", res);