408数据结构笔记(依据大纲来定)

一：线性表

定义：具有相同类型数据的n个元素的序列(相同数据类型，有限序列，序列就是有逻辑上的顺序性，元素有先后次序)
线性表是一种逻辑结构，包含两种存储方式：顺序存储和链式存储。
逻辑结构和存储结构：
逻辑结构：集合，线性，树形，图形(表明元素之间的关系)
存储结构：顺序，索引，链式在，散列(表明元素的存储结构)

1.顺序存储

逻辑上相邻的两个元素，物理位置上也相邻，插入删除需要移动大量元素。
时间复杂度：插入，删除的时间复杂度是O(n)
查找时间复杂度：按值查找是O(n),按照位置查找是O(1),顺序存储有着随机存取的性质：随机存取就是可以按照地址访问数据

2.链式存储

有着单链表，循环双链表，循环单链表，静态链表。
链表的几种判空：

1.没有头结点的链表判空 head==null
2.有头结点的判空head->next==null
3.循环单链表的判空：L->next==null
4.循环双链表的判空：L->next==null&&L->prior==null
链式存储的插入，删除时间复杂度还需要因地制宜，例如头插法时就是O(1),中间插入就是O(n)，
3.两种可以记忆一下的时间复杂度
有序单链表的生成：O(nlog2^n),,,有序顺序表的按值查找O(log2 ^n)
4.静态链表：预先分配一块连续的存储空间，适合数据元素固定不变的场景:比如操作系统的文件分配表FAT，静态链表以next==-1作为结束标志，插入删除和动态链表相同。
1
2
3
4
5
6
7
8

题目：
1.单链表增加头结点的意义：方便运算的实现
2.把一个时间复杂度n的单链表链接在长度为m的单链表的后面的时间复杂度O(m):遍历单链表m，找到尾指针，使其指向单链表n的首结点。
3.尾指针：作用为增加尾部的新结点不需要从头到尾巴遍历一遍(包括删除首结点和在首结点前面增加结点)，但是删除最后一个结点的时候，需要从头到尾遍历，然后置其前驱结点的指针域为NULL
4.双链表可以方便的访问前驱和后继，所以删除和插入数据较为方便
5.在末尾结点插入和删除(找末尾结点的前驱)，带头结点的循环双链表最好，可以快速找到尾巴结点的前驱。

二：栈和队列和数组

栈：只允许一端进行插入删除操作的线性表(栈顶)，卡特兰数：n个元素进栈后出栈元素不同排列的个数C(2n,n)/n+1
队列：操作受限的一种表，只允许在表的一端插入，一端删除，插入数据的一端为队尾，删除数据的一端为队首

栈：

1.栈的顺序存储：

栈的初始化：S.top=-1;
栈的判空：S.top==-1;
栈的入栈：S.data[++S.top]=X;指针加一再入栈
栈的出栈：X=S.data[S.top--];先出栈，指针再减一
判断栈满：S.top==Maxsiza-1;
栈的长度：S.top+1
若栈顶指针S.top=0;则栈顶指针指向栈顶元素的下一个位置，此时入栈为S.data[S.top++]=X;出栈为X=S.data[--S.top]
1
2
3
4
5
6
7

2.共享栈
利用栈底位置相对不变的特性，两个顺序栈共用一个空间，栈底设置在共享空间的两端，栈顶向共享空间的中间延伸。

判断栈空：stack1:S.top==-1, stack2:S.top==MAXSIZE;
判断栈满：top2-top1=1;
进栈时，栈1是指针加一再赋值，栈二是指针减一再赋值，出栈则刚好相反。
共享栈的目的：节省存储空间，防止上溢。
3.栈的链式存储
采用单链表的形式存储，所有操作都在链头进行，便于多个栈共享存储空间，更好的利用空间资源，避免上溢。
链栈插入结点的操作：x->next=top,top=x;
总结：栈，不管顺序栈还是链栈，入栈都是指针加一再赋值
题目：
1.共享栈的目的：节省存储空间，防止上溢，因为都是在栈顶操。l“作，所以只可能发生上溢
2.卡特兰数：适合于n个数的情况，如果有特定某个元素做为开头不适用
3.系统调用时，系统需要用栈保存必要的信息

队列

1.队列的顺序存储

分配一块连续的存储空间，并且配上两个指针，队首指针front指向队头，队尾指针rear指向队尾的下一个位置

出队：队不空时：取队首元素，队首指针加一
入队：队不满：送值到队尾，队尾指针加一
队列初始化：Q.rear=Q.front=0;
判空：Q.rear==Q.front==0;
判满：由于无法判满，引出循环队列
1
2
3
4
5

2.循环队列(顺序存储结构)

初始化：Q.rear=Q.front=0;
入列：(Q.rear+1)%MAXSIZE
出列：(Q.front+1)%MAXSIZE
队列空的条件：Q.rear==Q.front
判断队满：

1.牺牲一个存储单元：队尾指针的下一个位置是队首指针，此时队满
(Q.rear+1+MAXSIZE)%MAXSIZE=Q.front
队空的条件：Q.rear==Q.front
队长：(Q.rear-Q.front+MAXSIZE)%MAXSIZE
2.增设表示数据元素个数的数据成员Q.size
队空：Q.size==0;
队满：Q.size==MAXSIZE;
3.增设数据成员tag
当Q.rear==Q.front时,tag==0,队空，tag==1时，队满
1
2
3
4
5
6
7
8
9

3.队列的链式存储

带有队首指针和队尾指针的单链表

判空：Q.rear==Q.front==NULL
1

双端队列：两端同时可以插入和删除的队列
输入受限：某一端只能删除不能输入的双端队列
输出受限：某一端只能插入不能删除的双端队列
最适合链队的链表：带首尾指针的非循环单链表
题目：
1.队列首尾指针：front和rear，如果插入一个数，要求存储在A[0]，那么初始值rear=n-1,front=0；
解析;初始化时候：rear=front=0;又因为插入和rear有关，插入后指针要指向0，又因为rear=(
rear+1)%n=0；所以rear=n-1;

4.队列，栈和数组的应用

一：栈的应用

1.括号匹配：
遇到左括号入栈，遇到右括号出栈，匹配后栈非空，则匹配失败
2.表达式求值(前缀表达式，中缀表达式，后缀表达式)
前缀表达式：+ab 中缀表达式：a+b 后缀表达式：ab+
中缀表达式转后缀表达式：

1.确定好顺序，表达式中有括号第一顺序，括号外乘除优先加减
2.选择一个运算符，按照(左操作数，右操作数，运算符的顺序)，形成一个新的操作数
例子：
中缀：a+b*(c-d)-e/f    转成的后缀：  abcd-*+ef/-
确定好运算顺序，这里的运算顺序是
(c-d)-->b*(c-d)-->a+b*(c-d)-->a+b*(c-d)-e/f
这里以c-d为第一顺序，所以以它分左右，ef在左边运算符的右边
1
2
3
4
5
6
7

