Rni-L Blog

Appearance

数据结构 ​

线性表 ​

一种由相同类型的数据，有序的数据结构；元素之间是一对一的关系

因为是顺序存储结构，需要预分配

优点：

  1. 无须为表示表中元素之间的逻辑关系而增加额外的存储空间
  2. 可以快速地存取表中任一位置的元素

缺点：

  1. 插入和删除操作需要移动大量元素（是 $$O(n)$$ 复杂度)
  2. 线性表长度变化较大时，难以确定存储空间的容量
  3. 造成存储 空间的“碎片”

单链表 ​

每个节点都有一个指针(属性)指向它的下一个节点，通过控制节点的指针进行添加、删除、查询等

生成单链表，不需要在连续固定的位置进行存储

存储的数据的时候会存储两个数据：

  1. 数据域：当前要存储的数据部分
  2. 指针：存储后继位置的数据部分

两者结合，称为：节点(Node)

在第一个节点，会添加一个叫“头节点”的数据域，有时候会存放例如长度等一些信息，方便操作

相对于线性表，对于频繁地插入或删除操作，性能更好

因为线性表如果一次插入 10 个元素，它就要移动十次；而单链表，只要找到目标位置，只需 $$O(n)$$ + $$O(1)$$ 的复杂度就行了

静态链表 ​

就是用静态数组存储数据和指针；但是还会有线性表的缺点，只是在某些没有指针特性的语言进行实现链表

循环链表 ​

最后的节点的指针指向头结点，形成一个循环，就是循环链表

双向链表 ​

在单链表的基础上，每个节点添加一个“链接上一个节点”的指针

单链表在已知某个节点的基础上，查找下一个节点的复杂度是：$$O(1)$$，而上一个节点的复杂度是：$$O(n)$$

为了解决这个问题，就有了双向链表；说白了就是空间换时间

栈 ​

原则：先进后出的有序集合

栈其实和链表很类似，除了对添加、删除操作有特殊要求外。而栈的作用，就是简化程序设计的问题，划分不同关注层次，聚焦我们要解决的问题核心

像浏览器的历史记录，就是使用了栈数据结构；

递归的函数调用

队列 ​

原则：先进先出的有序集合（线性表）

循环队列 ​

头尾相接的顺序存储结构，就是循环队列

串 ​

串(strin) 是由零个或多个字符组成的有限序列，又叫字符串

串的比较大小，先把每个串里面的字符转换成对应的编码（比如：ASCII2 或者 Unicode）然后从首页进行比较

如果首页一样，接着往下，看谁比较大

集合 ​

原则：无序且唯一的项组成；是由 [值，值] 组成

字典 ​

原则：与集合类似，但是由 [键，值] 组成，类似 js 的 Object

散列 ​

原则：根据 key 和 value 访问的数据结构，把关键码值映射到表中一个位置来访问记录，映射函数叫做散列函数；存放记录叫做散列表

树 ​

由 n 个有限节点组成的一个具有层次关系的集合

根结点：无父结点，唯一

内部结点：非终端结点

叶结点/终端结点：无结点，可以多个

中间节点：一个父节点，多个节点

结点度：该结点有多少个叶结点

深度：该树有多少层级

二叉树 ​

由一个根节点和两个子节点组成的集合；每个节点都可以有且仅有两个子节点

子节点分为：左子树和右子树，这是有顺序关系的

性质 ​
  1. 第 i 层最多有多少个结点：$$2^{i-1}$$
  2. 深度为 K 的二叉树，最多有 $$2^k-1$$ 个结点
  3. 二叉树 T，如果其终端结点数为 $$n_0$$ ，度为 2 的结点数为 $$n_2$$ ，则 $$n_0 = n_2 + 1$$
    1. 这个等式解释为：终端结点 = 结点（子结点有两个） + 1
  4. 具有 n 个结点的完全二叉树的深度为 $$[log_2n]+1$$ ( [x] 表示不大于 x 的最大整数)
    1. 比如有 1 个结点 -> [$$log_21$$] + 1 -> [0.3….] + 1 -> 0 + 1 -> 1(深度为 1)
    2. 比如有 2 个结点 -> [$$log_22$$] + 1 -> [0.6….] + 1 -> 0 + 1 -> 1
    3. 4 个
  5. 对有 n 个结点的完全二叉树，对任一结点 i ( 1 <= i <= n)
    1. i = 1 i 是根（废话）
    2. 2 * i > n，则结点无左结点；否则左结点为 2 * i
    3. 2 * i + 1 > n，则结点无右结点；否则右结点为 2 * i + 1
