当前位置：首页 > news >正文

网站标题的作用如何推广普通话的建议6条

news 2025/8/10 5:21:32

网站标题的作用,如何推广普通话的建议6条,深圳企业网站建设制作网络公司,海珠区建网站公司数据结构考题1.4 更新了时间复杂度理论和计算方法（简单快速） 1.基本概念范围：数据项(最小单位)<数据元素(基本单位)<数据对象(性质相同的数据元素集合) 举例：数据对象：学生群体；数据元素&#xf…

数据结构考题1.4

更新了时间复杂度理论和计算方法（简单快速）

1.基本概念

范围：数据项(最小单位)<数据元素(基本单位)<数据对象(性质相同的数据元素集合)
举例：数据对象：学生群体；数据元素：某个学生；数据项：这个学生的姓名、年龄、年级等
数据结构：存在“关系”的数据元素集合，包括物理结构与逻辑结构
逻辑结构与数据存储无关，独立于计算机。有四个：“集合、线性、树、图”结构，分为线性结构和非线性
线性：线性表、队列和栈、字符串、数组和广义表
非线性：数和二叉树、有向图和无向图
存储结构要存储数据和逻辑关系，分为顺序存储结构和链式存储结构
顺序存储结构：存储地址相连接的整块存储，存储密度高，但插入删除运算效率低
链式存储结构：地址不一定连续，但是需要存储指针指向与之相关的结点，存储密度<顺序存储=100%，插入删除效率高
抽象数据类型：用户定义的、表示应用问题的数学模型，以及定义在这个模型上的一组操作的总成。包括：数据对象、数据对象的关系、对数据对象的操作
算法五大特性：有穷性、可行性、确定性、输入、输出
算法评价四个标准：：正确性、可读性、健壮性、高效性(低时间空间复杂度)
算法设计五大要求：正确性、可读性、健壮性、零个以上的输入、一个以上的输出
算法分析的目的：分析算法的效率以求改进

Extra-时间复杂度计算方法：
引入时间复杂度主定律：
设T[n]为问题规模，f(n)为n的函数
T[n] = a*T[n/b] + f(n)（不可直接求出T(n)与f(n)的关系）
令k = logb(a)（b为底，a为真数）

f(n) < O(n^k): T(n) = O(n^k)
f(n) = O(n^k): T(n) = O(n^k * logn)
f(n) > O(n^k): T(n) = O(f(n))

（这里的>,<,=是指n的幂，即f(n)中幂最大的n和O(n^k)的比较）
若不是a*T(n/b)的形式，为T(n-1)型
可求出T(n)与f(n)关系式
用高中学的等比数列求递推式的方式

例题：

hanio问题：T(n) = 2T(n-1) + 1其中T(1) = 1
类型2
2T(n-1) = 2²T(n-2) + 2¹
2²T(n-2) = 2³T(n-3) + 2²
…
2^n-1T(2) = 2ⁿT(1) + 2^n-1
求和得：
T(n) = 2ⁿ + 2ⁿ - 1
O(n) = 2ⁿ
T(n) = 2*T(n/2) + n/2
类型2
k = log2(2) = 1
f(n) = O(n^k): T(n) = O(nlogn)

2. 线性表

简述线性表：元素间的关系是一对一，特点是：存在唯一的“第一个”和“最后一个”元素，除第一个的元素都有唯一前驱，除最后一个的元素都有唯一后继

2.1. 顺序线性表

用一组连续的地址存储线性表的数据元素，特点是逻辑上连续的元素在物理结构也相邻

// 循序表
typedef struct 
{DataType *sqlist;int length;
}SqList;

查找第i个元素对比i次，查表ASL=(1+n)/2
插入到第i个元素前移动n-i+1次，插入ASL=n/2
删除第i个元素移动n-i次，ASL=(n-1)/2

2.2. 链表

