算法：一个计算过程，解决问题的方法

时间复杂度：用来评估算法运行效率的一个东西 时间复杂度: O(1)<O(logn)<O(n)<O(nlogn)<O(n^2)<O(n^2logn)<O(n^3) 如何判断时间复杂度: 循环减半的过程-->O(logn) 几次循环就是n的几次方的复杂度

空间复杂度：用来评估算法内存占用大小

空间换时间

递归 递归的两个特点： 调用自身(调用子问题) 结束条件

汉诺塔问题： n个盘子时： 1.把n-1个圆盘从A经过C移动到B 2.把第n个圆盘从A移动到C 3.把n-1个小圆盘从B经过A移动到C 时间复杂度: h(x)=2h(x-1)+1 ---> h(x)=2^n-1

列表查找: 1)顺序查找：从列表第一个元素开始，顺序进行搜索，直到找到为止(for循环),时间复杂度:O(n) 2)二分查找: 从有序的候选区data[0:n]开始，通过查找的值和中间值的比较可以使得候选区减少1半,时间复杂度O(logn)

排序low B三人组 1.冒泡排序：两两比较，如果比较大，大的数往上浮，每一趟让有序区增加最大值 代码关键点： 趟: n-1 无序区:n-i-1,当i=0的时候 冒泡排序-优化: 如果冒泡排序中执行一趟而没有交换，则列表已经是有序的状态，可以直接结束算法。

2.选择排序: 小数被放到下面
    代码关键点:
        趟数：n-1
        无序区：
    
3.插入排序：扑克牌
    代码关键点:
         摸到的牌、手里的牌       
low B 三人组总结:
    冒泡排序、插入排序、选择排序
        时间复杂度：O(n^2)
        空间复杂度：O(1),没有开辟新的空间

排序NB 三人组 快速排序： 1.取一个元素P,使元素P归位 2.列表被P分为两部分，左边都比P小，右边都比P大 3.递归完成排序 时间复杂度： 1.一般的情况,数据拆分为大小相同的两部分，深度为logn 时间复杂度:O(nlogn); 最坏的情况,数据拆分为1端为1个元素，1端为n-1个元素，深度为n 时间复杂度:O(n^2) 2.快速排序会出现爆栈的情况

堆前传：
树的度:一个节点下面分几个叉，叉的个数最多有多少个，树的度就有多少个
二叉树：度不超过2的树(节点最多有两个叉)
完全二叉树：最下面一层的节点都集中在该层最左边的若干位置的二叉树
二叉树的存储方式:
链式存储方式
顺序存储方式
i-->2i+1(左),2i+2(右)
i-->(i-1)/2
树-->二叉树-->完全二叉树-->堆

堆排序：
1.大根堆：一颗完全二叉树，满足任一节点上标的数字都比其孩子节点大
2.小根堆：一颗完全二叉树，满足任一节点上标的数字都比其孩子节点小
3.当根节点的左右子树都是堆时，可以通过一次向下的调整来将其变成一个堆
4.堆排序过程:
 4.1 建立堆
 4.2 得到堆顶元素为最大元素
 4.3 去掉堆顶，将堆最后一个元素放到堆顶，此时可通过一次调整重新使堆有序
 4.4 堆顶元素第二大元素
 4.5 重复步骤3，直到堆变空
 
归并排序：
1.假如现在的列表分两段有序，如何将其合成为一个有序列表
2.如何使用归并排序：(分解，合并)
    分解：将列表越分越小，直至分成一个元素
    终止条件：一个元素是有序的
    合并：将两个有序列表归并，列表越来越大。
3.时间复杂度O(nlogn),空间复杂度O(n)

NB三人组的总结:
时间复杂度:O(nlogn)
快和慢的时间:快速排序>归并排序>堆排序   
排序算法的缺点：
    快速排序:极端情况下排序效率低
    归并排序：需要额外的内存开销
    堆排序：在快的排序算法中相对较慢

线性时间排序： 计数排序:求出最大值，然后使用计数排序，一个位置表示该数出现的次数，缺点是浪费空间 桶排序:分桶，桶内进行插入排序，桶排序的表现取决于数据的分布 基数排序:多关键字排序，先按照个位，十位，百位...这样进行排序 时间复杂度:O(n)

希尔排序:分组插入排序算法。 1.首先取一个整数d1 = n/2,将元素分为d个组，每组相邻量元素之间距离为d1，在各组内进行直接插入排序 2.取第二整数 d2 = d1/2,重复上述排序，直到di=1 3.希尔排序每趟并不使某些元素有序，而是使整体数据越来越接近有序，最后一趟排序使得所有元素有序。

算法的稳定度： 1 2 4 2 --> 1 2 2 4 稳定： 位置不会发生变化 (相邻交换) 不稳定: 位置会发生变化 (跳动式交换)

排序动画网站: https://visualgo.net/en/sorting 4399小游戏可以展示汉诺塔游戏