js 排序

---

title: js 排序
tag: javascript
date: 2019/12/5 10:33

插入排序

function insertSort(arr) {
  for (let i = 0; i < arr.length; i++) {
    const current = arr[i] //7
    let j = i - 1 //1
    while (j >= 0 && arr[j] < current) {
      arr[j + 1] = arr[j]
      j--
    }
    arr[j + 1] = current
  }
  return arr
}
insertSort([1, 4, 7, 5])

第一轮结果:4,1,7,5
第二轮：i=2,arr[i]=7;
j=1 ,arr[j]=1;开始while循环
每次如下：//4,1,1,5//4,4,1,5//7,4,1,5
原理：其实就是arr[i]当前要插入项，拿后一项while循环检查如果（？？？）条件成立，将此arr[j--[n]]向后推移，并重复，达不成条件表示已找到插入点，把当前项赋值给arr[j+1]操作
另一种写法

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

原理：如果当前项比我的头项（头表示最大）还大，那么它就是最大放到首，否则表示在内部找地方插入，一个个比较哪个比它小就插入哪。
优点：稳定，快；
缺点：比较次数不一定，比较次数越少，插入点后的数据移动越多，特别是当数据总量庞大的时候，但用链表可以解决这个问题。

快速排序

function quickSort(arr) {
  if (arr.length <= 1) {
    return arr
  }
  let index = Math.floor(arr.length / 2)
  let mid = arr.splice(index, 1)[0]
  let left = [],
    right = []
  for (let i = 0; i < arr.length; i++) {
    const v = arr[i]
    if (v < mid) {
      left.push(v)
    } else {
      right.push(v)
    }
  }
  return quickSort(left).concat(mid, quickSort(right))
}

稍加优化

const quickSort = function(arr, func, filter) {
  if (arr.length <= 1) {
    return arr
  }
  if (typeof func != 'function') {
    func = (a, b) => a - b > 0
  }
  let index = Math.floor(arr.length / 2)
  let mid = arr.splice(index, 1)[0]
  let left = [],
    right = []
  for (let i = 0; i < arr.length; i++) {
    const v = arr[i]
    let funcBack = func
    if (filter) {
      funcBack = (a, b) => func(filter(a), filter(b))
    }
    if (funcBack(v, mid)) {
      left.push(v)
    } else {
      right.push(v)
    }
  }
  return quickSort(left, func, filter).concat(
    mid,
    quickSort(right, func, filter)
  )
}

1. 找基准（一般是以中间项为基准）
2. 遍历数组，小于基准的放在left，大于基准的放在right
3. 递归

冒泡排序

function bubbleSort(arr) {
  let res = arr.slice()
  let l = res.length
  let change = false
  for (let i = 0; i < res.length; i++) {
    for (let j = l - 1; j > i; j--) {
      if (res[j - 1] < res[j]) {
        let v = res[j - 1]
        res[j - 1] = res[j]
        res[j] = v
        change = true
      }
    }
    if (!change) return res
  }
  return res
}