No.912 排序数组

给你一个整数数组 nums，请你将该数组升序排列。

示例 1：

输入：nums = [5,2,3,1]
输出：[1,2,3,5]

示例 2：

输入：nums = [5,1,1,2,0,0]
输出：[0,0,1,1,2,5]

提示：

• 1 <= nums.length <= 5 * 10^4
• -5 * 10^4 <= nums[i] <= 5 * 10^4

解题思路

实现

冒泡排序

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var sortArray = function (nums) {
  let length = nums.length;
  for (let i = 0; i < length; i++) {
    for (let j = 0; j < length - 1 - i; j++) {
      if (nums[j] > nums[j + 1]) {
        [nums[j], nums[j + 1]] = [nums[j + 1], nums[j]];
      }
    }
  }
  return nums;
};

选择排序

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var sortArray = function (nums) {
  let length = nums.length;
  for (let i = 0; i < length; i++) {
    let min = i;
    for (let j = i; j < length; j++) {
      if (nums[min] > nums[j]) {
        min = j;
      }
    }
    if (min !== i) {
      [nums[i], nums[min]] = [nums[min], nums[i]];
    }
  }
  return nums;
};

插入排序

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var sortArray = function (nums) {
  let length = nums.length;
  let j, temp;
  for (let i = 1; i < length; i++) {
    j = i;
    temp = nums[i];
    while (j > 0 && nums[j - 1] > temp) {
      nums[j] = nums[j - 1];
      j--;
    }
    nums[j] = temp;
  }
  return nums;
};

归并排序

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var sortArray = function (nums) {
  const dfs = (l, r) => {
    let i = 0;
    let j = 0;
    let res = [];
    while (i < l.length && j < r.length) {
      if (l[i] < r[j]) {
        res.push(l[i++]);
      } else {
        res.push(r[j++]);
      }
    }
    return res.concat(i < l.length ? l.slice(i) : r.slice(j));
  };
  let length = nums.length;
  if (length > 1) {
    let midIndex = length >> 1;
    nums = dfs(
      sortArray(nums.slice(0, midIndex)),
      sortArray(nums.slice(midIndex, length))
    );
  }
  return nums;
};

希尔排序

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var sortArray = function (nums) {};

快速排序

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var sortArray = function (nums) {};

堆排序

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var sortArray = function (nums) {};