九旬的博客

算法

排序算法

冒泡排序

冒泡排序是排序算法中最简单的，然后从运行角度来看，它却是最差的一个。
冒泡排序的原理很简单，就是比较任何两个相邻的项，如果第一个比第二个大，则交换他们。元素项向上移动至正确的顺序，就好像气泡上升到表面一样，冒泡排序因此得名。

步骤

  • 比较相邻的元素，如果第一个如第二个大，就交换他们两个。
  • 对每一组相邻元素作同样的工作，从开始第一对到结尾的最后一对，这步做完，最后的元素会是最大的数。
  • 针对所有的元素重复以上步骤，直到没有任何一对数字需要比较。

JS 实现

// 第一种
let arr = [1, 5, 4, 2, 3];

function sort(arr) {
    let len = arr.length;
    for (let i = 0; i < len; i++) {
        for (let j = i+1; j < len; j++) {
            if(arr[i] > arr[j]){
                [arr[i], arr[j]] = [arr[j], arr[i]]
            }
        }
    }
    return arr;
}
let result = sort(arr);
console.log(result)// [ 1, 2, 3, 4, 5 ]

// 第二种
function bubleSort(arr) {
  let len = arr.length;
  for (let outer = len; outer >= 2; outer--) {
    for (let inner = 0; inner <= outer - 1; inner++) {
      if (arr[inner] > arr[inner + 1]) {
        [arr[inner], arr[inner + 1]] = [arr[inner + 1], arr[inner]];
      }
    }
  }
  return arr;
}
let arr = [1, 2, 5, 4, 5, 4, 78, 4];
console.log(bubleSort(arr)); // [1, 2, 4, 4, 4, 5, 5, 78]
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

冒泡排序动画演示

选择排序

选择排序是一种原址比较排序算法，选择排序大致的思路就是找到数据结构中最小的值并将其放在第一次，然后找到第二小的值，将其放在第二位...以此类推

步骤

  • 找到最小的值，和第一个元素交换。
  • 知道第二小的值，和第二个元素交换
  • 以此类推..

选择排序动画演示

插入排序

插入排序的原理如下。第一个元素默认是已排序元素，取出下一个元素和当前元素比较，如果当前元素大就交换位置。那么此时第一个元素就是当前的最小数，所以下次取出操作从第三个元素开始，向前对比，重复之前的操作。

步骤

  • 将第一待排序序列的第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是末排序列。
  • 从头到尾一次扫描未排序序列，将扫描的每个元素插入有序序列的适当位置。

JS 实现

function insertSort(arr) {
  let len = arr.length;
  for (let i = 1; i < len; i++) {
    for (let j = i; j > 0; j--) {
      if (arr[j] < arr[j - 1]) {
        [arr[j], arr[j - 1]] = [arr[j - 1], arr[j]];
      } else {
        break;
      }
    }
  }
  return arr;
}
let arr = [1, 2, 5, 4, 5, 4, 78, 4];
console.log(insertSort(arr)); // [1, 2, 4, 4, 4, 5, 5, 78]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

插入排序动画演示

归并排序

归并排序是一种分而治之算法，其思想是将原数组切割分为较小的数组，知道买个小数组只有一个位置，接着讲小数组归并为大的数组，知道最后只有一个排序完毕的大数组。

步骤

  • 将原始数组分割为多个的只有一个项的小数组
  • 然后将小数组排序
  • 最后将已排好的小数组归并为一个大数组

归并排序动画演示

快速排序

快排的原理如下。随机选取一个数组中的值作为基准值，从左至右取值与基准值对比大小。比基准值小的放数组左边，大的放右边，对比完成后将基准值和第一个比基准值大的值交换位置。然后将数组以基准值的位置分为两部分，继续递归以上操作。

步骤

  • 首先，从数组中选择中间一项作为基准值。
  • 创建两个指针，左边一个指向数组的第一项，右边一个指向数组的最后一项。
    • 移动左指针直到找到一个比基准值大的元素
    • 移动右指针直到找到一个比基准值小的元素
    • 然后交换他们
    • 重复这个过程，直到左指针超过右指针。
  • 这个过程将使得比基准值小的值都排在基准值之前，而比基准值大的值都排在基准值后面，直至数组排序完全。
