salvatore's blog

基本算法

... 2020-9-25 About 9 min

# 基本算法

算法这个东西怎么说呢，我觉得在项目中我多多少少还是会使用一些的吧，在学习的过程中也是了解一下最基本的算法的写法吧

# 1. 排序算法

简单的对排序分类一下

  • 比较排序，时间复杂度：O(nlogn) ~ O(n^2)不等，主要有：冒泡排序、选择排序、插入排序、归并排序、堆排序、快速排序
  • 非比较排序：时间复杂度可以达到O(n)，主要有：计数排序、基数排序、捅排序

# 1.1 冒泡排序

冒泡排序每次从数组的最开始索引处于后一个值比较，如果当前值大，则交换位置，这样一次下来，最大值就会排入到最后位置

let bubbleSort = arr => {
  for (let i = 0; i < arr.length; i++) {
    let temp
    for (let j = 0; j < arr.length - i - 1; j++) {
      if (arr[j] > arr[j+1]) {
        temp = arr[j]
        arr[j] = arr[j+1]
        arr[j+1] = temp
      }
    }
  }
}
1
2
3
4
5
6
7
8
9
10
11
12
分类 -------------- 内部比较排序
数据结构 ---------- 数组
最差时间复杂度 ---- O(n^2)
最优时间复杂度 ---- 如果能在内部循环第一次运行时,使用一个标签来表示有无需要交换的可能,可以把最优时间复杂度降低到O(n)
平均时间复杂度 ---- O(n^2)
所需辅助空间 ------ O(1)
稳定性 ------------ 不稳定

# 1.2 选择排序

选择排序每次比较的是数组中特定索引的值与全数组中每个值的大小比较，每次都选出一个最小(最大)值，如果当前索引的值大于之后索引的值，则两者进行交换

let chooseSort = arr => {
  for (let i = 0; i < arr.length; i++) {
    for (let j = 0; j < arr.length; j ++) {
      let temp
      if (arr[i] > arr[j]) {
        temp = arr[i]
        arr[i] = arr[j]
        arr[j] = temp
      }
    }
  }
}
1
2
3
4
5
6
7
8
9
10
11
12
分类 -------------- 内部比较排序
数据结构 ---------- 数组
最差时间复杂度 ---- O(n^2)
最优时间复杂度 ---- O(n^2)
平均时间复杂度 ---- O(n^2)
所需辅助空间 ------ O(1)
稳定性 ------------ 不稳定

# 1.3 插入排序

# 1.3.1 普通插入排序

插入排序类似于扑克牌的插入方法，选取待排序数组中的任意一个数字作为已经排序的基准，在依次从待排序数组中取出数字，根据依次比较，将这个数字插入到已排序的数组中