单链表
用一组任意的存储单元存储，为了表示元素与前驱后继的关系，用指针域表示其地址

// 单链表
typedef struct Node
{DataType data;struct Node *next;
}Node *LinkedList;
// 一般建立单链表，都会设立一个头结点

查找

p=L->next; 
while(p)
{// 遍历链表结点，用p表示p=p->next;
}

插入

// 头插法把s插入p结点后
Node *s = (*Node)malloc(sizeof(Node))
s->next = p->next;
p->next = s;

删除

// 删除p的后继（单链表中只能删后继，所以记得保存一个前驱结点pre）
s = p->next;
p->next = s->next;
free(s);

建立

void createList(LinkedList &L, DataType array[], int length)
// 头插法
p=L
for (i=0; i<length; ++i)
{Node* s = (*Node)malloc(sizeof(Node))s->data=array[i];s->next = p->next;p->next = s;
}
// 尾插法
r=L;
for (i=0; i<length; ++i)
{Node* s = (*Node)malloc(sizeof(Node))s->data=array[i];s->next = NULL;r->next = s;r=s;
}

循环链表
与单链表的区别是最后一个元素的next指向L(头结点)
判空区别，单链表：L->next == NULL;
循环链表：L->next == L;
应用：两个设立尾结点的循环的合并：
A、B为两个循环链表的尾结点。

p=B->next->next;
B->next=A->next;
A->next=p;

双向链表
在循环链表的基础上每个结点增加前驱指针
（考的很少）

2.3. 应用

有序链表的合并

void combine(List &a, List &b, List &c) // a和b合并到c链表，且不占用新内存空间
{p1=a->next, p2=b->next;c=a;  // 让c用a的头结点pc=c;while (p1 && p2){// 选择a和b的结点中小的一个，插入c表后面if (p1->data < p2->data) {pc->next=p1;pc=p1;p1=p1->next;}else{pc->next=p2;pc=p2;p2=p2->next;}}if (!p1) pc->next=p2;if (!p2) pc->next=p1;free(b);
}

链表原地反向

void reverse_list(List &L)
{  // 同时记录三个指针：pre, p, pNext；每次先保存pNext，把p指向prep=L->next; pre=L;while (p){pNext=p->next;p->next=pre;pre=p;p=pNext;}
}

（持续更新）

3. 栈和队列

栈和队列都是操作受限的线性表，只能在表的两端进行操作（栈只能在一端操作）受容量限制，虽可以重新分配空间但工作量较大

3.1. 顺序栈

用顺序表实现栈，有两个指针base和top，base指向栈底元素，top指向栈顶的下一个

typedef struct
{SDataType *base;  // 栈底指针，若==NULL，则栈不存在SDataType *top;  // 栈顶指针，初始时top=base，top==base: 栈空int stack_size;
}SqStack// 创建顺序栈
bool create_stack(SqStack &s)
{s.base = (SDataType*)malloc(MAX_SIZE * sizeof(SDataType));if (!s.base) return false;s.top=s.base;s.stack_size = MAX_SIZE;return true;
}

入栈

bool push(SqStack &s, SDataType e)
{if (s.top-s.base==s.stack_size) return false; // 满栈*s.top++ = e;return true;
}

出栈

bool pop(SqStack &s, SDataType &x)
{if (s.top==s.base) return false; // 栈空x = *--s.top;return true;
}

取顶

bool top(SqStack s, SDataType &x)
{if (s.top==s.base) return false; // 栈空x = *(s.top-1);return true;
}

3.2. 链栈

用链表形式实现栈

typedef StackNode
{DataType data;struct StackNode *next;
}StackNode, *LinkStack;void initStack(LinkStack &s)  // 初始化，置空指针
{s=NULL;
}

入栈

bool push(LinkStack &s, DataType e)  // 插入后部并栈顶指针后移
{StackNode *p = (*StackNode)malloc(sizeof(StackNode));if (!p) return false;  // 分配空间失败p->data=e;p->next=ss=p;return true;
}