斜树 ​

只有一边的节点，叫做斜树；比如全部子节点只有左子树，这叫左斜树；同理，另外一边的叫右斜树

满二叉树 ​

所有分支结点都有左右子树，且所有叶子都在同一层上

完全二叉树 ​

叶子一定是按左部连续位置的

特点：

  1. 叶子结点只能出现在最下两层
  2. 最下层的叶子一定集中在左部连续位置
  3. 倒数二层，若有叶子结点，一定都在右部连续位置
  4. 结点度为1，肯定是左结点
  5. 同样结点数的二叉树，完全二叉树深度最小
存储结构 ​

顺序存储结构，这种只适用于完全二叉树类型

链式存储结构，每个节点都存储数据源 + 左子节点 + 右子节点；这种又叫二叉链表

二叉搜索树 ​

二叉搜索树（BST）又称二叉查找树或二叉排序树

是一个递增序列，左节点 < 中节点 < 右节点

二叉树遍历方式 ​
前序遍历 ​

像这张图，遍历顺序：abdhkecfigj

具体实现：

javascript
// 伪代码
function func(tree) {
  if (!tree) return
  console.log(tree.data)
  func(tree.left)
  func(tree.right)
}

// 递归法
var preorderTraversal = function(root) {
  if (!root) return []
  let output = []
  output.push(root.val)
  if (root.left !== null) {
    output.push(...preorderTraversal(root.left))
  }
  if (root.right !== null) {
    output.push(...preorderTraversal(root.right))
  }
  return output
}

// 遍历法
var preorderTraversal = function(root) {
  if (!root) return []
  let output = []
  let stack = []
  stack.push(root)
  while(stack.length !== 0) {
    const target = stack.shift()
    output.push(target.val)
    // 这里因为栈的原因，要先插入 right，再插入 left
    if (target.right) {
      stack.unshift(target.right)
    }
    if (target.left) {
      stack.unshift(target.left)
    }
  }
  return output
}
中序遍历法 ​
javascript
function func(tree) {
  if (!tree) return
  func(tree.left)
  console.log(tree.data)
  func(tree.right)
}

代码实现，只是把打印位置放在另外一个位置，等左节点都遍历完后，从最底层的左节点开始一个个打印

遍历顺序：hkdbeaifcgj

后序遍历法 ​
javascript
function func(tree) {
  if (!tree) return
  func(tree.left)
  func(tree.right)
  console.log(tree.data)
}

遍历顺序：khdebifjgca

已知前序和后序，是不能确定一颗二叉树；已知前序或后序，和中序，才能确定

层序遍历 ​

按每层输出

下面这种是取巧方法，利用 level 确定当前是第几层，然后前序遍历，保证顺序

javascript
var levelOrder = function(root) {
  if (!root) return []
  const output = []
  function get(node, level) {
    if (!output[level]) output[level] = []
    output[level].push(node.val)
    if (node.left) get(node.left, level + 1)
    if (node.right) get(node.right, level + 1)
  }
  get(root, 0)
  return output
};

利用队列的性质，每次循环一层级的节点

javascript
var levelOrderBottom = function(root) {
  if (!root) return []
  const output = []
  const queue = []
  queue.push(root)
  while(queue.length) {
    const size = queue.length
    let i = 0
    const tmp = []
    while (i < size) {
      const target = queue.pop()
      tmp.push(target.val)
      if (target.left) queue.unshift(target.left)
      if (target.right) queue.unshift(target.right)
      i++
    }
    output.push(tmp)
  }
  return output
};
还原二叉树 ​

先序排列：

  1. 第一个值，是二叉树的根的值
  2. 一棵小树（最多三个结点），肯定是连续排列的

中序排列：

  1. 根结点左边的值是左树
  2. 根结点右边的值是右树

后序排列：

  1. 最后一个值，是二叉树的根的值

