Quick Sort

const swap = <T>(arr: T[], left: number, right: number): void => {

  const temp: T = arr[left];

  arr[left] = arr[right];
  arr[right] = temp;

  return;
};

const quickSort = <T>(arr: T[], left: number = 0, right: number = arr.length - 1): void => {

  if (left > right) {
    return;
  }

  let lp: number = left; // 左游标
  let rp: number = right; // 右游标

  const pivot: T = arr[left]; // 基准数选择最左侧的数

  while (lp != rp) {

    // 在游标不越过彼此的情况下，从右向左，寻找下一个比基准数小的数
    while (lp < rp && arr[rp] >= pivot) {
      rp--;
    }
    // 在游标不越过彼此的情况下，从左向右，寻找下一个比基准数大的数
    while (lp < rp && arr[lp] <= pivot) {
      lp++;
    }

    // 在游标不越过彼此的情况下，交换两个数，使比基准数小的右侧数放置于油表左侧
    if (lp < rp) {
      swap(arr, lp, rp)
    }
  }

  // 交换基准数
  arr[left] = arr[lp];
  arr[lp] = pivot;

  // 递归
  quickSort(arr, left, lp - 1);
  quickSort(arr, lp + 1, right);

  return;
};