冒泡排序

function buttleSort(arr) {
  const len = arr.length;
  if (len <= 1) return arr;
  for(let i = 0; i < len; i++) {
    let flag = true;
    // 从前往后冒泡，所以已经处理的数据不用再访问
    // 由于每次遍历都会访问 j + 1项；等于提前遍历了后一项
    // 所以终止条件是 len - i - 1；
    for(let j = 0; j < len - i - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
        flag = false;
      }
    }
    // 当前循环排序没有改变，flag=true，数组排序完成;
    if (flag) return arr;
  }
  return arr;
}

快排

/**
 * 
 * @param arr Number[] 待排序数组
 */
function quickSort(arr) {
  _quick(arr, 0, arr.length - 1);
  console.log(arr);
}
/**
 * 
 * @param arr Number[]
 * @param left Number 左边界
 * @param right Number 右边界
 * 对 arr[l...r] 部分进行快速排序
 */
function _quick(arr, left, right) {
  if (left >= right) {
    return;
  }
  let index = partition(arr, left, right);
  _quick(arr, left, index - 1);
  _quick(arr, index + 1, right);
}
/**
 * 
 * @param arr Number[]
 * @param left Number 左边界
 * @param right Number 右边界
 * @returns Number 索引值p，使得arr[left...p] < arr[p] < arr[p+1...right]
 * 对 arr[l...r] 部分进行快速排序
 */
function partition(arr, left, right) {
  let index = left;
  let target = arr[left];
  for(let i = left + 1; i <= right; i++) {
    if (arr[i] < target) {
      // 如果当前值小于基准值的话，就交换到index + 1的位置去
      swap(arr, i, index + 1);
      index++;
    }
  }
  // 把基准值交换至所有小于基准值的后边 既 index
  swap(arr, left, index);
  return index;
}
function swap(arr, i, j) {
  const temp = arr[i];
  arr[i] = arr[j];
  arr[j] = temp;
}

快排-三路

/**
 * 三路快排，将arr[l...r] 分为 < v; === v; > v 三部分
 *  之后递归的对 < v, > v 两部分三路快排
 * @param arr Number[]
 */
function quickSort(arr) {
  _quick(arr, 0, arr.length);
  return arr;
}
/**
 * @param arr Number[]
 * @param left Number 左边界
 * @param right Number 右边界
 * 对 arr[l...r] 部分进行快速排序
 */
function _quick(arr, l, r) {
  if (l >= r) return;
  let [lb, rb] = partition(arr, l, r);
  _quick(arr, l, lb);
  _quick(arr,rb, r);
}
/**
 * @param arr Number[]
 * @param left Number 左边界
 * @param right Number 右边界
 * @returns [lb, rb] Number[], 返回索引值[lb, rb]，使得arr[l...lb] < arr[lb] < arr[rb...r]
 * 对 arr[l...r] 部分进行快速排序
 */
function partition(arr, left, right) {
  let leftBound = left; // arr[left + 1...leftBound] < target
  let rigthBound = right + 1; // arr[rigthBound...r] > target
  let index = left + 1;
  let target = arr[left];
  while(index < rigthBound) {
    if (arr[index] < target) {
      swap(arr, index, leftBound + 1);
      leftBound++;
      index++
    } else if (arr[index] > target) {
      swap(arr, index, rigthBound - 1);
      rigthBound--;
    } else {
      index++
    }
  }
  swap(arr, left, leftBound);
  return [leftBound - 1, rigthBound];
}
function swap(arr, i, j) {
  const temp = arr[i];
  arr[i] = arr[j];
  arr[j] = temp;
}

快排-空间

function quickSort(arr) {
  const len = arr.length;
  if (len <= 1) return arr;
  const left = [];
  const right = [];
  const tag = arr[0];
  for(let i = 1; i < len; i++) {
    if (arr[i] < tag) {
      left.push(arr[i])
    } else {
      right.push(arr[i])
    }
  }
  return [...quickSort(left), tag, ...quickSort(right)]
}

选择排序

/**
 * 选择排序：每一次从待排序数组中，选择最小（大）的元素作为首元素，直到排完
 * @param arr number[] 待排序数组
 *
 * 1、有 n 个元素，由于内循环每次获取 i+1 的元素，因此外循环 n-1 次；
 * 2、选择最小（大）的元素，放到每次循环的第一位；
 * 3、重复过程至 n-1位
 */
function selectSort(arr: number[]) {
  const len = arr.length;
  if (len <= 1) return arr;
  for (let i = 0; i < len - 1; i++) {
    let temp = i;
    for (let j = i + 1; j < len; j++) {
      if (arr[j] < arr[temp]) {
        temp = j;
      }
    }
    if (temp !== i) {
      sawp(arr, temp, i);
    }
  }
  return arr;
}

插入排序

/**
 * 插入排序：通过构建有序数组、对于未排序的数据，在已排序的数组中从后往前比较，找到合适的位置插入；
 * @param arr number[] 待排序数组
 *
 * 1、从第一个元素开始，此元素被认定为已被排序；
 * 2、从第二个元素开始，在已排序的数组中从后往前比较；
 * 3、如果内循环 while 的 arr[pre] 元素大于外循环 for 的 arr[i] 元素，将该元素移至 pre+1;
 * 4、while循环内重复步骤3，直至找到 pre < 0 或 arr[pre] <= arr[i]；
 * 5、for循环；
 */
function insertSort(arr: number[]) {
  const len = arr.length;
  if (len <= 1) return arr;
  for (let i = 0; i < len; i++) {
    const cur = arr[i];
    let pre = i - 1;
    while (pre >= 0 && arr[pre] > cur) {
      sawp(arr, pre + 1, pre);
      pre--;
    }
    // 由于跳出 while 循环的条件为：pre < 0 或 arr[pre] <= cur
    // 所以当前循环的 arr[i] 应该插入至 pre + 1；
    // arr[pre + 1] = cur;
    // 因为 while 是在有序数组内进行循环，所以初始 arr[pre+1] 就是 cur
  }
  return arr;
}

归并排序

function mergeSort(arr: number[]) {
  const len = arr.length;
  if (len <= 1) return arr;
  const mid = Math.ceil(len / 2);
  const left = arr.splice(0, mid);
  const right = arr.splice(mid);
  const leftA = mergeSort(left);
  const rightA = mergeSort(right);
  return merge(leftA, rightA);
}
function merge(left: number[], right: number[]) {
  const res: any[] = [];
  while (left.length && right.length) {
    if (left[0] <= right[0]) {
      res.push(left.shift());
    } else {
      res.push(right.shift());
    }
  }
  while (left.length) {
    res.push(left.shift());
  }
  while (right.length) {
    res.push(right.shift());
  }
  return res;
}