我们可以根据先序和后序找出二叉树的根的值，再跟进中序排列的性质，还原二叉树

根据先序和中序还原 ​

javascript
/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {number[]} preorder
 * @param {number[]} inorder
 * @return {TreeNode}
 */
var buildTree = function(preorder, inorder) {
    if (!preorder.length) return null;
    const inMap = {}
    const pLen = preorder.length
    const iLen = inorder.length
    let i = 0
    while (i < inorder.length) {
        inMap[inorder[i]] = i
        i++
    }
    function check(pF, pL, iF, iL) {
        if (pF > pL) return null

        const node = new TreeNode(preorder[pF])
        const mid = inMap[preorder[pF]]
        const left = mid - 1 // 左侧的 iL
        const right = mid + 1 // 右侧的 iF
        const matchNum = mid - iF

        node.left = check(pF + 1, pF + 1 + matchNum - 1, iF, left)
        node.right = check(pF + 1 + 1 + matchNum - 1, pL, right, iL)

        return node
    }
  

    return check(0, pLen - 1, 0, iLen - 1)
};
根据先序和后序还原 ​

后序的排列，是反着来，从后面开始，最后一位是树的根。在构建树时，因为是反着来，所以要先构建右树

javascript
/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {number[]} inorder
 * @param {number[]} postorder
 * @return {TreeNode}
 */
var buildTree = function(inorder, postorder) {
  if (!postorder.length) return null
  const inMap = {}
  const inLen = inorder.length
  const postLen = postorder.length
  let i = 0
  while(i < inLen) {
      inMap[inorder[i]] = i
      i++
  }
  let pindex = postLen - 1
  function check(inF, inL) {
      if (inF > inL) return null
      const val = postorder[pindex]
      const node = new TreeNode(val)
      const mid = inMap[val]
      pindex--
      node.right = check(mid + 1, inL)
      node.left = check(inF, mid - 1)
      return node
  }

  return check(0, inLen - 1)
};
赫夫曼树 ​
解析 ​

带权路径长度 WPL 最小的二叉树就是赫夫曼树

权：就是某结点上一个数值

结点的带权路径长度：该结点到根之间的路径长度 * 该结点的权

树的带权路径长度：所有带权结点的路径综合

假设有 n 个结点的二叉树，每个结点的带权为： $$w_k$$ ，每个结点的路径长度：1k；那这颗二叉树就是赫夫曼树

二叉树 a 的带权路径：1 * 5 + 2 * 15 + 3 * 40 + 4 * 30 + 4 * 10 = 315

二叉树 b 的带权路径：3 * 5 + 3 * 15 + 2 * 40 + 2 * 30 + 2 * 10 = 220

赫夫曼树的性能提高了 1/3

如何构造赫夫曼树 ​
  1. 先把所有带权的结点从小到大排序： A5, E10, B15, D30, C40
  2. 去最小权限的两个结点，组成一个节点 N1，小的结点在左
  3. 将 N1(5+10) 插入序列排序，重复步骤 2
  4. 直到所有原结点都组合了

赫夫曼编码 ​

需要编码的字符集 {d1,d2,d3,…dn}，各个字符出现的频率{w1,w2,w3,…wn}。以 d1 ~ dn 作为叶子结点，以 w1 ~ wn 作为相应叶子结点的权值来构造一棵赫尔曼树。左分支代表 0 ，右分支代表 1，从根结点到叶子结点经过组成的 0/1 序列，则为该字符的赫尔曼编码

我的理解：赫夫曼编码，利用带权的二叉树，对字符进行编码。这样根据字符的权重，提升每个字符解析的速度。比如 A 字符是经常出现的，我就把它的赫夫曼编码权重级高点，能快速找到它

图 ​

图（Graph）是由顶点的有穷非空集合和顶点之间边的集合组成，通常表示：G(V, E)，其中，G 表示图，V 是图 G 中顶点的集合，E 是图 G 中边的集合

定义/性质 ​

顶点：数据元素

图结构，肯定至少存在一个顶点

无序偶对：(vi, vj)

无向边（Edge）：顶点间没有方向的边。用无序偶表示

无向图：所有边都是无序的

