arr.sort() // 默认排序，会将元素转换为字符串，然后比较它们的 UTF-16 代码单元值实现排序
arr.sort((a, b) => { return a - b }) // 自定义排序，递增
arr.sort((a, b) => { return b - a }) // 自定义排序，递减
复制代码

export function bubbleSort(arr) {
  const len = arr.length;
  // 外层遍历负责从头到尾进行比较
  for (let i = 0; i < len; i++) {
    for (let j = 0; j < len; j++) {
      // 若相邻元素前面的数比后面的大，则交换
      if (arr[j] > arr[j + 1]) {
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
      }
    }
  }
  return arr;
}
复制代码

export function bubbleSort(arr) {
  const len = arr.length;
  // 外层循环负责从前往后遍历数组元素，每次遍历时找出比它小的和它替换
  for (let i = 0; i < len; i++) {
      // 当内层循环遍历完一次数组，就能找出本次遍历中的最小值，并把最小值移动到数组头部
       for (let j = i + 1; j < len; j++) {
           // 只要当前头部元素大于后续任意元素就直接交换位置
           if (arr[i] > arr[j]) {
               [arr[i], arr[j]] = [arr[j], arr[i]]
           }
       }
   }
  return arr;
}
复制代码

// 外层遍历负责从头到尾进行比较
  for (let i = 0; i < len; i++) {
    for (let j = 0; j < len; j++) {
      // 若相邻元素前面的数比后面的大，则交换
      if (arr[j] > arr[j + 1]) {
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
      }
    }
  }
复制代码

export function betterBubbleSort(arr) {
  const len = arr.length;
  for (let i = 0; i < len; i++) {
    // len - i 避免遍历到已经有序的部分
    for (let j = 0; j < len - i; j++) {
      if (arr[j] > arr[j + 1]) {
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
      }
    }
  }
  return arr;
}
复制代码

export function bestBubbleSort(arr) {
  const len = arr.length;
  // 定义 isOrder 用于标识数组是否有序，默认是有序的
  let isOrder = true;
  for (let i = 0; i < len; i++) {
    for (let j = 0; j < len - i; j++) {
      if (arr[j] > arr[j + 1]) {
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
        isOrder = false;
      }
    }
    // isOrder 的值没有发生更改，意味着数组是有序的，不需要进行额外排序
    if (isOrder) return arr;
  }
  return arr;
}
复制代码

export function selectSort(arr) {
  const len = arr.length;
  // 定义最小值索引
  let minIdx;
  for (let i = 0; i < len; i++) {
    // 将每次循环索引 i 认为是本次遍历的 最小值索引 minIdx
    minIdx = i;
    // i、j 定义为本次需要遍历区间的 边界，i 为 左边界，j 为 右边界
    for (let j = i; j < len; j++) {
      if (arr[j] < arr[minIdx]) {
        minIdx = j;
      }
    }
    // 若当前 minIdx 和 i 不相等，则表明当前已经找到新的最小的元素，则进行交换
    if (minIdx !== i) {
      [arr[i], arr[minIdx]] = [arr[minIdx], arr[i]];
    }
  }
  return arr;
}
复制代码

export function insertSort(arr) {
  const len = arr.length;
  // temp 用来保存当前需要插入的元素
  let temp;
  // i = 1 即默认第一位元素（即 i = 0）是有序的
  for (let i = 1; i < len; i++) {
    // j 用于帮助 temp 寻找自己应该有的定位
    let j = i;
    temp = arr[i];
    // j 此时为有序区域的 右边界，因此 j - 1 就是有序区域中的内容
    // 判断 j 前面一个元素是否比 temp 大
    while (arr[j - 1] > temp) {
      // 如果是，则将 j 前面的一个元素后移一位，为 temp 让出位置
      arr[j] = arr[j - 1];
      j--;
    }
    // 循环让位，最后得到的 j 就是 temp 的正确索引
    arr[j] = temp;
  }
  return arr;
}
复制代码

