排序

排序

1. 冒泡排序

1. 对于一个数组，比较所有的相邻的元素，如果第一个大于第二个，则交换
2. 比较一轮下来，可以保证一个元素是有序的
3. 在比较n-1 轮，整个数组就排序好了

• 代码实现

// 将排序算法挂载到原型链上

Array.prototype.bubbleSort = function () {
  for (let i = 0; i < this.length - 1; i++) {
    // 一轮下来，最后一个排好了
    // 比较所有的相邻元素
    // 因为每一次可以排好一个，即后面的部分元素不参与排序
    for (let j = 0; j < this.length - 1 - i; j++) {
      if (this[j] > this[j + 1]) {
        // 交换
        let temp = this[j]
        this[j] = this[j + 1]
        this[j + 1] = temp
      }
    }
  }
}

let arr = [5, 4, 3, 2, 1]

arr.bubbleSort()

• 时间复杂度O(n*n)

2. 选择排序

1. 每次从数组中选择出一个最大的
2. 选择出的元素的与最后一个元素进行交换
3. 最后一个元素不参与排序
4. 排序n-1长度的数组
5. 重复执行上述操作

• 代码实现

// 选择排序
Array.prototype.selectSort = function () {
  //选择出一个最大的元素
  for (let i = 0; i < this.length; i++) {
    let max = -1
    let index = -1
    for (let j = 0; j < this.length - i; j++) {
      if (this[j] > max) {
        max = this[j]
        index = j
      }
    }

    // 交换
    let temp = this[index]
    this[index] = this[this.length - 1 - i]
    this[this.length - 1 - i] = temp
  }
}
let arr = [5, 4, 3, 2, 1]

arr.selectSort()

• 时间复杂度O(n*n)

3. 插入排序

1. 对于一个数组，从下标为1的数开始
2. 比较（当前下标的数）与（下标-1到下标为0）的大小
3. 当前的小，前面一个下标的右移，当前要插入的下标左移
4. 当前的大，将当前元素插入到当前要插入的下标，终止
5. 循环前面步骤

// 插入排序
Array.prototype.insertionSort = function () {
  // 从下标为1的开始比
  for (let j = 1; j < this.length; j++) {
    let before = j - 1
    let curr = this[j]
    while (curr < this[before]) {
      // before对应的元素右移
      this[before + 1] = this[before]
      before--
    }

    // before的值小于等于当前值
    this[before + 1] = curr
  }
}
let arr = [10, 5, 7, 5, 4, 2, 2, 1]

arr.insertionSort()

4. 归并排序

1. 对于一个数组，切分为两半
2. 对于左半和右半，再递归切分
3. 递归出口，切分的数组长度为1，返回
4. 左半回来，右半也回来了，使用一个栈，小的[数组第一个元素]先进去，大的[数组第一个元素]后进去，就是有序的了 返回
5. 循环上述操作

// 将排序算法挂载到原型链上
// 归并排序
Array.prototype.mergeSort = function () {
  const rcs = arr => {
    // 递归出口
    if (arr.length === 1) {
      return arr
    }

    // 数组切分
    let mid = Math.floor(arr.length - 1 / 2)

    // 左半部分
    let leftArr = arr.slice(0, mid)
    // 左边部分递归切分
    const orderLeft = rcs(leftArr)
    // 右半部分
    let rightArr = arr.slice(mid, arr.length)
    const orderRight = rcs(rightArr)

    // 合并左边和右边的部分

    // 合并后的数组
    let res = []

    while (orderLeft.length && orderRight.length) {
      if (orderLeft[0] > orderRight[0]) {
        res.push(orderRight.shift())
      } else {
        res.push(orderLeft.shift())
      }
    }

    while (orderLeft.length) {
      res.push(orderLeft.shift())
    }

    while (orderRight.length) {
      res.push(orderRight.shift())
    }

    return res
  }

  const res = rcs(this)

  return res
}

let arr = [1, 4, 7, 2, 1]

const res = arr.mergeSort()

console.log(res)

• 时间复杂度O(nlogn)

5. 快速排序

1. 自定义一个基准值（任意一个元素）
2. 把比基准值小的元素放在左边，基准值大的放在右边
3. 左边和右边的单独成为一个新数组（递归上面步骤）
4. 递归出口：数组长度为1
5. 合并左边，基准值，右边，得到已经排序好的数组

// 将排序算法挂载到原型链上
// 快速排序
Array.prototype.quickSort = function () {
  // 递归算法
  const rcs = arr => {
    // 递归出口
    if (arr.length === 1 || !arr.length) {
      return arr
    }
    // 选定一个基准值,随意选
    const base = arr[0]
    // 定义左边和右边
    let leftArr = []
    let rightArr = []

    // 循环当前数组，把比基准值小的放在左边，大的放在右边
    for (let i = 1; i < arr.length; i++) {
      if (arr[i] < base) {
        leftArr.push(arr[i])
      } else {
        rightArr.push(arr[i])
      }
    }

    // 对左边的右边的数组进行递归
    const orderLeft = rcs(leftArr)
    const orderRight = rcs(rightArr)

    // 返回合并的数组
    return [...orderLeft, base, ...orderRight]
  }

  const res = rcs(this)
  return res
}

let arr = [1, 4, 7, 2, 1]

const res = arr.quickSort()

console.log(res)

• O(log(n))
• 最坏：O(n*n)

搜索

1. 二分查找

1. 前提：待查找的数组是有序的
2. 找到中间值mid，比对target和mid
3. 如果mid>target ,搜索范围0-(mid-1) 重复上述操作
4. 如果mid<target,搜索范围(mid+1) - length 重复1，2操作
5. 相等，返回结果下标
6. 没找到，返回-1

// 将搜索算法挂载到原型链上
// 二分查找
Array.prototype.binarySearch = function (target) {
  let low = 0
  let high = this.length - 1

  while (low <= high) {
    // 找到中间值
    const mid = Math.floor((low + high) / 2)

    // 判断目标值与中间值的大小
    if (target < this[mid]) {
      // 缩小范围到左边
      high = mid - 1
    } else if (target > this[mid]) {
      // 缩小范围到右边
      low = mid + 1
    } else {
      // 找到
      return mid
    }
  }

  // 没找到
  return -1
}

let arr = [1, 4, 9, 12, 19]

const res = arr.binarySearch(4)

console.log(res)