无向完全图：任意两个顶点之间都存在边

有 n 个顶点的无向完全图，有 n*(n - 1)/2 条边

顶点 v 的度：就是该点有多少条边，记为 TD(v)

边数 = 各顶点度数的和 / 2

该图用代码表示：

设该图为 G1; G1 = (V1, {E1})

顶点集合 V1 = {A,B,C,D}

边集合 E1 = { (A,B), (B,C), (C,D), (D,A), (A,C) }

有向边/弧（Arc）：两个顶点的边是有方向的

有序偶：<vi, vj>；vi 是弧尾（Tail），vj 是弧头（Head）

有向图：所有的边都是有向边

有向完全图：任意两个顶点之间都存在边

有 n 个顶点的有向完全图，有 n*(n - 1) 条边

<v, v1> 称为顶点 v 邻接顶点 v1；顶点 v1 邻接自顶点 v

入度（InDegree）：以顶点 v 为头的弧的数目称为 v 的入度，ID(v)

出度（OutDegree）：以 v 为尾的弧的数目称为 v 的出度（OutDegree），OD(v)

TD(v) = ID(v) + OD(v)

该图用代码表示：

设该图为 G2; G2 = (V2, {E2})

顶点集合 V2 = {A,B,C,D}

边集合 E2 = { <A,D>, <B,A>, <C,A>, <B,C> }

有很少的边或弧，称为稀疏图，否则是稠密图。这里的量级是模糊的。

权：边或弧带数的

网：带权的图

子图：有两个图 G1 和 G2；如果 v2 <= v1 && E2 <= E1，则 G2 是 G1 的子图

路径：两顶点间（m,n）由边构成的称为路径。i <= m <= n。也就是路径最小要有两条边

回路/环：第一个顶点到最后一个顶点相同的路径

简单路径：序列中顶点不重复出现的路径

简单回路/简单环：除第一个和最后一个顶点外，其余顶点不重复出现的回路

存储结构 ​

邻接矩阵 ​

顶点用一维数组存储；边用二维数组存储

缺点：

  1. 如果边数相对于顶点较少的情况下，会存储大量无用数据，浪费空间
邻接表 ​

数组和链表相结合的方式

顶点用以为数组存储，每个顶点的邻接点用单链表存储

缺点：

  1. 要了解出度情况，要遍历整个表
十字链表 ​
邻接多重表 ​
边集数组 ​

遍历 ​

前序遍历

层序遍历

查找 ​

有序查找 ​

二分法 ​

插值法 ​

斐波那列 ​

线性索引查找 ​

稠密索引 ​

将每行数据使用索引存储，使用线性存储 [关键吗，指针]；当要查找某个索引时，可以根据折半、插值、斐波那锲等有序查找算法进行查询

缺点：

当数据量非常大的时候，索引也非常巨大，性能会下降

分块索引 ​

条件：

  1. 块内无序
  2. 块间有序
    1. 比如第二块所有记录的关键字均要大于第一块中所有记录的关键字，以此类推

将每块数据集，生成对应的索引项，索引项包含下面的数据：

  1. 最大关键码
  2. 存储块中的记录个数
  3. 指向块首数据元素的指针

查询规则：

  1. 先查关键字所在的块，因为块间是有序的，可以使用有序算法快速查询
  2. 找到对应的块后，再使用顺序查找内容

优点，大大增加了整体查找的速度，普遍用于数据库表查找

倒排索引 ​

根据属性的值来查找记录

索引项的通用结构：

  1. 次关键码，比如某个单词
  2. 记录号表，比如文章 id；而且存储具有相同次关键字的所有记录的记录号

优点：查找记录非常快

二叉排序树 ​

算法 ​

算法的基本特性：输入、输出、又穷性、正确性和可行性

算法时间复杂度 ​

T(n) = O(f(n)) , f(n) 是问题规模 n 的某个函数

O() -> 大 O 记法

推导大 O 阶：

  1. 用常数 1 取代运行时间中的所有加法常数
  2. 在修改后的运行次数函数中，只保留最高阶项
  3. 如果最高阶项存在且不是 1，则去除与这个项相乘的常数

得到的结果就是大 O 阶

常数阶 ​

