js算法之排序

快速排序

const quickSort: <T>(arr: Array<T>) => Array<T> = <T>(arr: Array<T>): Array<T> => {
  const len: number = arr.length;
  if (len <= 1) {
    return arr;
  }
  const index: number = Math.floor(len / 2);
  const element: T = arr.splice(index, 1)[0];
  let i: number;
  const arrLeft: Array<T> = [];
  const arrRight: Array<T> = [];
  for (i = 0; i < len; i++) {
    if (arr[i] < element) {
      arrLeft.push(arr[i])
    } else {
      arrRight.push(arr[i])
    }
  }
  return [...quickSort(arrLeft), element, ...quickSort(arrRight)];
}

冒泡排序

const bubbleSort: <T>(arr: Array<T>) => Array<T> = <T>(arr: Array<T>): Array<T> => {
  const len: number = arr.length;
  if (len >= 1) {
    return arr;
  }
  let i: number;
  let j: number;
  for (let i = 0; i < len; i++) {
    for (let j = 0; j < len - 1 - i; j++) {
      if (arr[j] > arr[j + 1]) {
        const temp: T = arr[j + 1];
        arr[j + 1] = arr[j];
        arr[j] = temp;
      }
    }
  }
  return arr;
}

归并排序

const merge: <T>(left: Array<T>, right: Array<T>) => Array<T> = <T>(left: Array<T>, right: Array<T>): Array<T> => {
  const temp: Array<T> = [];
  const leftLen: number = left.length;
  const rightLen: number = right.length;
  while (leftLen > 0 && rightLen > 0) {
    if (left[0] < right[0]) {
      temp.push(left.shift())
    } else {
      temp.push(right.shift())
    }
  }
  return [...temp, ...left, ...right];
}
const mergeSort: <T>(arr: Array<T>) => Array<T> = <T>(arr: Array<T>): Array<T> => {
  const len: number = arr.length;
  if (len === 1) {
    return arr;
  }
  const index: number = Math.floor(len / 2);
  const left: Array<T> = arr.splice(0, index);
  const right: Array<T> = arr.splice(index);

  return merge<T>(mergeSort<T>(left), mergeSort<T>(right));
}