手写算法: 排序数组

912. 排序数组

解法一：快速排序

var sortArray = function(nums) {
  if (nums.length <= 1) return nums;
  const idx = Math.floor(nums.length / 2);
  const pivot = nums.splice(idx, 1)[0];

  let left = [],
    right = [];
  for (let i = 0; i < nums.length; i++) {
    if (num[i] < pivot) {
      left.push(num[i]);
    } else {
      right.push(num[i]);
    }
  }
  return sortArray(left).concat([pivot], sortArray(right));
};

错误示范：将 nums.length 用变量缓存起来！！因为在拿基准数的时候，用splice是截取数组，此时原数组的长度会改变。如果用变量的话，就会有问题。

解法二：冒泡排序

var sortArray = function(nums) {
  for (let i = 0; i < nums.length; i++) {
    for (let j = 0; j < nums.length - 1 - i; j++) {
      if (nums[j] > nums[j + 1]) {
        let temp = nums[j + 1];
        nums[j + 1] = nums[j];
        nums[j] = temp;
      }
    }
  }
  return nums;
};

注意 ⚠️：第二层嵌套 for 的时候，每次遍历最大的数已经在最后一个了，所以长度需要减去 i

解法三：选择排序

var sortArray = function(nums) {
  const len = nums.length;
  let minIndex, temp;
  for (let i = 0; i < len; i++) {
    minIndex = i;
    for (let j = i; j < len; j++) {
      if (nums[minIndex] > nums[j]) {
        minIndex = j;
      }
    }
    temp = nums[minIndex];
    nums[minIndex] = nums[i];
    nums[i] = temp;
  }
  return nums;
};

注意点

选择排序是从待排序的数组中，选出最大或最小的元素，放到已排序的末尾，重复至排序完成。

{
  // 这一串换位置的代码，即便当前数组已经按照顺序排列完成了，依次会重复走这段代码，直到数组循环完后。
  temp = nums[minIndex];
  nums[minIndex] = nums[i];
  nums[i] = temp;
}

解法四：插入排序

像打扑克牌一样，左手拿牌，右手抓牌，每次将右手抓的牌插入左手的正确位置中，左手的牌总是排序好的。【一直拿当前这张牌，跟左手的牌依次对比，调换位置】

一般在输入规模大于 1000 的场合下不建议使用插入排序。

var sortArray = function(nums) {
  for (let i = 1; i < nums.length; i++) {
    let temp = nums[i];
    let j = i - 1;
    for (; j >= 0; j--) {
      if (temp >= nums[j]) break;
      nums[j + 1] = nums[j];
    }
    nums[j + 1] = temp;
  }
  return nums;
};

手写题: 实现 ThisParameterType<T>

14. 实现 ThisParameterType<T>

// your code here, please don't use ThisParameterType<T> in your code
type MyThisParameterType<T> = T extends (this: infer R) => any ? R : never;

分析

1. 看到这样的题，首先想到类型推断 infer

2. typeof Foo 拿到的是函数的类型结构，可以看到 Foo 函数，有入参 this，类型是个对象结构

3. 根据题意分析，需要返回 this 的 type，如果没有的话则使用 unknown

4. inter R推断 R 的类型， () => any 返回的类型不是 any 的话，那么就返回个never【never 会抛出错误】