c
int sum = 0, n = 100; // 执行一次
sum = (1 + n) * n / 2; // 执行一次
printf(sum); // 执行一次

这里的时间复杂度是： O(1)；上面的运行次数是 f(n) = 3；

根据第一条规则，用 1 取代所有加法常数

第三条规则不匹配，所有最终结果是 O(1) 而不是 O(3)

对于分支结构，无论真假，执行次数都是恒定的，不会随 n 的变大而变化，所以时间复杂度都是 O(1)

线性阶 ​

关键分析循环结构部分

c
int i;
for ( i = 0; i < n; i++ )

该算法的执行次数，会随着 n 的变化而变化，所以时间复杂度为：O(n)

对数阶 ​

c
int count = 1;
while (count < n) {
  count = count * 2
}

每次执行，count 都会乘以 2；由 $$ 2^x = n -> x=log_2n $$ 时间复杂度为 $$ O(logn) $$

平方阶 ​

c
int i, j;
for (i = 0; i < n; i++) {
  for (j = 0; j < n; j++) {}
}

因为这里是嵌套循环，时间复杂度为： $$ O(n^2) $$

c
int i, j;
for (i = 0; i < n; i++) {
  for (j = i; j < n; j++) {}
}

这里将 j=0 改为 j=i，看起来，相对减少了循环次数

执行总次数为： $$ n + (n - 1) + (n - 2) + … + 1 = n^2/2 + n/2 $$ 根据规则推导：

第一条没有加分常数，不考虑

第二条，只保留最高阶项，也就是 $$n^2/2$$

第三条，去除这个项相乘的常数 -> 除以 1/2

最终得到还是 $$O(n^2)$$

常见的时间复杂度 ​

阶非正式术语
O(1)常数阶
O(n)线性阶
$$O(n^2)$$平方阶
$$O(logn)$$对数阶
$$O(nlogn)$$nlogn 阶
$$O(n^3)$$立方阶
$$O(2^n)$$指数阶

算法空间复杂度 ​

Sn = O(f(n)) -> f(n) 为 n 所占存储空间的函数

通常说的复杂度，都是指时间复杂度

稳定排序/不稳定排序 ​

$$k_i = k_j$$(i <= i <= n, i <= j <= n, j != i)

且排序前的序列中 $$r_i$$ 领先于 $$r_j$$ 既 i < j

如果排序后 $$r_i$$ 仍领先于 $$r_j$$ ，则是稳定，小于的话就是不稳定

内排序 ​

整个排序过程中，待排序的所有记录存在内存中

外排序 ​

内外存之间多次交换数据才能进行

双指针 ​

双指针，指的是在遍历对象的过程中，不是普通的使用单个指针进行访问，而是使用两个相同方向（快慢指针）或者相反方向（对撞指针）的指针进行扫描，从而达到相应的目的。(引用自网上文章)

对撞指针 ​

对一个有序数组，进行前后遍历。凡是看到“有序”，“数组”这些关键词，就可以想下双指针

javascript
while (a === n) {
  if () {
    // ...
    i++
  } else {
    // ...
    j--
  }
}

滑动窗口 ​

滑动窗口算法可以用以解决数组/字符串的子元素问题，它可以将嵌套的循环问题，转换为单循环问题，降低时间复杂度。（引用自知乎）

类似上图这样

对一个数组，设置的开始和结束值

比如在 a 情况下，结束位置向右移动

在 b 情况下，开始位置向右移动

数字取反 ​

比如有数字 123321，在不转为字符串的情况进行取反

javascript
var num = 0
var x = 123321
while (x > num) {
  num = num * 10 + x % 10
  x = Math.floor(x / 10)
}

快速取幂 ​

快慢指针 ​

二分法 ​

binary search algorithm，是一种在有序数组中查找某一特定元素的搜索算法。

搜索过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜索过程结束；如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空，则代表找不到。这种搜索算法每一次比较都使搜索范围缩小一半。

搜索升序数组的目标值：

javascript
function searchInsert(nums, target) {
  var left = 0
  var len = nums.length
  var right = len - 1
  var mid = 0
  while (left <= right) {
    mid = Math.floor((left + right) / 2)
    if (nums[mid] > target) {
      right = mid - 1
    } else if (nums[mid] < target) {
      left = mid + 1
    } else {
      return mid
    }
  }
  return left
}