let insertSort = arr => {
  let sortList = [arr[0]]
  for (let i = 0; i < arr.length - 1; i++) {
    let length = sortList.length
    // 如果取出的数字比已经排序的第一个值小，插在开头
    if (arr[i] < sortList[0]) {
      sortList.unshift(arr[i])
      continue
    }
    // 如果取出的数字比已经排序的最后一个值大，插在最后
    if (arr[i] > sortList[sortList.length-1]) {
      sortList.push(arr[i])
      continue
    }
    // 剩下的情况就是在sortList中间，把他揪出来，添加进去
    for (let j = 0; j < sortList.length-1; j++) {
      if (arr[i] >= sortList[j] && arr[i] <= sortList[j+1]) {
        sortList.splice(j,0,arr[i])
        break
      }
    }
  }
  return sortList
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
分类 -------------- 内部比较排序
数据结构 ---------- 数组
最差时间复杂度 ---- 最坏情况为输入序列是降序排列的,此时时间复杂度O(n^2)
最优时间复杂度 ---- 最好情况为输入序列是升序排列的,此时时间复杂度O(n)
平均时间复杂度 ---- O(n^2)
所需辅助空间 ------ O(1)
稳定性 ------------ 稳定

# 1.3.2 二分插入排序

二分插入排序是直接插入排序的一个子类，利用二分查找法找出下一个数字对应的索引，然后进行插入

当数组长度比较大的时候，二分插入排序比直接插入排序的最差情况要好得多，但是比直接插入排序的最好情况要差得多，所以当元素初始序列已经接近升序时，直接插入排序比二分插入排序次数少，使用哪一个依赖元素初始序列

let twoInsertSort = arr => {
  let sortList = [arr[0]] // sortList是已经有顺序的位置
  for (let i = 1; i < arr.length; i ++) { // index为0的元素已经被取出去了
    let get = arr[i]
    let left = 0;
    let right = sortList.length - 1

    // 每次找到sortList中间的数字进行比较，确定最终的索引位置
    while (left <= right) {
      let mid = parseInt((left + right) / 2) // 先去soltList中间的数字
      if (sortList[mid] > get) { // 如果大于当前的比较值， 则有序数组的中间值需要向左移动
        right = mid - 1 // 中间值向左移动
      } else {
        left = mid + 1 // 中间值的选取向右移动
      }
    }
    sortList.splice(left, 0, get)
  }
  return sortList
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

这里说的这个二分指的是对已经排好序的数组去二分，然后找到原先数组在新数组的排序位置在哪，所以这种方法的重点在与新形成的数组，而不去过多的纠结老数组

分类 -------------- 内部比较排序
数据结构 ---------- 数组
最差时间复杂度 ---- O(n^2)
最优时间复杂度 ---- O(nlogn)
平均时间复杂度 ---- O(n^2)
所需辅助空间 ------ O(1)
稳定性 ------------ 稳定

# 1.3.3 希尔排序

希尔排序是一种更为高效的插入排序，通过步长将数组分组，然后每组中单独排序，然后再缩小步长，进行重复的分组排序工作，直到步长为1的时候将整个数组分为一个数组，结束

let hillSort = arr => {
  let step = Math.floor(arr.length / 2)
  for (; step > 0; step = Math.floor(step / 2)) { // 用于每次把步长减一半；当步长为0的时候终止循环
    for (let i = step; i < arr.length; i++) { // 对于数组后半部分遍历一次
      let j = i
      while (j - step >=0 && arr[j] < arr[j - step]) { // 这个地方实际上使用的就是冒泡排序
        [arr[j], arr[j - step]] = [arr[j - step], arr[j]] // 懒得再写一遍替换的函数了，这个地方直接使用结解构替换把
        j -=step // 每次跳着去寻找，这样就可以按照step找出相关的值，并且进行排序， 当然这一条可以不写，对结果也没有影响，写这个是为了减少while循环的次数
      }
    }
  }
  return arr
}
1
2
3
4
5
6
7
8
9
10
11
12
13
分类 -------------- 内部比较排序
数据结构 ---------- 数组
最差时间复杂度 ---- 根据步长序列的不同而不同。已知最好的为O(n(logn)^2)
最优时间复杂度 ---- O(n)
平均时间复杂度 ---- 根据步长序列的不同而不同。
所需辅助空间 ------ O(1)
稳定性 ------------ 稳定

# 1.4 快速排序

快排的原理是：首先随机选择一个值，遍历整个数组，比较这个值小的放左边数组，大就放右边数组，然后再根据上一步得到左右数组重复步骤，知道分出的数组长度为1或者0的时候停止

let quickSort = arr => {
  if (arr.length === 1 || arr.length === 0) { // 递归出去的唯一条件 随着数组的排序减半总为剪到1或者0（奇数偶数的差别）的，
    return arr
  }
  let [left, right] = [[],[]]
  let mid = Math.floor(arr.length / 2)
  let midVal = arr[mid]
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] < arr[mid]) {
      left.push(arr[i])
    } else if (arr[i] > arr[mid]){
      right.push(arr[i])
    }
  }
  let leftArr = quickSort(left)
  let rightArr = quickSort(right)
  return leftArr.concat(midVal).concat(rightArr)
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

* 得注意一点的是，只要是递归的运算都要考虑“栈溢出”的问题

分类 -------------- 内部比较排序
数据结构 ---------- 数组
最差时间复杂度 ---- O(nlogn)
最优时间复杂度 ---- O(nlogn)
平均时间复杂度 ---- O(nlogn)
所需辅助空间 ------ O(3)
稳定性 ------------ 稳定

# 1.5 堆排序

堆排序是指利用堆这种数据解构所设计的一种选择排序算法，堆是一种近似于完全二叉树（通常堆是通过一维数组来实现的），并满足性质：以最大堆（也叫大根堆，大顶堆）为例，其中父节点的指总是大于子节点

