排序算法

冒泡排序

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 (var 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 (var 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 mid = arr.length >> 1
  let left = arr.slice(0, mid)
  let right = arr.slice(mid)
  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 => {
    const swap = (i,j) => {
        let temp = arr[i]
        arr[i] = arr[j]
        arr[j] = temp
    }
    const maxHeapify = (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] <= arr[son]) {
            swap(dad,son)
            maxHeapify(son,end)
        }
    }
    let len = arr.length
    for(let i=(len>>1)-1;i>=0;i--) maxHeapify(i,len)// bottom parent node
    for (let i =len-1;i>0;i--) {
        swap(0, i); 
        maxHeapify(0, i);
    }
    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))
}

查找算法

二分查找

1. 基本形态
   一般来说，mid的溢出在js里还是挺难碰到的。如果有需要的场合的话，换成mid = low + Math.floor((high-low)/2)

function binarySearch (target, arr) {
  let low = 0, high = arr.length - 1, mid
  while (low <= high) {
    mid = Math.floor((high+low)/2)
    if (arr[mid] === target) {
      return mid
    } else if (arr[mid] < target) {
      low = mid + 1
    } else {
      high  = mid - 1
    }
  }
  return false
}

2. 查找目标值区域左边界

function binarySearch (target, arr) {
  let low = 0, high = arr.length - 1, mid
  while (low <= high) {
    mid = Math.floor((high+low)/2)
    if (arr[mid] >= target) {
      high = mid - 1
    } else {
      low = mid + 1
    }
  }
  if(low < A.length && A[low] == target)
    return low;
  else
    return false;
}