前言

看这篇文章之前，我们不妨自问一下，我们为什么要去学习算法？这个对我们有什么好处？

  1. 学习算法可以开拓我们的思维，让我们的逻辑更加严谨
  2. 学习算法是成为一名优秀的开发者的途径之一
  3. 可以高质、高效地完成我们业务上的需求

排序算法

冒泡排序

  1. 依次比较相邻的两个元素，根据大小互换位置，保证每一次比较大的数都在最后
  2. 重复n+1次，就可完成排序
1
2
3
4
5
6
7
8
9
10
11
12
13
14
// 时间复杂度 O(n ^ 2) n为数组长度
// 空间复杂度 O(1)
Array.prototype.bubbleSort = function () {
  // 获取当前的数组
  const ctx = this
  for (let i = 0; i < ctx.length - 1; i++) {
      for (let j = 0; j < ctx.length - 1 - i; j++) {
          // 判断后面一个数是否大于前面的，如果是则交换位置
          if (ctx[j] > ctx[j + 1]) {
              [ctx[j], ctx[j + 1]] = [ctx[j + 1], ctx[j]]
          }
      }
  }
}

测试：

1
2
3
let arr = [3, 6, 12, 65, 23, 2]
arr.bubbleSort()
console.log(arr)

选择排序

  1. 找到数组中最小的值，把它放到第一位，再找到第二小的值，放到第二位
  2. 重复上次操作n-1次
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// 时间复杂度：O(n ^ 2) n为数组长度
// 空间复杂度：O(1)
Array.prototype.selectionSort = function () {
  // 获取当前的数组
  const ctx = this
  for (let i = 0; i < ctx.length - 1; i++) {
      // 最小值的索引
      let indexMin = i
      for (let j = i; j < ctx.length; j++) {
          // 如果当前元素小于indexMin的值，则更新indexMin
          if (ctx[j] < ctx[indexMin]) {
              indexMin = j
          }
      }
      // 避免自己和自己交换
      if (indexMin !== i) {
          // 进行数据交换
          [ctx[i], ctx[indexMin]] = [ctx[indexMin], ctx[i]]
      }
  }
}

测试：

1
2
3
let arr = [3, 6, 12, 65, 23, 2]
arr.selectionSort()
console.log(arr)

插入排序

  1. 从数组第二个数开始往前比较，如它大就往后排
  2. 依次类推到最后一个数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
// 时间复杂度 O(n ^ 2)
  Array.prototype.insertionSort = function () {
      // 获取当前的数组
      const ctx = this
      // 插入排序数组长度至少是2
      if (ctx.length < 1) {
          return ctx
      }
      // 循环遍历，从第一位开始
      for (let i = 1; i < ctx.length; i++) {
          // 获取数组第一位元素
          let temp = ctx[i]
          // 获取当前索引
          let j = i
          while (j > 0) {
              // 当前面的数小于后面的数则交换位置
              if (ctx[j - 1] > temp) {
                  [ctx[j - 1], ctx[j]] = [ctx[j], ctx[j - 1]]
              } else {
                  // 如果条件不符合则跳出当前循环
                  break
              }
              // 递减
              j--;
          }
      }
  }

测试：

1
2
3
let arr = [3, 6, 12, 65, 23, 2]
arr.insertionSort()
console.log(arr)

归并排序

  1. 把数组劈成两半 在递归的对子数组进行分操作，直到分成一个个单独的数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
// 时间复杂度 O(nlogn) 分需要劈开数组，所以是logn， 合则是n
// 空间复杂度 O(n)
Array.prototype.mergeSort = function () {
    // 获取当前数组
    const ctx = this
    // 判断数组长度是否大于1
    if (ctx.length <= 1) {
        return ctx
    }
    const recursiveArr = (arr) => {
        // 递归结束条件
        if (arr.length === 1) return arr
        // 获取数组中间的索引
        const indexMid = arr.length >> 1
        // 截取左右两边的数组
        const leftTemp = arr.slice(0, indexMid)
        const rightTemp = arr.slice(indexMid)
        // 对 左右两侧的数组进行递归，得到两个有序数组
        const orderLeft = recursiveArr(leftTemp)
        const orderRight = recursiveArr(rightTemp)
        // 定义一个空数组
        let result = []
        // 遍历循环
        while (orderLeft.length || orderRight.length) {
            // 如果两个数组一直有数据，则把值小的出队
            if (orderLeft.length && orderRight.length) {
                // 值小的出队
                result.push(orderLeft[0] < orderRight[0] ? orderLeft.shift() : orderRight.shift())
            } else if (orderLeft.length) {
                // 把左边的队友放入数组
                result.push(orderLeft.shift())
            } else {
                // 把右边的队友放入数组
                result.push(orderRight.shift())
            }
        }
        return result
    }
    // 对当前数组进行递归处理
    const finalResult = recursiveArr(ctx)
    // 把当前结果放入原数组
    finalResult.forEach((element, index) => ctx[index] = element)
}