定义堆排序的过程

  • 由输入的无序数组构成最大堆，作为初始的无序区
  • 把堆顶元素（最大值）和堆尾元素互换
  • 把堆（无序区）的尺寸缩小1，并调用heapAdjust(arr,0)从新的堆顶元素开始进行堆调整
  • 重复步骤2，直到堆的尺寸为1
let heapAdjust = (arr, i = 0 , end = arr.length) => {
  let temp = arr[i]
  for (let j = 2 * i + 1; j < end; j =  2 * i + 1) {
    if (j < end && arr[j] < arr[j+1]) {
      ++j
    }
    if (temp >= arr[j]) {
      break
    }
    arr[i] = arr[j]
    i = j
  }
  arr[i] = temp
}
let heapSort = arr => {
  for (let i = arr.length / 2; i >= 0; i--) {
    heapAdjust(arr, i, arr.length)
  }
  for (let i = arr.length; i > 0; i--) {
    [arr[0], arr[i - 1]] = [arr[i - 1],arr[0]]
    heapAdjust(arr, 0, i - 2)
  }
  return arr
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

# 2. 数组操作

先说一个有趣的，将两个有序的数组合并成一个有序的数组

let mergeSortAB = (arrA, arrB) => {
  let arr = []
  while (arrA.length * arrB.length !== 0) {
    if (arrA[0] > arrB[0]) {
      arr.push(arrB[0])
      arrB.shift()
    } else if (arrA[0] === arrB[0]) {
      arr.push(arrA[0])
      arr.push(arrB[0])
      arrA.shift()
      arrB.shift()
    } else {
      arr.push(arrA[0])
      arrA.shift()
    }
  }
  return arr.concat(arrA.length ? arrA : arrB)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

# 3. 数组去重

# 3.1 indexOf

let uni = arr => {
  let re = []
  for (let i = 0; i < arr.length; i ++) {
    if (!~re.indexOf(arr[i])) {
      re.push(arr[i])
    }
  }
  return re
}
1
2
3
4
5
6
7
8
9

# 3.2 indexOf和lastIndexOf

let uni = arr => {
  let re = []
  for (let i = 0; i < arr.length; i ++) {
    if (i === arr.lastIndexOf(arr[i])) {
      re.push(arr[i])
    }
  }
  return re
}
1
2
3
4
5
6
7
8
9

# 3.3 Set

let uni = arr => [...new Set(arr)]
1

# 3.4 filter

let uni = arr => arr.filter((item,index) => arr.indexOf(item) === index)
1

资料 (opens new window)

# 4. 其他工作中遇到或者可能遇到的

# 4.1 矩阵相乘

今天突然想做一个两个矩阵相乘的方法，就写下来了，有什么问题我不管先写了再说

/** 
 * 两个矩阵相乘的问题
 * 判断是否为矩阵形式
 * 判断是否可以相乘
 * 计算出最后的结果
*/

let arr = [
  [1, 2, 3],
  [2, 3, 4],
  [3, 4, 5],
  [4, 5, 6]
]
let arr1 = [
  [1, 2],
  [2, 3],
  [3, 4]
]
// 判断是否为矩阵形式的二维数组
let isMatrix = arr => Array.isArray(arr) && arr.length > 0 && arr.every(item => Array.isArray(item) && item.length === arr[0].length)
let matrixMulti = (matrix, matrix1) => {
  // 先判断是否满足矩阵相乘的条件
  // 1. 确保两个数组都是矩阵数组
  if (!isMatrix(matrix) || !isMatrix(matrix1)) return '数组存在不为矩阵的数组'
  // 2. 矩阵函数列数是可以相乘的
  if (matrix1.length !== matrix[0].length) return `${matrix.length}*${matrix[0].length}和${matrix1.length}*${matrix1[0].length}的矩阵不可以相乘`
  // 先确定矩阵的行数和列数
  const row  = matrix.length
  const col = matrix1[0].length
  let result = []
  for (let i = 0; i < row; i++) {
    let arr = [] // 这个数组控制有几行
    for (let j = 0; j < col; j++) {
      // 一行中的每个数对应的值
      arr.push(matrix[i].reduce((sum,item,index) => sum + item*matrix1[index][j], 0))
    }
    result.push(arr)
  }
  return result
}
console.log('---------->', matrixMulti(arr,arr1))
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
Last update: December 23, 2022 13:14
Contributors: salvatoreliaoxuan , liaoxuan