二分法的情况：

左闭右闭、左闭右开

第一种即左闭右闭，所以我们的终止条件肯定是 left > right所以我们的循环条件就出来了，又因为我们是左闭右闭，所以在进行划分区间时，已经判断了该值，所以是mid -/+ 1。因为我们是缺少某个元素，所以不可能出现nums[i] < i的情况。我们的终止的条件可以试想一下必定有一个位置出现值大于我们的索引号，比如题目的8的位置是9，这时我们的left和right都指向的8，再做一次判断right就指向前一位元素了循环终止，所以我们返回的是left。

第二种即左闭右开，所以我们的终止条件肯定是 left = right所以我们的循环条件就出来了。又因为我们是左闭右开，所以在进行划分区间时，左边left已经判断了该值，所以是mid + 1。右边是我们的哨兵元素所以是mid，mid-1就会忽略掉一个元素。因为我们是缺少某个元素，所以不可能出现nums[i] < i的情况。我们的终止的条件可以试想一下必定有一个位置出现值大于我们的索引号，比如题目的8的位置是9，这时我们的left不断右逼到指向8，再做一次判断right也指向了8循环终止，所以我们返回的left和right都可以。

作者：lan-zhe-xian 链接：https://leetcode-cn.com/problems/que-shi-de-shu-zi-lcof/solution/xiang-jie-er-fen-cha-zhao-de-liang-chong-kai-bi-qi/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

贪心算法 ​

贪心算法是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。

贪心算法得出的结果不一定是最优解，选择贪心策略必须具备“无后效性”（某个状态以后的过程不会影响以前的状态，只与当前状态有关）

贪心算法在有最优子结构的问题中尤为有效。最优子结构的意思是局部最优解能决定全局最优解

贪心算法与动态规划的不同在于它对每个子问题的解决方案都做出选择，不能回退。动态规划则会保存以前的运算结果，并根据以前的结果对当前进行选择，有回退功能。

动态规划 ​

动态规格三个重要的概率

最优子结构 ​

边界 ​

状态转移公式 ​

冒泡排序 (bubble sort) ​

基本原理：两两比较相邻记录的关键字，如果反序则交换，直到没有为止

复杂度为 $$O(n^2)$$

比如 [1,2,3,4]

排序情形就是：

第一轮：[2,1,3,4] -> [3,1,2,4] -> [4,1,2,3]

第二轮：[4,2,1,3] -> [4,3,1, 2]

第三轮：[4,3,2,1]

第一轮就是拿索引值为 0 的值，和后面的数值进行比较，如果大的，就替换到索引 0 的位置

如此类推直到结束

最简单的冒泡排序

javascript
function bubbleSort(data) {
  for (let i = 0, len = data.length; i < len; i++) {
    for (let j = i + 1; j < len; j++) {
      if (data[i] < data[j]) {
        const o1 = data[i]
        data[i] = data[j]
        data[j] = o1
      }
    }
  }
  return data
}

这种排序方式，最差的循环次数是：$$n^2 - n*(n+1)/2$$ -> $$(n^2-n)/2$$

优化版：

而这种优化后的冒泡排序，第二层的循环是从后面开始，然后使用两两比较的方式，当前索引和下一个索引进行比较，如果当前的大了，把它往后排；这样就能保证这一层循环后，最小的数会被移到最左边

javascript
function bubbleSort(data) {
  for (let i = 0, len = data.length; i < len; i++) {
    for (let j = len - 1; j >= i; j--) {
      if (typeof data[j + 1] === 'number' && data[j] > data[j + 1]) {
        const o1 = data[j]
        data[j] = data[j + 1]
        data[j + 1] = o1
        isChange = true
      }
    }
  }
  return data
}

第三版：

比如：[4,3,2,1]；我们按照优化版来循环，发现第一轮循环是没改变过了，这样会有个规律：a0 > a1 > a2 > a3；其实这样已经是排好序了，后面几轮的循环都是无意义的。那我们就可以在某轮发现没有替换的话，就跳出完成

