冒泡排序

通过重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成

function bubbleSort(arr) {
  for (let i = 0; i < arr.length - 1; i++) {
    for (let j = 0; j < arr.length - 1 - i; j++) {
      if (arr[j] > arr[j + 1]) {
        let temp = arr[j]
        arr[j] = arr[j + 1]
        arr[j + 1] = temp
      }
    }
  }
  return arr
}

插入排序

通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入

function insertion(arr) {
  for (let i = 1; i < arr.length; i++) {
    for (let j = 0; j < i; j++) {
      if (arr[j] > arr[i]) {
        arr.splice(j, 0, arr[i])
        arr.splice(i + 1, 1)
        break
      }
    }
  }
  return arr
}

快速排序

1. 在数据集之中，选择一个元素作为"基准"（pivot）。
2. 所有小于"基准"的元素，都移到"基准"的左边；所有大于"基准"的元素，都移到"基准"的右边。
3. 对"基准"左边和右边的两个子集，不断重复第一步和第二步，直到所有子集只剩下一个元素为止。

function quickSort(arr) {
  if (arr.length < 2) return arr

  const pivot = arr[0]
  const left = []
  const right = []

  for (let i = 1; i < arr.length; i++) {
    arr[i] >= pivot && right.push(arr[i])
    arr[i] < pivot && left.push(arr[i])
  }

  return quickSort(left).concat(pivot, quickSort(right))

上面的版本缺点是需要额外的存储器配置，以下为原地（in-place）分割方法

function quickSort(arr, left, right) {
  let len = arr.length
  let partitionIndex
  left = typeof left !== 'number' ? 0 : left
  right = typeof right !== 'number' ? len - 1 : right

  if (left < right) {
    partitionIndex = partition(arr, left, right)

    quickSort(arr, left, partitionIndex - 1)

    quickSort(arr, partitionIndex + 1, right)
  }

  return arr
}

function partition(arr, left, right) {
  let pivot = left
  let index = pivot + 1

  for (var i = index; i <= right; i++) {
    if (arr[i] < arr[pivot]) {
      swap(arr, i, index)
      index++
    }
  }

  swap(arr, pivot, index - 1)

  return index - 1;
}

function swap(arr, i, j) {
  var temp = arr[i]
  arr[i] = arr[j]
  arr[j] = temp
}

选择排序

首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕

function selectionSort(arr) {
  for (let i = 0; i < arr.length - 1; i++) {
    let min = i

    for (let j = i + 1; j < arr.length; j++) {
      if (arr[min] > arr[j]) {
        min = j
      }
    }

    let temp = arr[min]
    arr[min] = arr[i]
    arr[i] = temp
  }

  return arr
}

归并排序

递归法

1. 把 n 个元素看成 n 个长度为 l 的有序子表
2. 进行两两归并使记录关键字有序，得到 n/2 个长度为 2 的有序子表
3. 重复第 2 步直到所有记录归并成一个长度为 n 的有序表为止

function mergeSort(arr) {
  if (arr.length < 2) return arr

  function merge(left, right) {
    let final = []

    while (left.length && right.length) {
      final.push(left[0] <= right[0] ? left.shift() : right.shift())
    }
    return final.concat(left, right)
  }

  let mid = Math.floor(arr.length / 2)

  return merge(mergeSort(arr.slice(0, mid)), mergeSort(arr.slice(mid)))
}

计数排序

1. 统计数组中每个值为 i 的元素出现的次数，存入数组 C 的第 i 项
2. 反向填充目标数组：将每个元素 i 放在新数组的第 C[i] 项，每放一个元素就将 C[i] 减去 1

function countSort(arr) {
  let C = []

  for (let i = 0; i < arr.length; i++) {
    let num = arr[i]
    C[num] >= 1 ? C[num]++ : (C[num] = 1)
  }

  let sortArr = []

  for (let j = 0; j < C.length; j++) {
    if(C[j]){
      while(C[j]>0){
        sortArr.push(j)
        C[j] --
      }
    }
  }
  return sortArr
}