出栈

bool pop(LinkStack &s, DataType &x)
{if (s==NULL) return false;StackNode* q=s;	x=q->data;s=s->next;free(q);return true;
}

3.3. 栈的应用

n个元素的出栈顺序有几种？
我们设F函数为解，则当n=0,1,2,3时，F(0)=F(1)=1, F(2)=2, F(3)=5
F(n)=C(2n, n) / (n + 1) = C(2n, n) - C(2n, n-1) [n个结点的二叉树有几种]
数值转换

// 十进制转八进制
void conversion()
{initStack(s);scanf("%d", &n);while(n){push(s, n%8);  // 可转为任意(10以下)进制n/=8;}while (!empty(s)){pop(s, e);printf("%d", e);}
}

括号检测

bool valid(char str[], int length)
{bool flag=true;for (i=0; i<length; ++i){char c=str[i];switch(c){case '['||'(': push(s, c); break;case ')': top(s, e); if (!empty(s) && e=='(') pop(s, e);else flag=false; break;case ']': top(s, e); if (!empty(s) && e=='[') pop(s, e);else flag=false; break;}if (!flag) break;}if (!empty(s) && flag) return true;else return false;
}

表达式求值（尚不知考与否）
递归问题与非递归
递归会占用空间，递归n次空间复杂度O(n)
递归函数调用次数=内部次数+外部次数(通常1次外调)

// 求斐波那契数列
int feb(int n)  // 递归
{if (n==1 || n==2) return 1;else return feb(n-1) + feb(n-2);
}int feb(int n)  // 循环消除递归
{if (n==1 || n==2) return 1;t1=1; t2=2;for (i=3; i<=n; ++i){t3=t1+t2;t1=t2; t2=t3;}return t3;
}

3.4 队列

一般顺序队列会出现“假溢出”，所以顺序表用循环队列
循环队列

typedef struct
{QDataType *base;  // 初始化分配空间int front; // 队首元素int rear; // 队尾的下一个元素
}SqQueue;bool InitQueue(SqQueue &q)
{q.base=(*QDataType)malloc(MAX_SIZE * sizeof(QDataType));if (!q.base) return false;q.front = q.rear = 0;return true;
}

判空：rear==front
判满：(rear+1) % MAX_SIZE == front
队列长度：(rear - front + MAX_SIZE) % MAX_SIZE
入队

bool EnQueue(SqQueue &q, QDataType e)
{if ((q.rear+1) % MAX_SIZE == q.front) return false;q.base[q.rear] = e;q.rear = (q.rear+1) % MAX_SIZE;return true;
}

出队

bool DeQueue(SqQueue &q, QDataType &x)
{if (q.rear == q.front) return false;x = q.base[q.front];q.front = (q.front + 1) % MAX_SIZE;return true;
}

缺点和所有顺序表一样，固定长度，修改成本大
链队

typedef struct QNode
{DataType data;struct QNode *next;	
}QNode, *QPtr;
typedef struct
{QPtr front;QPtr rear;
}LinkQueue;bool InitQueue(LinkQueue &q)  // 建立头指针的链队
{p=(*QNode)malloc(sizeof(QNode));if (!p) return false;p->next = NULL;q.front = q.rear = p;return true;
}

入队

bool EnQueue(LinkQueue &q, DataType d)
{p = (*QNode)malloc(sizeof(QNode));if (!p) return false;p->data = d;p->next = NULL;q.rear->next = p;q.rear = p;return true;
}

出队

bool DeQueue(LinkQueue &q, DataType &d)
{if (q.rear == q.front) return false;p = q.front->next;d = p->data;q.front->next = p->next;if (p == q.rear) q.rear = q.front;  // 最后一个元素出队后，要手动把rear=frontfree(p);return true;
}

4.串、数组和广义表

typedef struct
{char *str;int length;
}String;

4.1 模式匹配算法

KMP
next数组计算方法(教材的值)：

s串第0个字符的next[0]=0
对于第i个字符(0<i<n)，next[i]=str(0到i-1的字串)最长前后缀重合部分 + 1
例：S=abaabcac
next=[0, 1, 1, 2, 2, 3, 1, 2]（此next值适用于第一个字符元素下标为1的字符串；教材是从1开始，S[0]表示字符串长度）

// 更适合通用的方法，下标从0开始，即next值为教材的 -1
void get_next(String S, int next[])
{i=0; j=-1;next[0]=-1;while (i<S.length){if (j == -1 || S.str[i] == S.str[j]){++i; ++j; next[i] = j; }else j = next[j]; }
}int kmp(String T, String S, int next[])
{i=0; j=-1;while (i<T.length && j<S.length){if (j==-1 || T.str[i] == S.str[j]){++i; ++j;}else j = next[j];}if (j == S.length) return i-j; // S子串在T的匹配位置else return -1; // 匹配失败
}

4.2 数组和矩阵

三角矩阵
sa[k]和mat[i][j]的关系是(下标均从0开始)
上三角：(i <= j) k = 从0行加到i-1行, n+(n-1)+…+(n-i+1) + (j - i)
= (2n - i + 1)i / 2 + (j - i)
下三角：(j <= i) k = (1+2+3+…+i) + j
= i(i + 1) / 2 + j

对称矩阵的压缩
mat[i][j] = mat[j][i]（下标从0开始，若从1开始，则i = i + 1, j = j + 1）
和三角矩阵差不多，一般以行为主序存储在下三角
(i >= j) k = i (i + 1) / 2 + j
(i < j) k = j (j + 1) / 2 + i

4.3 广义表

LS = (a1, a2, …, an)
取表头getHead(LS) = a1，只取头部元素，可以是原子也可以是子表
取表尾getTail(LS) = (a2, …, an)，一定要带括号，一定是子表
L = (a, b); getTail(L) = (b);
表长：原子和子表个数之和
表深：括弧重度，也等于最大子表深度+1，若无子表则为1（递归）

5. 树和二叉树

对于非空树：仅有一个没有入度的根，其他点最多有m个互不相交的有限集，m称为树的度。（m=2，二叉树）

5.1. 二叉树性质

第i层最多有2^i-1个结点
深度为k的树最多有2^k-1个结点
n0 = n2 + 1
完全二叉树的叶子结点只存在最大和次大两层，右孩子的深度为L，则左孩子深度为L或L+1
n个结点的完全二叉树深度为: floor(log2(n)) + 1
结点i的父结点是i/2
结点i的左孩子是2i，右孩子是2i + 1. 若大于结点总数n，则无左孩子or右孩子
N个结点可以组成C(2n, n) / (n + 1) 或 C(n, 2n) - C(n-1, 2n)个不同的二叉树[n个元素出栈顺序数]
某二叉树先序后续正好相反，则为空树或每个结点只有一个孩子，则只有一个叶结点

5.2 二叉树存储

一般采用链式存储

typedef struct BiTNode
{TDataType data;struct BiTNode *left, *right;
}BiTNode, *BiTree;

5.3 二叉树的操作

遍历

void preOrder(BiTree T)  // 先序遍历
{if (T == NULL) return;d = T->data;preOrder(T->left);preOrder(T->right);/** 中序inOrder(T->left);d = T->data;inOrder(T->right);*//** 后序postOrder(T->left);postOrder(T->right);d = T->data;*/
}void levelTravel(BiTree T)
{Queue q;initQueue(q);enQueue(q, T);while (!empty(q)){BiTNode node;deQueue(q, node);printf("%d", node->data);  // 若数据为整型if (T->left != NULL) enQueue(q, T->left);if (T->right != NULL) enQueue(q, T->right);}
}

复制二叉树

void copy(BiTree T, BiTree newT)
{if (T == NULL){newT = NULL;return;}newT = (*BiTNode)malloc(sizeof(BiTNode));newT->data = T->data;copy(T->left, newT->left);copy(T->right, newT->right);
}

计算深度

int depth(BiTree T)
{if (T == NULL) return 0;else return max(depth(T->left), depth(T->right)) + 1;
}

计算最大宽度

void getWidth(BiTree T, int count[], int level)  // 用count数组存储每层的数量，最大宽度是Max(count)
{if (T == NULL) return 0;else{count[level]++;getWidth(T->left, count, level + 1);getWidth(T->right, count, level + 1);}
}

5.4 线索二叉树

（考的少）
线索化是指：对二叉树的遍历结果中，体现出前驱后继的关系。
建立线索化：先进行X序遍历（先、中、后、层次）得到序列，在原树的结点加入Ltag和Rtag，若0则left, right指针指向左右孩子；若1则指向直接前驱和后继。

5.5 森林、树和二叉树

参考：树、二叉树和森林的转换

森林转二叉树：一棵树中，每一层中靠右的兄弟变成靠左兄弟的右孩子，最左的兄弟成为父结点的左孩子。对每棵树之间，靠右的树根成为靠左的树根的右孩子，最左的树根成为二叉树的根。
二叉树转森林：把根与右孩子分开成若干单独的二叉树（单独树没有右孩子）对于每棵二叉树，右孩子变兄弟连接到最左的兄弟的父结点，左孩子依然是孩子。

遍历
树的遍历
先根遍历：先访问根结点后访问孩子(从左至右)
后根遍历：先访问孩子后访问根结点
森林的遍历
先序遍历：先访问第一棵树的根结点，再访问根的子树，最后访问剩下的树
中序遍历：先中序遍历第一棵树的子树（从左至右，从叶到根的顺序）在访问根节点，最后访问剩下的树

5.6 霍夫曼树

会手动操作就行
主要思路：每次选择最小的两个值组成新结点，并加入到结点列表中，重复。
霍夫曼编码过程则是在建立树之后，按左为1，右为0的方式。直到叶结点。
HT表的构建参考电子书P129

5.7 其他应用

通过先序、中序，中序、后序，而得到一棵唯一的树（简单题目）先序、后序不能得到一棵唯一的树

6. 图

6.1 图的建立

邻接矩阵

typedef VexType char;
typedef ArcType int;
typedef struct
{VexType vexs[MAX_NUM];  // 顶点表，用来映射顶点名称(一般char)和数字下标(int)ArcType arcs[MAX_NUM][MAX_NUM];  // 邻接矩阵int vex_num, arc_num;
}AMGraph;

特点：

对于无向图，第i行元素之和表示顶点i的度。对于有向图，第i行元素之和表示顶点i的出度，第i列表示顶点i的入度。
mat[i][j]=1表示i和j之间有边
不利于增加删除顶点
不利于统计边数
空间复杂度高，n个顶点需要O(n²)的空间

邻接表
默认为邻接出表，即指向顶点的出度

typedef struct ArcNode  // 边结点
{int adjvex;struct ArcNode* nextarc;InfoType info;
}ArcNode;
typedef struct VNode  // 顶点结点
{VexType vex;struct ArcNode *firstarc;
}VNode, AdjList[MAX_NUM];
typedef struct
{AdjList vertices;  // 邻接表int vex_num, arc_num;
}ALGraph;

插入新边（有向图）

void insert(ALGraph &G, VexType v1, VexType v2, InfoType info)
{i = locate(G, v1); j = locate(G, v2); // 确定v1和v2在G的位置struct ArcNode* p = (ArcNode*) malloc(sizeof(ArcNode));p->adjvex = j;p->info = info;p->next = G.vertices[i]->firstarc;G.vertices[i]->firstarc = p;// 若为无向图，则把i和j反过来再插入一次即可
}

特点：

利于增加删除结点
统计边数方便，时复O(n+e)
空间效率高，空复O(n+e)
不利于判断v1和v2是否存在边，需要扫描v1和v2的边表，最差O(n)
不利于统计顶点的度，出表可以计算出度，但是计算入度需要遍历整个表。逆邻接表计算入度方便却计算出度困难

6.2 图的遍历

深度优先搜索和广度优先搜索
题目中可能考察深度优先生成树和广度优先生成树
两个遍历方法中，用邻接矩阵的时间复杂度是O(n²), 用邻接表复杂度为O(n+e)

6.3 图的应用

最小生成树

Prim算法：先随机确定一点，再每次选连通分量周围最小的边，复杂度O(n²)，适合稠密图
Kruskal算法：每次选不构成回路的最小边，复杂度O(eloge)，其中包含排序，适合稀疏图

最短路径
Dijskra算法：从源点到其他点最小距离（注意题目中可能要求完成距离变化表，电子书P157）
思路：
(1) 用d数组记录距离，起点为0，其他点为正无穷。从起点开始运算
(2) 对当前点所有邻边进行访问，若当前点的d值 + 其邻边代价 < 邻边的d值：则更新邻边的d值和其父结点
(3) 找到更新后的最小d值的点，放入“已完成”集合中，并把此边作为下一个运算的顶点
(4) 若“已完成”集合包含了所有顶点，则d值更新完成
(5) 终点的d值则为全局最小代价。从终点开始，循环访问其父结点可找到起点，这就是最短路径
Floyd算法：每个点之间最小距离（只适合邻接矩阵）

拓扑排序
一定是有向无环图，所以可以检测有向图中是否有环，无解则有环
过程：选一个无入度的顶点并输出，再删除这个顶点以它为尾的弧，重复。

关键路径
题目中主要是完成关键路径表
注意：影响关键活动的因素有很多，若子工程的时间有变化，则要重新计算关键路径，所以单提高一条关键路径上的关键活动速度，还不能导致工程缩短工期，必须同时提高几条关键路劲上的活动速度

6.4 十字链表

十字链表是有向图的另外一种存储方式，通常可视为把邻接表和逆邻接表结合的方式。
定义：
弧结点：tailvex, headvex, headLink, tailLink, info(信息位)
tailvex和headvex分别表示弧尾和弧头链接的顶点在图中的位置
headLink和tailLink分别表示弧尾和弧头指向（的顶点）相同的下一条弧
（也就是说：如果tailvex相同，则用tailLink连接，headvex相同用headLink连接）
顶点结点：data(信息位), firstIn, firstOut
firstIn表示第一个入度的边
firstOut表示第一个出度的边

稀疏矩阵压缩也可以用十字链表方式
通常也分为两个
元素结点: 行标、列标、元素值、指针A、指针B
其中前三个（行标、列标、元素值）一般也是三元组的组成，后面两个指针，A指向同行的下一个，B指向同列的下一个
表头：chead, rhead
数组chead存储所有的列表头，数组rhead存储所有行表头

7. 查找

7.1 顺序表

顺序查找ASL=(n+1)/2。可为顺序结构也可为链式结构
折半查找比较次数最多=floor(log2(n)) + 1，ASL=log2(n + 1) - 1。只能为可随机存储的顺序结构

int biSearch(SqList list, DataType e)
{low = 0; high = list.length - 1;while (low <= high){mid = (low + high) / 2;if (list.array[mid] == e) return mid;else if (list.array[mid] > e) high = mid - 1;else low = mid + 1;}return -1;
}

折半查找虽然数值上比顺序查找高效，但是不一定快于后者

7.2 二叉排序树

左子树若不为空，则比根结点小。右子树若不为空，则比根结点大。左右子树都是二叉排序树。
增加结点
简单，比结点大就放左子树，比结点小就放右子树，若不为空则继续

void insert(BSTree &T, BSDataType e)
{if (T == NULL){T = (BSTNode*) malloc(sizeof(BSTNode));T->data = e;T->left = T->right = NULL;}else{if (e < T->data) insert(T->left, e);else insert(T->right, e);}
}

删除结点
分为三个情况（删除x结点）

x为叶结点，直接删除即可
x有一个非空子树，直接把此子树替代x结点
x有两个非空子树，让中序序列的x的直接前驱替代x，左子树的最右的结点（相当于删去此结点替换到x的位置，若此结点也有子树(只有左子树)则启用方法2）

7.3 平衡二叉树

左右子树深度差为-1、0、1（称为平衡因子），左右子树都是平衡二叉树
四个旋转LL、RR、LR、RL，参考旋转方式

7.4 B-树

参考m阶b-树的特点：

每个结点最多m个子树，最少ceil(m/2)个子树
每个结点有n个信息，ceil(m/2)-1 ≤ n ≤ m-1（4阶b-树为[1,3]，5阶b-树为[2,4]）
叶结点都在同一层

增加结点：简单
以三阶b树为例：每次插入到叶子结点，若信息达到3个，则把下标m/2的信息（即中间的，第二个）上提到父结点，若父节点也达到3个，重复。
删除结点：三种情况，电子书P199
对于非终端结点，则用右子树的最左结点（即右边最小的元素）替代此结点并删除该叶子结点的元素
对于终端结点，如果信息 > ceil(m/2)-1，则无需更多操作
若 == ceil(m/2)-1，则向父结点借一位刚好比自己大的信息，若不满足，继续上借，直到下沉（参考文章）

7.5 散列表的查找

构建散列函数
要求：计算简单，尽量做到一个关键词一个散列地址。散列值在表长范围内，尽量减少冲突，并且均匀分布
没有好与不好的函数，只有适合与不适合的函数，处理冲突的方法也如此
处理冲突

开放地址法：若地址H0冲突则通过合适的计算得到另外一个地址H1
线性探测，二次探测（下一个位置为1², -1², 2², -2², …），伪随机探测（下一个地址Hi=base+di(伪随机序列)）
优点：充分利用散列表空间，缺点：线性探测容易发生“二次聚集”现象，二次探测和伪随机探测可以避免，但还是不可避免不断地地址冲突
链地址法：把相同散列值记录在单链表上

散列因子a = 状如表的元素数量n / 散列表长度length
一般情况下，a越大，空间利用越高，越容易发生冲突。a越小，不易冲突但空间浪费多

等概率情况下ASL	查找成功	查找失败
线性探测	1/2 (1 + 1 / (1 - a))	1/2 (1 + 1 / (1 - a)²)
二次探测，伪随机探测	-1/a ln(1 - a)	1 / (1 - a)
链地址法	1 + a / 2	a + e^-a
一般做题不会用上面公式，而是查找成功/失败的ASL用比较次数之和/总查找元素个数(电子书p209)

8. 排序

8.1 插入排序

思路：将待排序关键字插入到已排序好的序列中合适的位置
直接插入排序：顺序遍历序列，每次选择一个关键字插入到已排序好的序列中（从后往前），如果序列趋于正序，则插入部分速度越快，接近O(1)，最好情况是O(n)，最坏情况下序列完全颠倒O(n²)，平均O(n²)，空间辅助O(1)，排序稳定，可适用于顺序表和链表

折半插入排序：在直接插入的基础上改为折半查找并插入，性能和上面一样。序列趋于有序和无序速度接近，且不能适用于链表，只适合顺序表

希尔排序：缩小增量排序，增量k的意义是将表每隔k个元素进行一次直接插入排序（最好最好平均复杂度可参考上文直插排序），然后缩小k并重复上述操作，直到k=1时序列趋于有序，再对全体进行直插入排序。时复O(n^1.3)，空间辅助O(1)，排序不稳定，只可用于顺序表，而且序列n越大越明显

8.2 交换排序

思路：两两进行比较，若不符合次序则交换，直至整个有序
冒泡排序：对序列中相邻的两个数，若不符合顺序则进行交换，并继续迭代。如果没有发生交换，则算法结束。对于趋于正序，发生交换的次数减少，则迭代次数减少，最好情况是完全正序，时间复杂度O(n)，一般和最差时复O(n²)，空间辅助O(1)，排序稳定。可适用于顺序表和链表

快速排序：选择待排序列的某一个元素作为中枢pivot(一般第一个)，序列最后下标为high，第一个元素为low。从high往左找第一个比pivot小的元素，与pivot进行交换。再从low往右边找第一个比pivot大的元素，与pivot进行交换。重复操作直到low==high，则固定了这个元素在已排好序列中的位置。最后对此元素的左右子序列进行同样的交换操作。
对于元素趋于有序（正序or反序），快速排序则退化成直接选择排序，复杂度O(n²)，最好的情况是分布均匀的序列，复杂度O(nlogn)，平均O(nlogn)，因为用到了递归，则最坏空间辅助O(n)，平均空间辅助O(logn)，，不稳定排序，仅适用于顺序表

8.3 选择排序

思路：每一趟选择最小的关键字，放在已排好序列的最后
直接选择排序：序列前一段是已排序，后一段是未排序。每一趟在未排序序列中选择最小的元素，与未排序第一个进行交换。无论是否趋于有序，选择最小元素必须遍历一次序列，所以最好最坏平均复杂度都是O(n²)，辅助O(1)，不稳定排序，可用于顺序表和链表

堆排序：通过维护一个堆进行排序（以小根堆为例：从最后的非叶结点开始建立堆，即把根和左右孩子中最小元素作为根，并往前遍历直到整个堆的根，此过程复杂度O(n)），每次选出第一个元素，把最后一个元素放第一个后维护堆（此过程简述为：换上来的根元素X与最小的孩子进行交换，发生交换的一边继续交换，直到X比左右孩子都小，复杂度为O(logn)），堆为空的时候完成排序。复杂度O(nlogn)，空间可不用辅助数组O(1)，不稳定排序，仅顺序表

8.4 归并排序

思路：将两个及以上的有序表合并成一个有序表
2-路归并排序：1. 分治阶段：每次从中间分割序列，直到子序列长度<=2。2. 进行交换。3. 结合阶段：所有子序列按照分治阶段的分组进行整合。每次整合复杂度O(n)，分治结合的次数为O(logn)，所以总复杂度O(nlogn)。需要辅助数组O(n)和递归空间O(logn)，总空间辅助O(n)。稳定排序。可用于链表，而且两个有序链表的合并不需要辅助数组，辅助空间是递归空间O(logn)。但是需要手动找到序列中间位置。不过总时复不变

8.5 基数排序

不进行比较，根据关键字的值来分配，O(n)排序，稳定（考的少）

排序名称	最好情况	最坏情况	平均情况	空间复杂度	稳定性	链式结构可用
直接插入排序	正序O(n)	反序O(n²)	O(n²)	1	稳定	可用
希尔排序	O(n)	O(n²)	O(n^1.3)	1	不稳定	不可用
直接选择排序	O(n²)	O(n²)	O(n²)	1	不稳定	可用
堆排序	O(nlogn)	O(nlogn)	O(nlogn)	1	不稳定	不可用
冒泡排序	正序O(n)	反序O(n²)	O(n²)	1	稳定	可用
快速排序	相对无序O(nlogn)	正序或反序O(n²)	O(nlogn)	logn(最坏n)	不稳定	不可用
归并排序	O(nlogn)	O(nlogn)	O(nlogn)	n	稳定	可用(链表版辅助空间logn)