javascript
function bubbleSort(data) {
  for (let i = 0, len = data.length; i < len; i++) {
    let isChange = false
    for (let j = len - 1; j >= i; j--) {
      if (typeof data[j + 1] === 'number' && data[j] > data[j + 1]) {
        const o1 = data[j]
        data[j] = data[j + 1]
        data[j + 1] = o1
        isChange = true
      }
    }
    if (!isChange) {
      console.log('change:', data)
      return
    }
  }
  return data
}

而要排正序的话，第一个版本只要把 < 改成 >；而优化版却不行，因为：

倒序是把大的数往前面移，

简单选择排序(Simple Selection Sort) ​

从 n-i+1 中选出关键字最大的记录，与 i 进行交换

javascript
function simpleSort(data) {
  const len = data.length
  let index = 0
  let max = 0
  for (let i = 0; i < len; i++) {
    max = i
    for (let j = i + 1; j < len; j++) {
      index += 1
      if (data[max] > data[j]) {
        max = j
      }
    }
    const tmp = data[i]
    data[i] = data[max]
    data[max] = tmp
  }
  console.log(index)
  return data
}

简单来说，两重循环，二循环从 i + 1 开始，在 i 后面的值包含 i 中最大的值，然后和 i 进行替换

这个比冒泡排序的优点是：减少交换操作

复杂度：

$n - 1 + n - 2 + … + 1 = n(n - 1) / 2$ -> $O(n^2)$

虽然时间复杂度和冒泡是一样的，但是减少了交换的操作，性能还是优于冒泡排序

直接插入排序（Straight Insertion Sort） ​

一开始选择第二个点作为锚点，往右循环，变动锚点，向左进行二次循环判断，如果有值小于/大于锚点值，上一个值（j - 1）赋值到该索引值上；二次循环判断有相反结果，停止循环；二次循环结束后，将锚点值插入到 j 值上

原理是构建有序序列，将要插入的值，在有序序列进行循环查找，合适的位置后，最后进行插入

javascript
function starightSort(data) {
  let index = 0
  for (let i = 1; i < data.length; i++) {
    let key = data[i]
    let j = i
    for (; j > 0; j--) {
      index += 1
      if (key >= data[j - 1]) {
        break
      }
      data[j] = data[j - 1]
    }
    data[j] = key
  }
  console.log(index)
  return data
}

记录排序的移动次数最大值：$(n + 4)(n - 1)/2$

时间复杂度：$O(n^2)$

性能会比冒泡和简单选择排序要好

希尔排序 ​
javascript
function shellSort(arr) {
  const len = arr.length;
  let gap = Math.floor(len/2);
  while(gap!==0){
    for (var i = gap; i < len; i++){
      const temp = arr[i];
      let j;
      for (j = i - gap; j >= 0 && temp < arr[j]; j -= gap){
        arr[j + gap] = arr[j];
      }
      arr[j + gap] = temp;
    }
    gap = Math.floor(gap/2);
  }
  return arr;
}

原理：先将整个数组，按增量序列进行划分多个小组，然后每个小组各自进行插入排序，然后多个小组形成一个“基本有序”的数组；直到增量值等于 1 后，最后再直接插入排序

时间复杂度为： $O(n^{3/2})$

归并排序 ​

快速排序 ​

原理：

通过分治进行排序。它会将数组拆分成一个个小处理，通常以每次循环的第一个值为基准，用左右两个指针，将要处理的数组范围，比基准值小的放在左边，大的放在右边，当两个指针重叠时，将左右划分好的范围各自重新再处理，也就是用递归。

javascript
function quickSort(nums) {
  function check(start, end) {
    if (start >= end) return
    const target = nums[start]
    let i = start
    let j = end
    while(i < j) {
      while (i < j && nums[j] > target) {
        j--
      }
      // 当前 nums[j] < target，就要进行移动
      if (i < j) {
        // 此时的 i 还是 start 的值，所以直接替换不怕
        nums[i] = nums[j]
        i++
      }
      while (i < j && nums[i] < target) {
        i++
      }
      if (i < j) {
        nums[j] = nums[i]
        j--
      } 
    }
    nums[i] = target
    check(start, i - 1)
    check(i + 1, end)
  }

  check(0, nums.length - 1)
  return nums
}