**中缀转前缀表达式：**和转后缀一样的方法，不过此时是按照(运算符 ，左操作数，右操作数)的方式
前缀表达式的机算：
1.从右往左扫描，遇到操作数压入栈内，遇到运算符，弹出栈的两个操作数，得出的结果压入栈顶
后缀表达式的机算：
1.从左往右扫描：遇到操作数压入栈内，遇到运算符，弹出栈的两个操作数，得到的结果压入栈顶
中缀表达式的机算：
1.初始化两个栈
2.从左到右扫描，操作数入操作数栈，运算符和界限符进入另一个栈
3.运算符若是优先级高于栈顶运算符或空栈，则压入栈顶，如果低于栈顶运算符，则弹出两个操作符，用当前运算符栈顶元素运算，运算结果入栈顶，若是同级，比如加减，默认栈顶高半级。遇到界限符(,(继续入栈,遇到)，则开始弹出栈顶两个元素，运算，知道遇到(,结束。
中缀表达式机算看起来复杂，但是一般选择题出现，自己列一个表达式，带入选项给的方法就行，不用死记。

二：队列的应用

1.解决主机与外设速度不匹配的问题：打印机
2.解决多用户引发资源竞争的问题：先进先出cpu分配给用户使用
3.图的广度优先遍历，二叉树的层次遍历：队列作为辅助空间(先序，中序，后序用栈实现)

三：数组的应用

1.多维数组的存储
行优先，一行一行存储；列优先：一列一列存储，，，这个对应位置的公式当场推就行
2.特殊矩阵的压缩存储：
对相同的元素分配一个存储空间，对零元素不分配存储空间，这是为了节省空间，常见的特殊矩阵有对称矩阵，三角矩阵，三对角矩阵，稀疏矩阵

元素下标计算公式的核心：等差数列前n项和公式：n*(首项+末项)/2
对称矩阵：关于左对角线对称的矩阵
k=i*(i-1)/2+j-1 ;i>=j(下三角区域和对角线元素)，按照行优先
k=j*(j-1)/2+i-1;j>=i(上三角区域)，列优先
三角矩阵：下三角矩阵（上三角区域所有元素均为同一常量）
k=i*(i-1)/2+j-1; i>=j(下三角区和主对角线元素)
k=n(n+1)/2  ;ij(下三角区元素)
三对角矩阵：在一维数组B中存放的下标为K=2i+j-3;
稀疏数组：存储方式：三元组 ，将非零元素及其相应的行和列构成一个三元组（行标，列标，值）

对称矩阵，三角矩阵，三对角矩阵三种压缩后仍然有着随机存取的特性，稀疏矩阵压缩存储后便失去了随机存取的特性
1
2
3
4
5
6
7
8
9
10
11
12
13
14

记住两个就行(其他现场推就行，记得根据题目情况看一般数组第一个位置是0)：
1.对于三角矩阵，对角线一边全是一个数的记得存储一次，位置k=n*(n+1)/2
2.三对角矩阵：除了三条对角线，其余为零，这个时候位置k=2i+j-3
稀疏矩阵：非零元素比较多，采用三元组进行存储**(行标，列标，值)**表示。
压缩后，稀疏矩阵失去随机存取的特性，其他三种压缩还是有对应特性的。
题目
1.消除递归使用循环for就可以，不一定要使用栈
2.手工写出对应中缀表达式的前缀和后缀表达式
((a/b)+(((cd)-(ef))/g))
转化为后缀表达式：把运算符移动到对应的括号后面,然后去掉括号
转化为前缀表达式：把运算符移动到对应括号的前面，然后去掉括号
3.机械将中缀表达式转化为后缀表达式：注意规则：
a.若为(,入栈
b.若为），把栈内所有元素退出直到(,然后从栈中删除(
c.若为括号外的其他元素，若当前栈顶元素的优先级高于当前扫描到的元素(+,-下，栈顶高半级，所以扫描到-号时，此时栈顶是+号，则要弹出+号，再入栈-)，则弹出栈顶元素，直到优先级相等，或者是碰到(，此时当前元素入栈
4.适合压缩矩阵存储的是：十字链表和三元组表，需要存储列，行和值
5.这种求对应数组下标的，如果是对称矩阵：一定要看清楚是按照行还是列，自己画图，根据累加计算，如果按照上三角行优先存储是10*10的矩阵，此时问坐标(7,2),此时明显不是上三角，则转为(2,7)映射算出对应的数组下标
6.三对角矩阵：2i+j-3

三：串

简单的模式串匹配：会导致指针回溯，增加时间的开销
改进的模式串匹配：KPM算法
改进的算法中子串和模式串不匹配时，主指针不会回溯，主指针跳到next[j]，继续匹配。

next[j]=数组S(由1到j-1个字符组成的串)的最长相等前后缀长度+1；
特殊：next[1]=0;以上串在数组的位置是由1开始，若是从0开始，则不用整体加一，此时next[1]=-1

四：树和二叉树

1.树的基本概念

1.树是一种逻辑结构，也是一种分层结构，树的根节点没有前驱，除根节点外的节点有一个前驱，
所有结点的后继可以是N个
2.结点和树的度：结点的度是结点的孩子树，最大的结点的度为树的度
3.叶子结点：度为0的结点
4.结点的层次，深度，高度：
层次=深度：从根节点开始累加 高度：叶结点开始累加
5.树的高度：树中结点的最大层次
6.有序树，无序树：树中结点各子树从左到右是否有次序
7.路径和长度：路径：两节点所经过的结点序列，路径长度：经过的边的个数
8.森林：树的根节点删去就成了森林
m叉树和度为m的树：
m叉树：任何子树的结点<=m,可以全部小于m,可以为空树
度为m的树：至少有一个节点的度等于M,不可能是空树，树的结点个数最少是m+1
由m叉树引出的问题：
高为h的m叉树最多的结点树：(m^h-1)/m-1 利用等比数列求和
具有n个结点的m叉树的最小高度：利用上面的最多结点做算式得出

9.树的路径长度：根节点到每一个叶子结点的路径长度之和
10.结点度之和=分支(边数)=结点数-1
题目：
1.告诉各种结点度的个数(除了叶节点)，求叶节点个数：用结点度总数+1=所有结点数n；n-前面告知的度非0的结点总数

2.二叉树的概念

1.一些定义
二叉树是有序树，有左右之分，次序不能任意颠倒，每个结点最多两个子树，二叉树可以为空树
特殊的二叉树：
满二叉树：都有左右儿子，高为h的树结点数是 2 ^h-1，父节点为i，左儿子为2i，右孩子为2i+1
完全二叉树：1到n个结点的排列和满二叉树一样，结点度为1时，只有左儿子，所以当n为奇数时，所有非叶子结点都有左右儿子结点，当n为偶数时，最大分支结点(n/2)只有左孩子，没有右孩子。i<=n/2时为分支结点，否则为叶结点。
二叉排序树：左子树任一结点一定小于右子树任一结点。
二叉平衡树：任一结点左右子树深度不超过1。
2.二叉树的链式和顺序存储
顺序存储：从上到下，从左到右，依次存入一维数组中，为了满足随机存取的特性，即使没有的空儿子，也只能添加空结点，比较浪费存储空间，比较适合满二叉树和完全二叉树。
链式存储：为了减少顺序存储带来的空间浪费
一个结点带有两个指针，其中n个结点的非空指针树=分支树=n-1,空指针树=n+1=2*结点数-分支数
题目：
1.n个结点二叉树采用链式存储：空指针数为n+1
2.顺序存储：空间点也得分配存储空间
3.完全二叉树求叶节点：分支结点=总结点数/2，然后向下取整；根据这个再可得叶节点数

3.二叉树的遍历和线索二叉树

1.二叉树的先序，中序，后序遍历由栈实现，层次遍历由队列实现

由遍历序列构造二叉树：必须有中序遍历
三种方式：先序中序 后序中序 层次中序，这三种可以确定一颗唯一的二叉树

2.线索二叉树
每一个结点除了第一个和最后一个，他们都有直接前驱和直接后继，规定若无左子数，Ichild作为线索指向前驱结点，若无右子树，rchild作为线索指向后继

二叉树的线索化：就是把二叉树链表的空指针指向前驱或后继，前驱和后继只有遍历才知道，实际上就是二叉树的一次遍历。
直接找到前驱或后继：在普通的二叉树中，要找到一个节点的前驱和后继节点，需要通过遍历整个二叉树来查找。而在线索二叉树中，通过添加线索，可以直接在常数时间内找到一个节点的前驱和后继节点，不需要从根节点遍历，当父节点为前驱或后继时，需要从根节点开始遍历，左右孩子做前驱后继不用从根节点遍历。
1.先序的前驱(有左右孩子，没有线索指针)为父节点，需要从根结点遍历。
2.后序的后驱(有左右孩子，没有办法通过线索指针快速找后继)为父节点,需要从根节点遍历。
3.以上两种情况采用三叉链表结构，分配一个指针指向父节点，那么也可以直接找到前驱或后继。

这里理解这个前驱和后继就要先学会构造相应的二叉树再具体分析。
中序线索二叉树：
中序序列：a+b*c-d-e/f

树中所有叶子结点的右链是线索，则右链直接指向了结点的后继；b结点的后继为 * 。
非叶子结点右链是指针，无法得到后继信息。
根据中序遍历的规律知：
结点的后继：若右标志为1，右链作为线索，否则，遍历其右子树时访问的第一个结点，即右子树中最左下的结点；
结点的前驱：若没有左孩子其左标志为 1 ，则左链为线索，指向其前驱 ；否则，遍历左子树时最后一个访问的结点（左子树中最右下的结点）位其前驱。
其实除了根节点外，左右孩子都在的情况，左右孩子分别为前驱和后继，但是为了统一点，就用上面两句话。

先序二叉线索树：

根据先序遍历的规律知：
结点的后继：若有左孩子，则左孩子就是其后继，若没有左孩子但有右孩子，则右孩子就是其后继，若是叶子结点右标志为1，则右链为线索，指向其后继；
结点的前驱：若没有左孩子其左标志为 1 ，则左链为线索，指向其前驱 ；否则，有左孩子(此时左孩子指向后继)，无法存储左链，不能直接找到其前驱结点。
在先序遍历中，某一个结点的左右子树只可能是它的后继，均不可能是它的前驱，所以，如果要求其前驱，有两种方法：
1 可以使用最原始的方式从根节点依次遍历，但是浪费时间，时间复杂度
2. 采取三叉链表的数据结构，分配一个指针，用于指向该结点的父结点。
后序线索二叉树：

根据后序遍历的规律知：
结点的前驱：
1.若没有左孩子其左标志为 1 ，则左链为线索，指向其前驱 ；
2.只有左孩子，左孩子为其前驱结点；
3.左右孩子都在右孩子为前驱。
结点的后继：
后序遍历中，某一个结点的左右子树只可能是它的前驱，均不可能是它的后继，所以，如果要求其后继，有两种方法：
1 使用最原始的方式从根节点依次遍历
3. 或者采取三叉链表的数据结构，分配一个指针，用于指向该结点的父结点。

3.三种遍历的动态演示
一般会考是否存在m到n的路径：只有后序可以找到路径，所谓找到路径，就是在辅助栈中找到m到n的路径

以上图为例：

1、先序：

进入m：
m入栈，m出栈并输出；
进入m的左子树a：
a入栈，a出栈并输出；
a为叶子节点，左右孩子均为空；
回退至m；
进入m的右子树b
 b入栈，b出栈并输出；
 进入b的左子树n：
 n入栈，n出栈并输出；
 n为叶子节点，左右孩子均为空；
 回退至
 进入b的右子树c：
 c入栈，c出栈并输出；
 c为叶子节点，左右孩子均为空；
  回退至b；
回退至m；
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

结论：栈内不存在路径，栈中一直只有一个元素

2.后序

进入m：
 m入栈（栈内情况：m）；  
 进入m的左子树a：   
 a入栈（栈内情况：ma）；   
 a为叶子节点，左右孩子均为空，a出栈并输出（栈内情况：m）；
 回退至m；   
 进入m的右子树b：  
 b入栈（栈内情况：mb）；   
 进入b的左子树n：   
 n入栈（栈内情况：mbn）；//栈内出现了从m到n的路径   
 n为叶子节点，左右孩子均为空，n出栈并输出（栈内情况：mb）；   
回退至b；   
 进入b的右子树c：   
 c入栈（栈内情况：mbc）；                       
 c为叶子节点，左右孩子均为空，c出栈并输出（栈内情况：mb）；   
 回退至b；   
 b的左右子树均遍历完毕，b出栈并输出（栈内情况：m）；
回退至m；

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

结论：辅助栈内存在路径：ma mbn mbc
题目：
1.先序序列a,b,c,d的不同二叉树的个数是多少：因为先序是用栈的，相当于知道进栈序列，求出栈序列的个数：C(2n,n)/n+1
2.已经知道先序和后序序列，求中序序列：利用位置相对不变的性质：NLR,LRN,
例子：二叉树前序序列和后序序列分别是1，2，3，4和4，3，2，1，则该二叉树的中序遍历序列：解析;刚刚好逆序，所以要么没有左子树，要么没有右子树，则1的孩子2要么在序首要么在序尾巴。
3前序和后序不能确定一个二叉树，但是可以确定祖先关系
例子2：前序序列：a,e,b,d,c 后序：b,c,d,e,a则根节点的孩子结点：e
解析：对于a来说，e作为根节点的话对于bcd位置不变还是序首或者序尾

4.树和森林

1.树的三种存储结构
1.双亲表示法：找父节点方便，找孩子不方便，一组连续的空间，分配一个指针指向父节点
2.孩子表示法：找孩子方便，找父节点不方便，每个结点的孩子用单链表串起来
3.孩子兄弟表示法：找孩子方便，找父节点不方便，二叉链表存储，两个指针，一个指向孩子，一个指向兄弟，这样转二叉树方便。
2.树，森林，二叉树的相互转化
1.树转化为二叉树(左孩子右兄弟)
只保留第一个孩子，孩子之间加直线，断开除第一个孩子的其他孩子的线
2.森林转化为二叉树(左孩子右兄弟，此时喊兄弟树)
森林中的每棵树转化为相应的二叉树，然后每棵树的根节点连线
3.二叉树转化为森林
左右子树非空情况，左子树看成一颗二叉树，右子树看作除左子树外的森林转化的二叉树

3.树和森林的遍历和二叉树遍历对应的关系

题目:
1.树对应二叉树中无右孩子的结点个数=分支结点数+1=树结点总数-叶节点数+1
2.森林F转换为对应的二叉树T，F中叶节点的个数等于=T中左孩子指针为空的结点个数
3.树的一个很重要的性质，即在n个结点的树中有n-1条边，对于每棵树，结点数比边数多1，若森林中的结点 树比边数多10，显然含有10棵树
4.如果给中序和先序序列，求森林对应有几棵二叉树构成，不能再用上面的方法，而是画出对应的森林的图，森林中每棵二叉树以右子树的方式相连，然后用此判断

5.树的应用

1.并查集
我们通常用树的双亲表示法，作为并查集的存储结构。
定义：
并查集是一种不相交集合的数据结构，用于处理不相交集合。
并查集顾名思义，合并两个集合简称“并”，找出包含给定元素的唯一集合简称“查”，并查集是表示一组不相交的集合的数据结构，简称“集”，表示对象是一组不相交的集合构成的一个集族，合起来就是“并查集”。
为了标识每个集合，从每个集合的所有元素中选出一个代表。每个集合有且仅有一个代表。类比每个小组有一个小组长。
操作
并查集主要有三种操作，即创建集合，合并集合，查找集合。

下面两个优化都可以有效减缓树高的增加，使得find的时间复杂度下降。
并的优化：小树合并到大树
查的优化：找到根结点，将查找路径的所有结点挂到根结点上，

例题：

2.并查集中，查的最坏情况就是O(n)，此时树的结点都只有一个孩子。

2.二叉排序树
特性：左子树的值<根节点<右子树
二叉排序树的查找：根据他的大小特性一排一排比较得来
二叉排序树的的插入：添加新的叶结点，要根据特性添加
二叉排序树的删除：三种情况
1.无子结点：直接删除
2.单子结点：子节点代替原结点
3.左右双结点：选择左子树最大的或者右子树最小的代替原结点

3.平衡二叉树
1.特性：在插入和删除结点时，保证左右子树的高度相差不超过一，这样的树称为平衡二叉树
2.平衡二叉树：插入后的平衡因子的绝对值小于1(四种情况)
1.LL：右单旋转
2.RR：左单旋转
3.LR：先左旋后右旋
4.RL：先右旋后左旋
(左旋右旋一一对应，像这种LR从后面®先对应)
LL：左孩子的左子树插入，单旋一次以孩子作为旋转点
LR：左孩子的右子树插入，左旋加右旋两次，以左孩子的右孩子，，就是孙子级别为旋转点

3.平衡二叉树的平均查找长度：Olog(n)

4.哈夫曼树和哈夫曼编码
1.定义：哈夫曼树：也称最优二叉树，n个带权叶结点的二叉树中带权路径(WPL)最小的二叉树
结点带权路径长度：根节点到该叶结点的路径长度和该点带权值的乘积
树的带权路径长度：所有结点带权路径长度之和
构造：每次合成后存在的结点中(此时合成后的点作为新的结点参加挑选)选择两个最小的进行构造二叉树
唯一性：构造的二叉树的可以不唯一，但是他们的WPL值是唯一确定的
2.哈夫曼编码：
对编码了解
定长编码：每一个字符的编码的定长的
不定长编码：对于常用的字符用短编码，对于不常用的用长编码，这样降低平均编码长度
哈夫曼编码：被广泛应用的数据压缩码，根据出现频率构造的不定长编码
以哈夫曼树为基础的编码规则
以每个字符出现的次数作为他的权值来构造一个哈夫曼树，左边分支为0，右边分支为1，从根节点到改叶结点的路径的编码为该字符的哈夫曼编码

哈夫曼编码：叶子结点数为n,非叶子结点数为n-1
题目：
1.哈夫曼树为带权路径长度最小的二叉树，不一定是完全二叉树
2.前缀编码：在一个字符集中，任何一个字符的编码都不是另一个字符编码的前缀
3.哈夫曼码是前缀编码
4.n个符号构成哈夫曼树，新建n-1个分支结点，因此哈夫曼树的结点总数为2n-1
5.哈夫曼编码：乘以的是经过的边数，而不是层数

五：图

1.图的基本概念

1.定义：边表E，顶点表V，记为G=(V,E)
线性表可以是空表，树可以是空树，图不可以是空图，边表可以为空，顶点表不能为空。
2.有向图，无向图，边是否有向
3.简单图：没有顶点到自身的边，，多重图：有自己到自己，一点到另一点不止一条边
4.完全图：也叫简单完全图
对于无向图：每个顶点之间都有边
对于有向图：每个顶点之间有存在相反方向的两条弧
连通图：无向图 强联通图：有向图 -----》带个强字有向
强连通分量：有向非强连通图的最大连通子图
连通分量：无向图的极大连通子图
生成子树：无向连通图的极小连通子图(包含全部顶点)，加一条边成为环，减少一条边不连通
强连通和连通不一样，强连通是有向图，连通是无向图
连通图边数最少：n-1 一颗树 强连通图边数最少：n 一个环
5.稀疏图和稠密图
E 题目：
1.无向连通图的顶点度之和为边数的两倍，所以所有顶点度之和为偶数
2.保证无向图在任何情况下都是连通的，即任意变动图的边，图始终保持连通，若有n个顶点，则需要将n-1个顶点构成完全连通子图C(n-1,2),再添加一条边将第n个结点和n-1个结点构成的完全连通子图连接起来
3.邻接矩阵为非对称矩阵，说明图是有向图，度为入度和出度之和，各顶点的度是矩阵中此结点对应的行和列的非零元素之和

2.图的存储和基本操作

有四种存储：领接表，邻接矩阵，十字链表，邻接多重链表
一：邻接矩阵
就是矩阵的形式存储，有边就是1，，无边为0，适合稠密图的存储
二：邻接表(顶点表和边表)
邻接表法：
无向图：相关联的边都是
有向图：出度，仅仅是做弧尾的时候，
逆邻接表(有向图)：入度：顶点作为弧头

三十字链表法
主要知道弧结点和顶点结点，每个弧对应着一个弧结点，每个顶点对应一个顶点结点
顶点结点：

弧结点：

举个例子：

总结：其实和邻接表法差不多，只不过邻接表的顶点结点指向顶点结点，这里是指向弧结点，然后对相应的指针域连线就行

四：多重邻接表法

总结：邻接矩阵，邻接表 有向图，无向图都可以
十字链表有向图 邻接多重表 无向图

3.图的遍历

一：广度优先搜索(BFS)
类似二叉树的层次遍历，利用队列实现搜索，依次访问邻接的所有结点，然后再访问这一层邻接的下一层结点
二：深度优先搜索(DFS)
类似于二叉树的先序搜索,利用栈实现；访问邻接且未被访问的任一顶点
总结：广度优先搜索后会生成广度优先树，深度优先搜索后会形成树(连通图)或者森林(非连通图)，，，因为邻接矩阵表示树具有唯一性，所以基于邻接矩阵遍历得到的DFS序列和BFS序列具有唯一性，基于邻接表遍历得到的BFS序列和DFS序列不是唯一的
题目：
1.

4.图的应用

最小生成树，最短路径，拓扑排序，逆拓扑排序
一：最小生成树
1.prim算法：
从一个点开始，每次找该点集合里面所有相连的边中最短的边，加入边集合，直到所有的点连通，构成最小生成树
2.kruskal算法：
1.将图中所有边对象(边长、两端点)依次加入集合(优先队列)q1中。初始所有点相互独立。
2.取出集合(优先队列)q1最小边，判断边的两点是否联通(分为直接和间接)。
3.如果联通说明两个点已经有其它边将两点联通了，跳过，如果不连通，则使用union（并查集合并）将两个顶点合并，这条边被使用(可以储存或者计算数值)。
4.重复2，3操作直到集合（优先队列）q1为空。此时被选择的边构成最小生成树。

总结：prim和kruskal都是贪心算法(贪心算法，又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，算法得到的是在某种意义上的局部最优解 。贪心算法不是对所有问题都能得到整体最优解，关键是贪心策略的选择 。prim和kruskal的贪心策略不同。
prim适合稠密图，kruskal适合稀疏图。Prim算法适合边稠密图，时间复杂度O(n²)，Kruskal算法与边有关，适合于稀疏图O(eloge)，kruskal是先把边的权值排序一次再进行选择。

二：最短路径
Dijksra,Floyd
Dijkstra算法：
从dis数组(原点到其他各个顶点当前的最短路径)选择最小值，则该值就是原点s到该值对应的顶点的最短路径，并且把该点加入到T中，此时完成一个顶点。
然后，我们需要看看新加入的顶点是否可以到达其他顶点并且看看通过该顶点到达其他点的路径长度是否比源点直接到达短，如果是，那么就替换这些顶点在dis中的值。
然后，又从dis中找出最小值，重复上述动作，直到T中包含了图的所有顶点。

Floyd算法：
各个顶点之间的最短距离，暴力破解法，通过循环的方式，时间复杂度比较高，对于稀疏图将会生成稀疏矩阵，极大浪费了储存空间。
初始化矩阵，将所有相邻的节点对应的权值写入矩阵，不相邻的节点对应的权值初始化为inf，如下面的例子所示：
初始化结束后，开始循环，每层循环从第一个节点开始遍历，直至遍历到第n个节点，则以节点i为中介点，以节点j为起点，节点k为目标点，判断由起点j经由中介点i到达目标点k的代价值是否小于由起点j直接到目标点k的代价值，若小于，则将从起点j到目标点k的代价值d[j][k]更新为d[j][i]+d[i][k]。循环结束后，路径规划结束。每个顶点都做一次中间点，当所有结点循环完以后，算法结束。
① 以A为中介点，分别更新B/C/D/E/F/G经中介点A到其他节点的累积权值

三：拓扑排序
1.有向无环图：DAG图
2.AOV网，若DAG图表示一个工程，有向边，表示活动V1必须优于活动V2，这样一种关系，这样的有向图称为AOV图，自己不能作为自己的前驱或者后继
3.拓扑排序的定义：
每个顶点只出现一次，若顶点A在顶点B前面，则不存在顶点B到A的路径
4.拓扑排序的实现方法：
从AOV网删除一个没有前驱的顶点和以它为起点的有向边
因为后继不一定唯一，环不存在拓扑结构：因为拓扑排序的定义就是从AOV网选择一个没有前驱的顶点输出
四：逆拓扑排序
1.选择一个没有后继的结点输出，并且删除以它为终点的有向边
五：关键路径
核心思路：从汇点按照逆拓扑排序求其余顶点最迟发生时间
1.汇点与源点：汇点就是终止点
2.过程
从最末端的活动开始：
step1：将最末端的活动时间标记为0（这里选汇点，将汇点当做一个虚活动），活动a10与0(我们记汇点的活动时间为0)相加，标注在它的前置活动a7上方，同理，活动a11与0相加，标注在它的前置活动上方（这里a11有两个前置活动，都要标注）：
依次选最大往前加，标注在前一个活动上方(核心):


只有关键路径的时间减少，工期才减少，当关键路径减少到一定程度的时候，可能变成非关键路径。
判断一个有向图是否有回路：
(1)深度优先 （2）拓扑排序 (3)关键路径
题目：
1.最小生成树的树形可能不唯一，因为可能存在权值相同的边，但代价一定是唯一的
2.有多条关键路径，找可以缩短工期的点，需要找到这些关键路径的共同结点，只有 它们同时减少时，才能缩短工期
3.对于无环有向图，一定存在拓扑序列，但是不一定是唯一的
4.活动的最早开始时间和最晚开始时间：
最早开始时间：活动头最早开始时间：起点到活动头最长的时间
最晚开始时间：关键路径长度-活动为到终点的时间-该活动需要耗费的时间
5.有向无环图描述表达式，需要的顶点个数至少是：将表达式转化为有向二叉树，节省存储空间，去除重复的点，将有向二叉树去重转换成有向无环图
6.

六：查找

1.查找的基本概念

查找的概念：在数据集合中寻找满足某种条件的数据元素的过程为查找
查找表：查找表是一种存储结构，专门用来存储无逻辑关系的数据。也可以这样理解，查找表就是一个包含众多元素的集合，表中的各个元素独立存在，之间没有任何关系。
对于无逻辑关系的数据，做的最多的操作就是从中查找某个特定的元素。和有逻辑关系的数据相比，在无逻辑关系的数据中查找特定元素的难度更大。例如，同样是查找一个电话号，在杂乱无章的电话簿中查找既费时又费力，在有序的电话簿中很快就能找到。
原本没有逻辑关系的数据，为了提高查找效率，会人为地给数据赋予一种逻辑关系，继而选用线性表、树或者图结构来存储数据。比如说，为电话簿中的电话号赋予“一对一”的关系，就可以用线性表（顺序表或者单链表）存储电话号。
从名称上看，查找表是一种新的存储结构，但实际上它指的就是用线性表、树或者图结构来存储数据，只不过数据间的逻辑关系是人为赋予的。
数据结构中，将存储无逻辑关系数据的线性表、树或者图结构统称为查找表。

查找表操作：查询某个特定元素是否在查询表中，查询成功插入，查询失败时删除
静态查找表：查找完不会对表进行操作，
动态查找表：查找完对表进行操作
平均查找长度：所有查找次数中关键字比较次数 的平均值
数学表达式：ASL=

平均查找长度是算法效率的最主要指标

2.顺序查找和折半查找和分块查找

1.顺序查找
分为无序的顺序查找和有序表的按位的有序的顺序查找
一：一般线性表的顺序查找
成功的平均查找长度：(n+1)/2
失败的平均查找长度：N+1
二：有序表的顺序查找
基本思想：当查找的元素在第i个位置是小于它的，但是第i+1个位置是大于它的，则返回查找失败。
成功的平均查找长度：(n+1)/2
失败的平均查找长度：n/2+n/n+1
2.折半查找
折半查找也可以叫做二分查找，只用于有序的顺序表查找，只适用于顺序存储结构不能是链式
基本思想：将查找元素和表中间位置的元素对比，若相等，返回查找成功，失败则只能在前半部分或者后半部分，根据这个思想一直缩小范围，直到找到或者失败。
有些时候是圆形结点表示查找成功结点，方块的叶子结点才是查找失败的情况
3.分块查找
又成为索引顺序查找；吸收了顺序查找和折半查找的有点，既有动态结，又可以按顺序快速查找
基本思想：
将查找表分为若干子块，块内元素无序，块之间有序，第一个块的最大关键字小于第二个块的所有关键字，在建立一个索引表，索引表中每个元素含有该块的最大元素和该块第一个元素的地址，索引表按关键字有序排列。
查找长度：
将长度为n的查找表分为b块，每块有s个记录，b=n/s 在等概率的情况下
在块内和索引表都使用顺序查找，则平均查找长度:(b+1)/2+(s+1)/2
在索引表使用折半查找：log2(b+1)+(s+1)/2

总结：查找判定树(顺序和折半)：查找成功的比较次数等于它自身所在是层数，查找失败的比较次数等于它父节点所在的层数

3.B树和B+树

一：B树及其基本操作
定义：
1.每个结点最多有m-1个关键字。
2.根结点最少可以只有1个关键字。
3.非根结点至少有Math.ceil(m/2)-1个关键字。(Math.ceil就是向上取整)
4.每个结点中的关键字都按照从小到大的顺序排列，每个关键字的左子树中的所有关键字都小于它，而右子树中的所有关键字都大于它。
5.所有叶子结点都位于同一层，或者说根结点到每个叶子结点的长度都相同。

上图是一颗阶数为4的B树。在实际应用中的B树的阶数m都非常大（通常大于100），所以即使存储大量的数据，B树的高度仍然比较小。每个结点中存储了关键字（key）和关键字对应的数据（data），以及孩子结点的指针。我们将一个key和其对应的data称为一个记录。但为了方便描述，除非特别说明，后续文中就用key来代替（key, value）键值对这个整体。在数据库中我们将B树（和B+树）作为索引结构，可以加快查询速速，此时B树中的key就表示键，而data表示了这个键对应的条目在硬盘上的逻辑地址。
B树的插入操作：
插入操作是指插入一条记录，即（key, value）的键值对。如果B树中已存在需要插入的键值对，则用需要插入的value替换旧的value。若B树不存在这个key,则一定是在叶子结点中进行插入操作。

1.根据要插入的key的值，找到叶子结点并插入。
2.判断当前结点key的个数是否小于等于m-1，若满足则结束，否则进行第3步。
2.以结点中间的key为中心分裂成左右两部分，然后将这个中间的key插入到父结点中，这个key的左子树指向分裂后的左半部分，这个key的右子树指向分裂后的右半部分，然后将当前结点指向父结点，继续进行第3步。
下面以5阶B树为例，介绍B树的插入操作，在5阶B树中，结点最多有4个key，最少有2个key：

B树的删除操作：
删除操作是指，根据key删除记录，如果B树中的记录中不存对应key的记录，则删除失败。
删除非叶子结点：
1.如果当前需要删除的key位于非叶子结点上，则用后继key（这里的后继key均指后继记录的意思）覆盖要删除的key，然后在后继key所在的子支中删除该后继key。此时后继key一定位于叶子结点上，这个过程和二叉搜索树删除结点的方式类似。删除这个记录后执行第2步
2.该后继所在叶结点key个数大于等于Math.ceil(m/2)-1，结束删除操作，否则执行第3步。
3.兄弟够借：如果兄弟结点key个数大于Math.ceil(m/2)-1，则父结点中的key下移到该结点，兄弟结点中的一个key上移，删除操作结束。
4.兄弟不够借：否则，将父结点中的key下移与当前结点及它的兄弟结点中的key合并，形成一个新的结点。原父结点中的key的两个孩子指针就变成了一个孩子指针，指向这个新结点。然后当前结点的指针指向父结点，重复上第2步。
有些结点它可能即有左兄弟，又有右兄弟，那么我们任意选择一个兄弟结点进行操作即可。
下面以5阶B树为例，介绍B树的删除操作，5阶B树中，结点最多有4个key，最少有两个key
**删除叶子结点：**删除后大于Math.ceil(m/2)-1，则删除结束，否则就和上面一样
情况一：兄弟够借

删除27。从上图可以得知27位于非叶子结点种，所以用27的后继替换它。从图中可以看出，27的后继为28，我们用28替换27，然后在28（原27）的右孩子结点中删除28。删除后的结果如下所示：

删除后发现，当前叶子结点的记录的个数小于2，而它的兄弟结点中有3个记录（当前结点还有一个右兄弟，选择右兄弟就会出现合并结点的情况，无论选哪一个都行，只是最后B树的形态不一样而已），我们可以从兄弟结点中接取一个key。所以父结点中的28下移，兄弟结点中的26上移，删除结束。结果如下所示：

情况二：兄弟不够借

上述情况下，我们继续删除key为40的记录，删除后结果如下图所示：

同理，当前结点的记录数小于2，兄弟结点中没有多余key，所以父结点中的key下移，和兄弟（这里我们选择左兄弟，选择右兄弟也可以）结点合并，合并后的指向当前结点的指针就指向了父结点。

同理，对于当前结点而言只能继续合并了，最后结果如下所示。

二：B+树的基本概念
一颗m阶的B+树满足如下条件：
1.每个节点最多只有m个子节点。
2.除根节点外，每个非叶子节点具有至少有 m/2（向下取整）个子节点。
3.非叶子节点的根节点至少有两个子节点。
4.有k颗子树的非叶节点有k个键，键按照递增顺序排列。
5.叶节点都在同一层中。
6.叶结点：从小到大顺序链式连接，可以支持顺序查找

总结：B树，B+树都支持随机查找

4.散列表

1.散列表的基本概念
1.散列函数定义：一个把查找表中关键字映射为该关键字对应的地址的函数
hash(key)=addr
2.冲突：散列函数可能会把两个及以上的关键字映射到同一个地址，同义词越少，冲突越少，效率越高
3.散列表：根据关键字而进行直接访问的数据结构
4.理想状态的时间复杂度：O(1)

2.散列表的构造：
注意点：
1.散列表的定义域需要包含所有涉及到的关键字，散列表的值域需要依赖于散列表的；地址范围
2.散列表计算出来的地址应该等概率均匀分布在地址空间中，减少冲突的发生
3.散列函数应该简单，可以在短时间内计算出关键字对应的地址
散列函数的构造方法：
一：直接定址法(简单，且不会起冲突)
1.直接取用关键字的线性函数数值作为对应的散列表的地址
Hash(key)=a*key+b
常用情况：关键字连续的情况，如果不连续会导致空间的浪费
2.除留余数法（简单常用，但是要选好P，减少冲突）
方法：假设散列表长度为M，取一个质数P，接近且小于M的质数，对关键字取余，将关键字转化为散列表对应的地址
hash(key)=key%p
3.数字分析法(适合已知关键字的集合，若更换关键字，则需要重新构造新的哈希函数)
方法：利用进制数，比如这些关键字集合在二进制中他们转化的二进制数的某几位分布比较均匀，则选择这几位作为散列地址
4.平方取中法(散列地址分布比较均匀，适用于关键字每位取值不够均匀或均小于散列地址所需的位数)
方法：取关键字平方的中间几位作为散列地址

总结：散列表是典型的空间换时间的算法，散列表越长，越不可能起冲突

处理冲突的方法：
1.开放地址法
开放地址法的基本思想时：将记录都存储在散列表数组中，当某一记录关键字经过散列函数的计算所得到的初始地址H0此时已有其他关键字占据（即发生冲突）,采取合适的方法计算得到另一个地址，如果仍然发生冲突，就以相同的计算方法di=d[i+1]，代入增量序列数组中的下一位，直到所得到的地址不再发生冲突。
这种方法在寻找下一个地址时，原来的数组空间对于所有的元素都是开放的，不管关键字key经过哈希函数计算所得到的初始地址是否与之相同，也没有其他的要求任何的元素中可以存储，所以称作开放地址法。
开放地址法是线性存储空间上的解决方案，也被称为闭散列。
当发生冲突时，采用冲突处理方法在线性存储空间上探测其他位置。hash′(key)=(hash(key)+di )%m ，其中，hash(key)为原散列函数，hash′(key)为探测函数，di 为增量序列，m 为表长。
根据增量序列的不同，开放地址法又分为线性探测法、二次探测法、随机探测法、再散列法。
例子一：线性探测法：
线性探测法是最简单的开放地址法，线性探测的增量序列为di =1,…,m -1。
例如，有一组关键字(14,36,42,38,40,15,19,12,51,65,34,25)，若表长为15，散列函数为hash(key)=key%13，则可采用线性探测法处理冲突，构造该散列表。

按照关键字顺序，根据散列函数计算散列地址，如果该地址空间为空，则直接放入；如果该地址空间已存储数据，则采用线性探测法处理冲突。

[1] hash(14)=14%13=1，将14放入1号空间（下标为1）；hash(36)=36%13=10，将36放入10号空间；hash(42)=42%13=3，将42放入3号空间；hash(38)=38%13=12，将38放入12号空间。

[2] hash(40)=40%13=1，1号空间已存储数据，采用线性探测法处理冲突。

hash′(40)=(hash(40)+di )%m ，di =1,…,m -1

d1 =1：hash′(40)=(1+1)%15=2，2号空间为空，将40放入2号空间，即hash(40)=40%13=1→2。

[3] hash(15)=15%13=2，2号空间已存储数据，发生冲突，采用线性探测法处理冲突。

hash′(15)=(hash(15)+di )%m ，di =1,…,m -1

d1 =1：hash′(15)=(2+1)%15=3，3号空间已存储数据，继续进行线性探测。
d2 =2：hash′(15)=(2+2)%15=4，4号空间为空，将15放入4号空间。
即hash(15)=15%13=2→3→4。

例子二：平方探测法
di=1^{2},-1{2},2^{2},-2{2},…+k^{2},-k{2}
平方探测再散列是加1的平方；减1的平方，加2的平方，减2的平方，加3的平方，减3的平方。。。加k的平方，减k的平方。来回探测

2.拉链法
链地址法的基本思想是：将具有相同散列地址的记录放在同一个单链表中，称为同义词链表，不需要处理冲突。

以前面相同的题为例，采用尾插法，下面是示意图

总结：开放地址法不能随意删除表中已经有的元素，若删除元素，会截断其他具有相同散列地址的元素的查找地址。

5.红黑树

它在效率上对AVL又做了进一步的优化，因为AVL(平衡二叉树)结构在插入，或删除时，无法避免大量的旋转操作，导致效率有所损耗，但是红黑树，就在这一点有了更好的优化，但是牺牲了平衡性，所以是不是一个完全平衡的二叉搜索树。
概念：
红黑树，是一种二叉搜索树，但在每个结点上增加一个存储位表示结点的颜色，可以是Red或Black。 通过对任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路径会比其他路径长出俩倍，因而是接近平衡的。
性质：
1、叶结点，根节点是黑色的
2、每个节点不是红色的就是黑色的
3、红色节点的子节点一定是黑色的
4、红色节点不能相连
5、从任意节点出发，不包括本身，它每一条路径上的黑色节点数目是相同的
6.有平衡二叉树的性质

七：排序

1.排序的定义

排序：重新排列表中的元素，使得表中元素满足按照关键字有序的过程
算法的稳定性：若表中元素a和b的关键字相同，在原表中a在b前面，排序后a还在b的前面，则算法具有稳定性
分类：
1.根据数据是否在内存中：
内部排序：排序过程中，元素全部存放在内存中
外部排序：排序期间元素无法全部存放在内存中，必须在排序过程中不断在内外存之间移动的排序
基本类型：
插入排序，交换排序，选择排序，归并排序，基数排序

2.插入排序

基本思想：每次将一个待排记录按照其关键字大小插入到前面已经排好的子序列中，直到全部记录插入完成
三种：直接插入算法，折半插入排序，希尔排序
一：直接插入排序
1.方法：将整个序列分为两个部分：有序部分和无序部分，每次从无序中取一个数，在有序中遍历，插入这个数，插入完后，自新插入的位置后的有序列向后移动一个位置
2.性能分析：
最好的情况：表已经有序，只需要比较元素不需要移动元素，时间复杂度O(n)
最坏的情况：表中排序恰好和排序结果刚刚好相反(逆序)，时间复杂度O(n^2)
3.算法稳定，适合顺序存储和链式存储
二：折半插入排序
1.方法：确定折半插入排序的范围，进行类似于二分法定界缩小范围，最后移动数据，插入
2.性能分析：O(nlogn)，比较次数之和表中元素有关
3.适合顺序存储，算法稳定
三：希尔排序
1.方法：可以认为是插入排序的优化。因为插入排序在序列已经大部分有序的情况下表现还是较为良好。所以希尔排序主要目标是先让序列整体大部分有序，然后最后再插入排序，从而实现优化。
算法过程：设定一个gap值，然后元素下标差值为gap的被认为是同一组，每一组完成插入排序。gap每次/2直到gap为0就停止。所以在最后一次排序gap为1时候，实际上也是插入排序，能够保证这个序列已经大部分有序。
一般来说gap初始设定为排序长度/2.

2.时间复杂度：O(n^2)
3.算法不稳定，适合顺序存储

3.交换排序

思想：根据序列中两个关键字的 比较结果交换两个记录在序列中的位置
考试范围：冒泡排序和快速排序
一：冒泡排序
思想：比较相邻的元素。如果第一个比第二个大，就交换他们两个。
对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
针对所有的元素重复以上的步骤，除了最后一个。
持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较
时间复杂度：
最好的情况：正序：O(n),只需要比较，不需要移动
最坏的情况：逆序：O(n^2)
稳定性：冒泡排序是一种稳定的算法
二：快速排序
快速排序采用的是分治思想，即在一个无序的序列中选取一个任意的基准元素pivot，利用pivot将待排序的序列分成两部分，前面部分元素均小于或等于基准元素，后面部分均大于或等于基准元素，然后采用递归的方法分别对前后两部分重复上述操作，直到将无序序列排列成有序序列。
（1）设置两个变量i、j，排序开始的时候：i=0，j=N-1；
（2）以第一个数组元素作为关键数据，赋值给key，即key=A[0]；
（3）从j开始向前搜索，即由后开始向前搜索(j–)，找到第一个小于key的值A[j]，将A[j]和A[i]的值交换；
（4）从i开始向后搜索，即由前开始向后搜索(i++)，找到第一个大于key的A[i]，将A[i]和A[j]的值交换；
（5）重复第3、4步，直到i等于j,(3,4步中，没找到符合条件的值，即3中A[j]不小于key,4中A[i]不大于key的时候改变j、i的值，使得j=j-1，i=i+1，直至找到为止。找到符合条件的值，进行交换的时候i， j指针位置不变。另外，i==j这一过程一定正好是i+或j-完成的时候，此时令循环结束）。
总结：找小的由后到前，找大的从前到后面
例子：
假设一开始序列{xi}是：5，3，7，6，4，1，0，2，9，10，8。
此时，ref=5，i=1，j=11，从后往前找，第一个比5小的数是x8=2，因此序列为：2，3，7，6，4，1，0，5，9，10，8。
此时i=1，j=8，从前往后找，第一个比5大的数是x3=7，因此序列为：2，3，5，6，4，1，0，7，9，10，8。
此时，i=3，j=8，从第8位往前找，第一个比5小的数是x7=0，因此：2，3，0，6，4，1，5，7，9，10，8。
此时，i=3，j=7，从第3位往后找，第一个比5大的数是x4=6，因此：2，3，0，5，4，1，6，7，9，10，8。
此时，i=4，j=7，从第7位往前找，第一个比5小的数是x6=1，因此：2，3，0，1，4，5，6，7，9，10，8。
此时，i=4，j=6，从第4位往后找，直到第6位才有比5大的数，这时，i=j=6，ref成为一条分界线，它之前的数都比它小，之后的数都比它大，对于前后两部分数，可以采用同样的方法来排序。 [3]
稳定性：是一种不稳定 的算法
最好的时间复杂度：O(n^2)
最坏的时间复杂度：O(nlogn)

4.选择排序

基本思想：每次在待排序列中选取最大/最小元素，排列到前面已排好子列中
一：简单选择排序
基本思想：每次在待排序列中利用依次对比方法选取最大/最小元素，排列到有序子列中，n个元素的简单选择排序序列需进行n-1趟处理。
时间复杂度：O(n^{2}) 无论是有序乱序还是逆序，都需要进行n-1趟处理
稳定性：不稳定
适用性：顺序表，链表
二：堆排序
堆分为大根堆和小根堆，大根堆是指根元素大于全部元素，小根堆是指根元素小于全部元素（这里的根不仅指根节点，也包括子树上面的根）。
堆排序是一个可以高效实现排序的算法，复杂度是O(nlogn)和之前的快速排序与归并排序的复杂度相同，而它高效的排序依赖于它的结构特点
1.堆是一个完全二叉树
2.堆中每一个节点的值都必须大于等于(或者小于等于)其子树中每个结点的值

堆的建立：自底向上
注意：在调整时可能上一层根节点的调整会引起下层的调整，所以不是所有节点都绝对只调整一次。

堆的插入：自底向上

堆的删除：自上向下

总结：不管插入，还是删除，或者建立，一定要满足堆的特性：1.完全二叉树 2.堆的结点对于其子树也要满足堆的特性
时间复杂度：O(nlogn)
稳定性：不稳定
适合结构：顺序表和链表

五：归并排序和基数排序

一：归并排序
基本思路：通过从小到大依次将各个子表进行有序合并生成有序子表，不断归并达到整体有序

注意：当两个待合并子表长度不一样，其中一个表元素已全部合并时，直接将另一子表元素全部加到已合并表后。

二：基数排序：
思想：基数排序不是关键字之间的对比，而是关键字之间各个位之间的对比
例子：

空间复杂度：（r个辅助队列）O®
时间复杂度：分配O(n) + 收集O® = O(n+r),有几位就回收几趟
稳定性：稳定

六：内部排序算法比较

插入排序的基本思想在于每次将一个待排序的记录按其关键字的大小插入到前面已经排好的序列中
交换排序的基本思想是根据序列中两个关键字的比较结果来交换着两个记录的位置。
选择排序的基本思想是每一次（假设第i次）都从带排序表中选出关键字最小的元素作为带排序表的第i个元素。直到第n-1趟结束。实现算法主要有简单选择排序和堆排序。
归并排序算法是将两个或者两个以上的有序表组合成一个新的有序表。而基数排序算法是基于多关键字排序思想，借助分配和采集两种操作对单逻辑关键字进行排序。
七：外部排序
概念：外部排序的提出主要是因为内存空间有限，因此对于较大篇幅的序列进行排序时需借助外存实现，即将待排序的记录存储在外存上，排序时再将数据一部分一部分地调入内存，排序过程中会涉及到多次内外存的交互，因此叫做外部排序。
方法： 通常使用归并算法：①根据内存缓冲区大小将外存上文件划分为多个子文件，依次读入内存并利用内部排序的方法对其进行排序，并将得到的有序序列写回外存，这些归并的子文件被成为归并段或顺串；②对这些归并段进行逐趟归并，使归并段有小到大，直到整个文件有序。
总结：以块为单位读入内存进行排序，排好之后再按块写回外存，实际排序还是在内存进行。

注意：对m路平衡归并排序时，若实现输入/内部归并/输出的并行处理，需设置2m个输入缓冲区和2和输出缓冲区；若实现串行处理，则仅需m个输入缓冲区和1个输出缓冲区。
例子：












后面再进行两轮归并即可。