leetcode-75 颜色分类

/**
 * @param {number[]} nums
 * @return {void} Do not return anything, modify nums in-place instead.
 */
var sortColors = function (nums) {
  // 冒泡排序
  // 排序需要的次数nums.length-1
  for (let i = 1; i < nums.length; i++) {
    // 方法1:小的冒到最前面
    for (let j = nums.length - 1; j >= i; j--) {
      if (nums[j] < nums[j - 1]) {
        [nums[j], nums[j - 1]] = [nums[j - 1], nums[j]];
      }
    }
    // 方法2:大的冒到最后面
    // for (let j = 0; j < nums.length - i; j++) {
    //   if (nums[j] > nums[j + 1]) {
    //     [nums[j], nums[j + 1]] = [nums[j + 1], nums[j]];
    //   }
    // }
  }
  return nums;
};
// console.log(sortColors([2, 0, 2, 1, 1, 0]));

var sortColors = function (nums) {
  // 选择排序
  // 排序次数nums.length-1
  // 方法1:每次选择最小的放在前面
  // for (let i = 0; i < nums.length - 1; i++) {
  //   let minIdx = i;
  //   for (let j = i + 1; j < nums.length; j++) {
  //     if (nums[j] < nums[minIdx]) {
  //       minIdx = j;
  //     }
  //   }
  //   [nums[minIdx], nums[i]] = [nums[i], nums[minIdx]];
  // }
  // 方法2:每次选择最大的放在后面
  for (let i = nums.length - 1; i >= 0; i--) {
    let maxIdx = i;
    for (let j = i - 1; j > 0; j--) {
      if (nums[j] > nums[maxIdx]) {
        maxIdx = j;
      }
    }
    [nums[maxIdx], nums[i]] = [nums[i], nums[maxIdx]];
  }
  return nums;
};
console.log(sortColors([2, 0, 2, 1, 1, 0]));

var sortColors = function (nums) {
  // 插入排序
  for (let i = 1; i < nums.length; i++) {
    // 排序多少轮
    const cur = nums[i];
    let j = i - 1;
    while (j >= 0 && nums[j] > cur) {
      // 后移
      nums[j + 1] = nums[j];
      j--;
    }
    nums[j + 1] = cur;
  }
  // console.log("🚀 ~ sortColors ~ nums:", nums);
  return nums;
};
// sortColors([2, 0, 2, 1, 1, 0]);

var sortColors = function (nums) {
  // 快速排序
  if (nums.length <= 1) return nums;
  const pivot = nums[0];
  const left = nums.slice(1).filter((x) => x < pivot);
  const right = nums.slice(1).filter((x) => x >= pivot);
  return [...sortColors(left), pivot, ...sortColors(right)];
};
// sortColors([2, 0, 2, 1, 1, 0]);
// console.log(
//   "🚀 ~ sortColors([2, 0, 2, 1, 1, 0]):",
//   sortColors([2, 0, 2, 1, 1, 0])
// );

var sortColors = function (nums) {
  // 归并排序
  function mergeSort(nums) {
    if (nums.length <= 1) return nums;
    const mid = Math.floor(nums.length / 2);
    const left = mergeSort(nums.slice(0, mid));
    const right = mergeSort(nums.slice(mid));
    return merge(left, right);
  }
  function merge(left, right) {
    const result = [];
    while (left.length && right.length) {
      result.push(left[0] < right[0] ? left.shift() : right.shift());
    }
    return result.concat(left, right);
  }
  return mergeSort(nums);
};
sortColors([2, 0, 2, 1, 1, 0]);
console.log(
  "🚀 ~ sortColors([2, 0, 2, 1, 1, 0]):",
  sortColors([2, 0, 2, 1, 1, 0])
);