排序算法

冒泡排序

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

选择排序

const selectionSort = arr => {
  for (let i = arr.length - 1; i > 0; i--) {
    let max = i
    for (let j = 0; j <= i; j++) {
      if (arr[j] > arr[max]) max = j
    }
    let temp = arr[i]
    arr[i] = arr[max]
    arr[max] = temp
  }
}

插入排序

const insertionSort = arr => {
  for (let i = 1; i < arr.length; i++) {
    let temp = arr[i]
    for (let j = i - 1; j >= 0 && arr[j] > temp; j--) {
      arr[j + 1] = arr[j]
    }
    arr[j + 1] = temp
  }
}

希尔排序

const shellSort = arr => {
  for (let gap = arr.length >> 1; gap > 0; gap >>= 1) {
    for (let i = gap; i < arr.length; i++) {
      let temp = arr[i]
      for (let j = i - gap; j >= 0 && arr[j] > temp; j -= gap) {
        arr[j + gap] = arr[j]
      }
      arr[j + gap] = temp
    }
  }
}

归并排序

const mergeSort = arr => {
  if (arr.length <= 1) return arr
  let middle = arr.length >> 1
  let left = arr.slice(0, middle)
  let right = arr.slice(middle)
  return merge(mergeSort(left), mergeSort(right))
}

const merge = (left, right) => {
  let result = []
  while (left.length > 0 && right.length > 0) {
    if (left[0] < right[0]) {
      result.push(left.shift())
    } else {
      result.push(right.shift())
    }
  }
  return result.concat(left, right)
}

堆排序

const heapSort = arr => {
  arr = [...arr]
  const swap = (i, j) => {
    let tmp = arr[i]
    arr[i] = arr[j]
    arr[j] = tmp
  }
  const max_heapify = (start, end) => {
    let dad = start
    let son = dad * 2 + 1
    if (son >= end) return
    if (son + 1 < end && arr[son] < arr[son + 1]) son++
    if (arr[dad] <= ar[son]) {
      swap(dad, son)
      max_heapify(son, end)
    }
  }
  let len = arr.length
  for (let i = (len >> 1) - 1; i >= 0; i--) max_heapify(i, len) // 找到最底部的父节点
  return arr
}

快速排序

const quickSort = arr => {
  const len = arr.length
  if (len < 2) return arr
  const pivot = arr[0],
    left = [],
    right = []
  for (let i = 1; i < len; i++) {
    const item = arr[i]
    item >= pivot && right.push(item)
    item < pivot && left.push(item)
  }
  return quickSort(left).concat(pivot, quickSort(right))
}