测试：

1
2
3
let arr = [3, 6, 12, 65, 23, 2]
arr.mergeSort()
console.log(arr)

合并两个有序链表

  1. 把两个树合并为有序数组，再对有序数组进行合并， 直到全部子数组合并为一个完整的数组
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
// 时间复杂度O(n) n为链表1和链表2的长度之和
// 空间复杂度O(1)
const mergeTwoLists = (list1, list2) => {
    // 定义一个新链表，作为返回值
    const result = {
        val: 0,
        next: null
    }
    // 创建一个指向新链表的指针
    const p = result
    // 创建两个指向链表的指针
    const p1 = list1
    const p2 = list2
    // 遍历循环
    while (p1 && p2) {
        // 判断两个链表的值大小
        if (p1.val < p2.val) {
            // 往p插入一个链表
            p.next = p1
            // p1需要往后移动
            p1 = p1.next
        } else {
            // 同上
            p.next = p2
            p2 = p2.next
        }
    }
    // 如果p1和p2还有值，就把后面的值全部接入新链表
    if (p1) {
        p1 = p1.next
    }
    if (p2) {
        p2 = p2.next
    }
    return result.next
}

快速排序

  1. 从数组中任意选择一个基准，比基准小的放在基准前面，比基准大的放在基准后面
  2. 递归对基准前后的的子数组进行分区
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
// 时间复杂度 O(nlogN)
// 空间复杂度 O(1)
Array.prototype.quickSort = function () {
    // 获取当前数组
    const ctx = this
    // 判断数组长度，小于1的就不用排序了
    if (ctx.length <= 1) {
        return ctx
    }
    // 定义一个递归函数
    const recursive = arr => {
        // 如果数组长度小于1就不用排序
        if (arr.length <= 1) return arr
        // 获取一个基准元素
        const benchmark = arr[0]
        // 定义基准两侧的数组
        const leftB = []
        const rightB = []
        // for遍历循环
        for (let i = 1; i < arr.length; i++) {
            // 判断元素唯一基准的左右
            if (arr[i] < benchmark) {
                leftB.push(arr[i])
            } else {
                rightB.push(arr[i])
            }
        }
        // 递归调用两边的数组
        return [...recursive(leftB), benchmark, ...recursive(rightB)]
    }
    // 执行递归后的返回值
    const result = recursive(ctx)
    // 把当前结果放入原数组
    result.forEach((element, index) => ctx[index] = element)
}

测试：

1
2
3
let arr = [3, 6, 12, 65, 23, 2]
arr.quickSort()
console.log(arr)

搜索算法

顺序搜索

  1. 从头开始搜索数组中的某个元素，比如数组的 indexOf 方法。

二分搜索

  1. 从数组中的中间位置开始搜索，如果中间元素正好是目标值，则搜索结束
  2. 如果目标值大于或者小于中间元素，则在大于或者小于中间元素的那一半数组中搜索
  3. 数组必须是有序的，如不是则需要先进行排序
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
// 时间复杂度：O(log n)
// 空间复杂度：O(1)
Array.prototype.binalySearch = function (element) {
    // 获取当前数组
    const ctx = this
    // 获取最小索引
    let minIndex = 0
    // 获取最大索引
    let maxIndex = ctx.length - 1
    // 循环遍历
    while (minIndex <= maxIndex) {
        // 获取中间元素索引
        let midIndex = (minIndex + maxIndex) >> 1
        // 判断元素是否大于中间索引,如果大于就把最小索引往中间索引的下一个
        if (element > ctx[midIndex]) {
            // 则最小索引往前
            minIndex = midIndex + 1
            // 判断元素是否小于中间索引,如果大于就把最大索引往中间索引的前一个
        } else if (element < ctx[midIndex]) {
            maxIndex = midIndex - 1
        } else {
            // 如果中间的元素正式要查找的元素
            return midIndex
        }
    }
    // 如果都找不到，则返回-1
    return -1
}

测试：

1
2
3
const arr = [1, 2, 3, 4, 5, 6]
const index = arr.binalySearch(7)
console.log(index)