排序和搜索

动画：viualgo

排序

冒泡排序

最简单但性能并不好，不建议工作中使用，但面试可以用到，每次成员都和后一位成员对比，如果比它大则往后走，否则结束到下一位成员开始排序

const bubbleSort = <T extends number>(ary: Array<T>, sort: "asc" | "desc" = "asc") => {
  const len = ary.length - 1;
  for (let i = 0; i < len; i++) {
    // 核心 内圈循环每次最大循环次数都减少基于外圈一次
    // 因为排完一位成员，下一次的循环就要排除掉这个成员
    for (let j = 0; j < len - i; j++) {
      if (sort === "asc") {
        if (ary[j] > ary[j + 1]) {
          const temp = ary[j];
          ary[j] = ary[j + 1];
          ary[j + 1] = temp;
        }
      } else if (sort === "desc") {
        if (ary[j + 1] > ary[j]) {
          const temp = ary[j + 1];
          ary[j + 1] = ary[j];
          ary[j] = temp;
        }
      }
    }
  }
  return ary;
};

选择排序

与冒泡排序一样，性能都不是很好，找到数组中最小值放到第一位(此时这个第一位不再参与排序，使用剩余的成员继续寻找最小值)，找到第二小值 放到第二位，以此类推

const selectionSory = <T extends number>(ary: Array<T>) => {
  let len = ary.length - 1;
  for (let i = 0; i < len; i++) {
    let indexMin = i; //寻找最小值 第一次假设为0
    // 开始内圈循环 每次循环完成都排除一位成员
    // 这里核心就在内圈要保证 最后一位成员也能排序
    for (let j = i + 1; j <= len; j++) {
      if (ary[j] < ary[indexMin]) {
        indexMin = j;
      }
    }
    const temp = ary[i];
    ary[i] = ary[indexMin];
    ary[indexMin] = temp;
  }
  return ary;
};

插入排序

优于冒泡和选择，从第二位数开始往前对比，每次条件成立时都往前挪位并记录当前位置，每次都从记录的当前位置开始将后一位与前面的数进行比较，只要条件成立就进行位置交换

const insertionSort = <T extends number>(ary: Array<T>) => {
  for (let i = 1; i < ary.length; i++) {
    const temp = ary[i]; //记录当前的位置
    let j = i;
    while (j > 0) {
      // 每次都和前面的数进行比较，符合条件的就交换
      if (ary[j] < ary[j - 1]) {
        ary[j - 1] = ary[j];
      } else {
        //不符合条件就等于前面的数都比 当前这个位置的数要大或者小就结束内圈循环
        break;
      }
      j--; // 结束循环条件
    }
    ary[j] = temp; //将记录的值填充到一开始比较的地方
  }
};

归并排序

优于之前所有排序，可以在业务中实际用到的排序。其特点就是不用交换数组位置 先将数组每一位成员看作是一个个独立的有序数组，每次排序都会将一个固定的有序数组和后一位有序数组进行合并，合并的操作就是比较 数组的头部大小，更小或更大的一个先进入到新的数组，以此保证新数组中合并成功的操作结果也是有序的。就比如把321，拆分成3，2，1，然后将3，2进行对比，组成新数组[2,3],1,然后再比较头部2,1, 1更小，然后先入队，组成新数组变成 1,2,3 再之前的合并思路上还要做这个操作，先把两个数合并为有序数组，再把有序数组进行合并，直到所有有序数组合并完成

const mergeSort = <T extends number>(ary: Array<T>) => {
  // 递归函数 拆分数组
  const rec = (arr: T[]) => {
    if (arr.length === 1) return arr; //结束递归条件
    const mid = Math.floor(arr.length / 2);
    const left = arr.slice(0, mid);
    const right = arr.slice(mid, arr.length);

    let orderLeft = rec(left); //最终拆分完成有序数组
    let orderRight = rec(right);

    //合并数组
    const res: any[] = [];
    while (orderLeft.length || orderRight.length) {
      if (orderLeft.length && orderRight.length) {
        // 都有长度 就进行最小头部插入
        res.push(
          orderLeft[0] < orderRight[0] ? orderLeft.shift() : orderRight.shift()
        );
      } else if (orderLeft.length > 0) {
        res.push(orderLeft.shift());
      } else if (orderRight.length) {
        res.push(orderRight.shift());
      }
    }

    return res;
  };
  return rec(ary);
};

快速排序

和归并排序都是更好的排序方式，曾经就作为sort的方法实现 先选择一个基准，按照基准 将比它大和比它小的数值 放到它的前后，然后将前后子数组通过递归的形式将每一个数都作为一次基准重复这个过程，思路类似归并排序，但是借用解构的方式更简单

const quickSort = <T extends number>(ary: T[]) => {
  const rec = (arr: T[]) => {
    if (arr.length <= 1) return arr;
    const left: T[] = [];
    const right: T[] = [];
    const mid = arr[0];
    // 拆分左右两组
    for (let i = 1; i < arr.length; i++) {
      if (arr[i] < mid) {
        left.push(arr[i]);
      } else {
        right.push(arr[i]);
      }
    }
    // 递归拆分的再继续重复
    return [...rec(left), mid, ...rec(right)];
  };
  return rec(ary);
};

搜索

顺序搜索

非常低效但简单且最常用，按顺序遍历，找到相符合的就返回

const sequentialSearch = <T>(arr: T[], target: T) => {
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] === target) return i;
  }
  return -1;
};

二分搜索

如果数组是乱序的，你无法通过先排序再二分搜索来获得优于顺序搜索的性能 从数组中间开始，如果刚好是目标值就结束，否则判断目标值大于小于中间值，去那一半数组中查找，再重复这个过程，也就是去那一半再取中间值作判断 大前提，数组得是一个有序数组，乱序不行,排序后再用二分其性能就不优于顺序搜索了

const binarySearch = <T>(arr: T[], target: T) => {
  let low = 0;
  let high = arr.length - 1;
  while (low <= high) {
    // 取中间值
    const mid = Math.floor((low + high) / 2); //防止奇数
    const element = arr[mid];

    if (element < target) {
      //如果小于说明在后一半
      low = mid + 1; //最小下标变为后一半的起始下标
    } else if (element > target) {
      high = mid - 1; // 最大下标变为前一半的最后一位
    } else {
      return mid; // 否则就等于中间值 直接返回
    }
  }
  return -1;
};