排序算法

• 冒泡排序 (bubbleSort)

  const bubbleSort = arr => {
      let swapped = false
      const a = [...arr]
      for(let i = 1; i < a.length; i ++) {
          swapped = false
          for(let j = 0; j < a.length - i; j ++) {
              if(a[j + 1] < a[j]) {
                  [a[j], a[j + 1]] = [a[j + 1], a[j]]
                  swapped = true
              }
          }
          if(!swapped) return a
      }
      return a
  }
  

• 插入排序 (insertionSort)

  const insertionSort = arr => 
      arr.reduce((acc, x) => {
          if(!acc.length) return [x]
          acc.some((y, idx) => {
              if(x <= y) {
                  acc.splice(idx, 0, x)
                  return true
              }
              if(x > y && idx === acc.length - 1) {
                  acc.splice(idx + 1, 0, x)
                  return true
              }
              return false
          })
          return acc
      }, [])
  

• 选择排序 (selectionSort)

  const selectionSort = arr => {
      const a = [...arr]
      for(let i = 0; i < a.length; i ++) {
          // acc为min值下标
          const minIdx = a
              .slice(i + 1)
              .reduce((acc, val, j) => val < a[acc] ? j + i + 1 : acc, i)
          if(minIdx !== i) [a[i], a[minIdx]] = [a[minIdx], a[i]]
      }
      return a
  }
  

• 快速排序 (quickSort)

  const quickSort = arr => {
      const a = [...arr]
      if(a.length < 2) return a
      const pivotIdx = Math.floor(arr.length / 2)
      const pivot = a[pivotIdx]
      const [left, right] = a.reduce(
          (acc, val, i) => {
              if(val < pivot || (val === pivot && i !== pivotIdx)) {
                  acc[0].push(val)
              } else if(val > pivot) {
                  acc[1].push(val)    
              }
              return acc
          },
          [[], []]
      )
      return [...quickSort(left), pivot, ...quickSort(right)]
  }
  

• 归并排序 (mergeSort)

  const mergeSort = arr => {
      if(arr.length < 2) return arr
      const mid = Math.floor(arr.length / 2)
      const left = mergeSort(arr.slice(0, mid))
      const right = mergeSort(arr.slice(mid, arr.length))
      return Array.from({  length: left.length + right.length }, () => {
          if(!left.length) return right.shift()
          if(!right.length) return left.shift()
          return left[0] < right[0] ? left.shift() : right.shift()
      })
  }
  

• 桶排序 (bucketSort)

  const bucketSort = (arr, size = 5) => {
      const min = Math.min(...arr)
      const max = Math.max(...arr)
      const buckets = Array.from(
          { length: Math.floor((max - min) / size) + 1 },
          () => []
      )
      arr.forEach(val => {
          buckets[Math.floor((val - min) / size)].push(val)
      })
      return buckets.reduce((acc, bucket) => [...acc, ...bucket.sort((a, b) => a - b)], [])
  }
  

• 堆排序 (heapSort)

  const heapSort = arr => {
      const a = [...arr]
      const len = a.length
      const heapify = (a, i) => {
          const left = 2 * i + 1
          const right = 2 * i + 2
          let max = i
          if(left < len && a[left] > a[max]) max = left
          if(right < len && a[right] > a[max]) max = right
          if(max !== i) {
              [a[max], a[i]] = [a[i], a[max]]
              headify(a, max)
          }
      }
  
      for(let i = Math.floor(len / 2); i >= 0; i -- ) heapify(a, i)
      for(i = a.length - 1; i > 0; i --) {
          [ a[0], a[i] ] = [ a[i], a[0] ]
          len --
          heapify(a, 0)
      }
      return a
  }
  

其他常用算法

洗牌算法 (shuffle)

const shuffle = arr => {
    let m = arr.length
    while(m) {
        const i = Math.floor(Math.random() * m--);
        [ arr[m], arr[i] ] = [ arr[i], arr[m] ]
    }
    return arr
}

最小公约数 (lcm)

const lcm = arr = {
    const gcd = (x, y) => (!y ? x : gcd(y, x % y))
    const _lcm = (x, y) => (x * y) / gcd(x, y)
    return [...arr].reduce((a, b) => _lcm(a, b))
}

最大公因数 (gcd)

const gcd = arr => {
    const _gcd = (x, y) => (!y ? x : _gcd(y, x % y))
    return [...arr].reduce((x, y) => _gcd(x, y))
}

indexOfSubStrings

const indexOfSubStrings = function* (str, searchVal) {
    let i = 0
    while(true) {
        const r = str.indexOf(searchVal, i)
        if(r !== -1) {
            yield r
            i = i + 1
        } else return
    }
}

参考来源: https://www.30secondsofcode.org/js/t/algorithm/p/1