function quickSort(arr) {
  if (arr.length <= 1) {
    return arr; // 边界
  }
  var left = [];
  var right = [];
  var current = arr.splice(0, 1);
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] < current) {
      left.push(arr[i]); // 放在左边
    } else {
      right.push(arr[i]); // 放在右边
    }
  }
  return quickSort(left).concat(current, quickSort(right)); // 递归
}
let arr = [1, 2, 5, 4, 5, 4, 78, 4];
console.log(quickSort(arr)); // [1, 2, 4, 4, 4, 5, 5, 78]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

快速排序动画演示

搜索算法

顺序搜索

顺序或线性搜索是最基本的搜索算法，它的机制是，将每一个数据结构中的元素和我们要找的元素做比较，顺序搜索是一种抵消的算法。

步骤

  • 遍历这个呢个数组，并将每个元素和搜索项比较
  • 如果搜索到就返回 true 或索引，搜素不到返回 false 或-1，

二分搜索

二分搜索采用分而治之的方法，这个算法要求被搜索的数据结构已排序，然后将数据一分为二。直到找到该值为止。

步骤

  • 选择选中值的中间值
  • 如果选择的值是待搜索值，那么算法执行结束（找到了）
  • 如果待搜索的值比选中值要小，则返回步骤 1 并在选中值左边的子数组中寻找
  • 如果待搜索的值比选中值要大，则返回步骤 1 并在选中值右边的子数组中寻找。

二分.png

JS 实现 | 循环版本

function binarySeachFindIndex(arr, target) {
  let low = 0;
  let high = arr.length - 1;
  let mid = null;
  while (low <= high) {
    mid = Math.floor((low + high) / 2);
    if (target === arr[mid]) {
      return mid;
    }
    if (target > arr[mid]) {
      low = mid + 1; // 猜大了 +1
    } else {
      high = mid - 1; // 猜小了 -1
    }
  }
  return -1; // 没找到 返回 -1
}
let result = binarySeachFindIndex([1, 2, 3, 4, 5, 6], 5);
console.log(result); // 4
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

JS 实现 | 循环版本

function binarySeachFindIndex(arr, target, low = 0, high = arr.length - 1) {
  let mid = Math.floor((low + high) / 2);
  let cur = arr[mid];
  if (cur === target) {
    return mid;
  } else if (cur > target) {
    return binarySeachFindIndex(arr, target, low, mid - 1);
  } else if (cur < target) {
    return binarySeachFindIndex(arr, target, mid + 1, high);
  } else {
    return -1;
  }
}
let result = binarySeachFindIndex([1, 2, 3, 4, 5, 6], 5);
console.log(result); // 4
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

补充知识

递归

能够调用自身的方法或函数就是递归函数,每个递归函数都必须有一个边界条件，即一个不再递归的条件（停止点），以防止无限递归，无限递归会导致栈溢出（stack overflow error）。

  • 自己调用自己函数
  • 存在一个边界条件 JS 数组扁平化
Array.prototype.flat = function() {
  let arr = [];
  this.forEach((item, index) => {
    if (Array.isArray(item)) {
      arr = arr.concat(item.flat()); //是数组 连接数组+继续递归
    } else {
      arr.push(item); // 非数组，push
    }
  });
  return arr; // 递归出口
};
let arr = [
  1,
  2,
  3,
  [4, 5, 6, [7, 8, 9, [10]]],
  [10, 11],
  [12, 13, [14, 15, [16, 17, [18, 19, [20]]]]],
];
console.log(arr.flat());
//  [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

斐波那契数列

定义

  • 1 和 2 的斐波那契数是 1
  • n(n > 2) 的斐波那契数是(n + 1)的斐波那契数加上(n - 2)的斐波那契数
  • 参考爬楼梯

动态规划

动态规划，是一种将复杂问题分解成更小问题来解决的优化技术。

贪心算法

贪心算法遵循一种近似解决问题的技术，期盼通过每个阶段的局部最优选择，从而达到全局的最优。

大 O 表示法

即时间复杂度，通常使用最差的时间复杂度来衡量一个算法的好坏，即 CUP 运行一个算法所需的时间。

  • O(1)：只运行一次
  • O(log(n))： 运行 n 的对数次
  • O(n)：运行 n 次，n 是(输入)数组的大小
  • O(n^2)：运行 n^2，输入值的平方

OIP

参考