// 计算分割点 
const mid = Math.floor(len / 2) 
// 递归分割左子数组，然后合并为有序数组 
const leftArr = mergeSort(arr.slice(0, mid)) 
// 递归分割右子数组，然后合并为有序数组 
const rightArr = mergeSort(arr.slice(mid,len))
复制代码

export function mergeSort(arr) {
  const len = arr.length;
  // 定义递归边界
  if (len <= 1) {
    return arr;
  }
  // 获取中间元素的索引值
  const midIdx = Math.floor(len / 2);
  // 根据中间索引 midIdx 划分左右两个子数组，即进行了 分割
  const left = mergeSort(arr.slice(0, midIdx));
  const right = mergeSort(arr.slice(midIdx, len));
  // 将左右两个子数组进行有序的合并
  return mergeArr(left, right);
}
// 通过双针指针合并两个有序数组
function mergeArr(arr1, arr2) {
  const len1 = arr1.length;
  const len2 = arr2.length;
  // 定义 l r 指针，分别指向 arr1 arr2 中的元素
  let i = 0,
    j = 0;
  // 定义结果集
  const res: any[] = [];
  // 循环合并数组，直到至少一个数组被遍历完
  while (i < len1 && j < len2) {
    if (arr1[i] > arr2[j]) {
      res.push(arr2[j]);
      j++;
    } else {
      res.push(arr1[i]);
      i++;
    }
  }
  // 判断具体是哪个数组被遍历完，将另一个数组直接进行合并即可
  if (i < len1) {
    return res.concat(arr1.slice(i));
  } else {
    return res.concat(arr2.slice(j));
  }
}
复制代码

export function quickSort(arr, left = 0, right = arr.length - 1) {
  // 递归边界
  if (arr.length > 1) {
    // lineIndex 表示下一次划分左右子数组的索引位
    const lineIndex = partition(arr, left, right);
    // 如果左边子数组的长度不小于 1，则递归快排这个子数组
    if (left < lineIndex - 1) {
      // 左子数组以 lineIndex-1 为右边界
      quickSort(arr, left, lineIndex - 1);
    }
    // 如果右边子数组的长度不小于1，则递归快排这个子数组
    if (right > lineIndex) {
      // 右子数组以 lineIndex 为左边界
      quickSort(arr, lineIndex, right);
    }
  }
  return arr;
}
// 以基准值为轴心，划分左右子数组的过程
function partition(arr, left, right) {
  // 基准值默认取中间位置的元素
  let pivotValue = arr[Math.floor(left + (right - left) / 2)];
  // 初始化左右指针
  let i = left;
  let j = right;
  // 当左右指针不越界时，循环执行以下逻辑
  while (i <= j) {
    // 左指针所指元素若小于基准值，则右移左指针
    while (arr[i] < pivotValue) {
      i++;
    }
    // 右指针所指元素大于基准值，则左移右指针
    while (arr[j] > pivotValue) {
      j--;
    }
    // 若 i<=j，则意味着基准值【左边】存在较大元素 或【右边】存在较小元素
    // 交换两个元素确保左右两侧有序
    if (i <= j) {
      [arr[i], arr[j]] = [arr[j], arr[i]];
      i++;
      j--;
    }
  }
  // 返回左指针索引作为下一次划分左右子数组的依据
  return i;
}
复制代码

// Insertion sort is faster for short arrays.
  if (to - from <= 10) {
    // 插入排序
    InsertionSort(a, from, to);
    return;
  }
  ...
  if (to - high_start < low_end - from) {
    // 快速排序
    QuickSort(a, high_start, to);
    to = low_end;
  } else {
    QuickSort(a, from, low_end);
    from = high_start;
  }
复制代码

while (remaining != 0) {
    let currentRunLength: Smi = CountAndMakeRun(low, low + remaining);
    // If the run is short, extend it to min(minRunLength, remaining).
    if (currentRunLength < minRunLength) {
      const forcedRunLength: Smi = SmiMin(minRunLength, remaining);
      // 二分插入排序
      BinaryInsertionSort(low, low + currentRunLength, low + forcedRunLength);
    }
    ...
    // 归并
    MergeCollapse(context, sortState);
}