排序和搜索

一、排序

将某个乱序的数组变成升序或降序的数组

image.png

• 冒泡排序

//冒泡排序 时间复杂度 O(n^2)
Array.prototype.bubbleSort = function () {
  for (let i = 0, len = this.length; i < len; i++) {
    for (let j = i + 1; j < len; j++) {
      if (this[i] > this[j]) {
        const tmp = this[j]
        this[j] = this[i]
        this[i] = tmp
      }
    }
  }
}

• 选择排序

//选择排序 时间复杂度 O(n^2)
Array.prototype.selecteSort = function () {
  for (let i = 0; i < this.length - 1; i++) {
    let min = i
    for (let j = i; j < this.length; j++) {
      if (this[min] > this[j]) {
        min = j
      }
    }
    if (this[i] !== this[min]) {
      const tmp = this[i]
      this[i] = this[min]
      this[min] = tmp
    }
  }
}

• 插入排序

//插入排序 时间复杂度 O(n^2)
Array.prototype.insertSort = function () {
  for (let i = 1; i < this.length; i++) {
    let tmp = this[i]
    let j = i
    while (j > 0) {
      if (this[j - 1] > tmp) {
        this[j] = this[j - 1]
      } else {
        break
      }
      j--
    }
    this[j] = tmp
  }
}

• 归并排序

//归并排序  时间复杂度  O(n * Logn)
Array.prototype.mergeSort = function () {
  const recursion = arr => {
    if (arr.length < 2) return arr
    const mid = ~~(arr.length / 2)
    const left = arr.slice(0, mid)
    const right = arr.slice(mid, arr.length)
    const leftArr = recursion(left)
    const rightArr = recursion(right)
    const res = []
    while (leftArr.length || rightArr.length) {
      if (leftArr.length && rightArr.length) {
        res.push(leftArr[0] > rightArr[0] ? rightArr.shift() : leftArr.shift())
      } else if (leftArr.length) {
        res.push(leftArr.shift())
      } else if (rightArr.length) {
        res.push(rightArr.shift())
      }
    }
    return res
  }
  const result = recursion(this)
  result.forEach((v, i) => this[i] = v)
}

• 快速排序

//快速排序  时间复杂度  O(n * Logn)
Array.prototype.quickSort = function () {
  const recursion = arr => {
    if (arr.length < 2) return arr
    const basic = arr[0]
    const left = []
    const right = []
    for (let i = 1; i < arr.length; i++) {
      if (arr[i] > basic) {
        right.push(arr[i])
      } else {
        left.push(arr[i])
      }
    }
    return [...recursion(left), basic, ...recursion(right)]
  }
  const result = recursion(this)
  result.forEach((v, i) => this[i] = v)
}

二、搜索

找出数组中某个元素的下标

• 顺序搜索

//顺序搜索  时间复杂度 O(n)
Array.prototype.sequentialSearch = function (item) {
  for (let i = 0; i < this.length; i++) {
    if (this[i] === item) {
      return i
    }
  }
  return -1
}

• 二分搜索

//二分搜索  需要确保数组是有序的（如果是乱序的，需要先排序。数组有序的话时间复杂度是 O(logN)
Array.prototype.binarySearch = function (item) {
  this.sort((a, b) => a - b) //如果是有序数组 可省略
  let min = 0
  let max = this.length - 1
  while (min <= max) {
    const mid = ~~((min + max) / 2)
    const cur = this[mid]
    if (item < cur) {
      max = mid - 1
    } else if (item > cur) {
      min = mid + 1
    } else {
      return mid
    }
  }
  return -1
}