算法难点复习
0x00 kmp
字符串比较算法，核心思想，跳过重复比较，例子：
/*
->abababc str
->ababc pattern
-> ababc
-> ababc
*/
在str[4]与pattern[4]时不同，暴力求解时，将str指针i+1，将pattern指针j置0，然后a与b比较，不同然后又将i+1,j置0得到结果，最终匹配。 时间复杂夫m*n
考虑优化
当在pattern[4]处发生不匹配时，我们直接将pattern串整体右移2，str i指针不变，patternj指针j=j-2,2是右移的位数。为什么能够直接右移2呢，因为已经匹配长度为4的字符串，前缀和尾缀的部分匹配值为2（前缀和尾缀的最大公共部分）,因此可以直接右移4-2个位置
因此kmp查找字串的框架为：
int solv(const string& str,const string& pattern){
int i=0,j=0;
for(;i<str.size()&&j<pattern.size();){
if(str[i]==pattern[j]) {
i++;j++;
}else{
if(j=0){
i++;
j++;
}else{
j=j-(j-1-match[j-1]);
}
}
}
if(j==pattern.size()) return i-pattern.size();
else return -1;
}
怎么求match数组呢？用表达式递推，match[n]=match[n-1]+1 ,当pattern[n]==pattern[match[n-1]] 。这个表达式的原因n-1的头缀和尾缀 都有一个共同的新添加元素pattern[n]，因此头缀和尾缀的长度都加1，因此match[n]=match[n-1]+1。如果不等呢，那就要考虑缩短原来的头缀，且头缀的最后一个元素也要与pattern[n-1]相等，之前是pattern[match[n-1]-1],现在这个元素是pattern[ match[ match[n-1]-1]-1 ],pattern[n]比较的是pattern[match[ match[n-1]-1 ]],相等match[n]=match[match[n-1]-1]+1,那边界条件是什么呢？边界条件是如果不想等时，pattern[i] i是被比较的元素，已经为0时，说明已经不能再比较了，此时match[n]=0; kmp算法时间复杂度m+n
0x01 二叉树的非递归遍历
将递归函数转为非递归函数需要栈的支持。
考虑函数的实现，通过栈保存调用位置，因此我们也需要一个结构保存递归的时的位置。
void preorder_trans(Node* p){
if(p){
preorder_trans(p->l);
visit(p);
preorder_trans(p->r);
}
}
struct node{
int val;
struct node* l;
struct node* r;
int step;
node():val{0},l{nullptr},r{nullptr},step{0}{};
};
void visit(node* p){
cout<<p->val<<endl;
}
void trans(node* p){
stack<node*> s{};
s.push(p);
while(!s.empty()){
node* p=s.top();
if(!p){
s.pop();
continue;
}
switch (p->step)
{
case 0:{
s.push(p->l);
}
break;
case 1:{
visit(p);
}
break;
case 2:{
s.push(p->r);
}
break;
default:
s.pop();
break;
}
p->step++;
}
}
因为每一个节点作为参数产生一个函数调用栈，因此我们不妨在node中定义一个step表示阶段。用一个while循环当作cpu，当函数调用不空，也就是栈不空时，一直循环，每次对当前栈（top）进行一次处理，将其阶段+1；根据原来递归函数，可以在不同的阶段产生新的调用栈，下一次循环时就来到栈顶，而如果某个栈执行到了最后阶段，就pop掉该栈，即退出函数调用。
空间复杂度O(n)时间复杂度O(n)
补充线索二叉树
线索二叉树通过增加两个标志位区分左右节点是否存在，还是保存的前驱后继。
线索二叉树用途：遍历速度快， 不需要递归
中序线索二叉树的构建：（0表明是子节点1是前驱后继）
void mid_trav(Node* pre,Node* n){//pre用于修改n的l 同时修改pre的r为p
//每一次处理节点只左两件事，将前面传入的pre设置为n的l（当n的l不存在时）
//第二件事，如果pre的r不存在，那么将pre的r设置为p。
//而对于左右子节点的递归处理，由于左节点总在当前节点前（中序遍历），因此pre
//总是试图传给当前节点的左节点。
//而对于右节点，当前节点总比右节点前，因此试图将当前节点作为pre交给右节点，让右节点
//去找到底是谁的pre
if(!n) return;
mid_trav(pre,n->l);
if(!n->l){
n->ltag=1;
n->l=pre;//指向前驱
}
if(pre&&!pre->r){
pre->rtag=1;
pre->r=p;
}
mid_trav(p,p->r);
}
以下是该线索二叉树的遍历
void trans(Node* root){
for(Node* p=findstart(root);p;p=findnext(p)){
visit(p);
}
}
Node* findstart(Node*p){
if(!p) return nullptr;
while(p->l){
p=p->l;
}
return p;
}
Node* findnext(Node* p){
if(p->rtag==0) reutrn findstart(p->r);//如果右节点存在，则是以右节点为root，找第一个
else return p->r;
}
0x02 树转二叉树、森林转二叉树
树转二叉树，对于其子节点，选一个（一般是第一个）作为其左孩子，其余子节点（兄弟节点），作为左孩子的右孩子，不断向右延申。然后对每一个子节点重复前面过程，伪代码如下：
//由于对一个节点的处理，会移动其原本子节点的位置，因此使用层序便来来处理最好，在处理节点时，能将其子节点先保存在队列里
void trans(Node* p){
if(!p) return;
queue q{};
q->append(p);
while(q.size()){
p=q.dequeue();
Node* l=nullptr;
//i=0时是第一个选为左孩子不用改变位置
for(int i=0;i<p->childsize();i++){
if(i==0) {
p->l=p->child[0];
l=p->l;
}else{
l->r=p->child[i];
l=p->child[i];
}
q.append(p->child[i]);
}
}
}
而森林的转换则可以可以给所有僧侣加一个根节点，转换成二叉树后去掉根节点。
0x03 哈夫曼树与编码
哈夫曼树是带权路径和最短的树，应用于压缩算法，带权路径指，叶子节点的权值*根节点到叶子节点的路径长度（边数，在第二层则路径长1，依此类推）。而哈夫曼树的所有叶子节点的带权路径和最小。构造方法如下：
//1将n个节点作为n个仅含1个节点的二叉树,形成一个森林
//2从森林中移除根节点的值最小的两个二叉树，作为左子树右子树，添加一个根节点，为左右子树的根的和，放回森林
//3重复2，直到森林中仅有一棵树，即为哈夫曼树
哈夫曼树用于前缀编码，即任何一个编码是其他编码的前缀。对于文本压缩，假设仅有a-z26个字母，则根据字母出现的次数作为权重，形成哈夫曼树，从根开始，左边代表0，右边代表1，访问一个叶节点产生的边序列，即为对应字符的哈夫曼编码。
每次都需要找到最小的两个节点，更新后插入最大节点，适合用堆，此时时间复杂度O(nlog) 空间复杂度O(n)
0x04 并查集
并查集，集合中选一个元素作为根节点，其余元素作为子节点，记录每一个元素的根节点，根节点记录该集合元素个数。并操作，一个集合的根节点的根节点设置为另一个集合的根节点。 查操作（查询元素属于哪个集合），不断访问其根节点，直到无根可循。
0x05 图概念及特征
完全图，有向图中指任意两个顶点存在两个方向边，无向图任意两点存在边，故边数前者为n*(n-1) 后者为n*(n-1)/2 每个点有n-1条边，n个点，但是被计算了两次。
连通图，指无向图中任意两点存在路径，连通分量，非连通的无向图中的极大连通子图（包含最多都互相连通的顶点和边）。 n个顶点的无向图，不连通同时最大边的数量：(n-)*(n-2)/2 ，即除一个顶点外，其余完全图。
强连通，指有向图
生成树：指完全图中包含全部顶点的极小连同分量（包含最少的边，因为顶点要求了为全部顶点）
度，指依附顶点的边数，无向图度=2*e,因为一条边被算两次
0x06 图的有关算法
遍历 DFS，访问起始顶点，依次访问与之相邻的顶点，直到无相邻顶点可访问，在访问相邻顶点时，递归的重复上述过程：
void DFS(Node* p){
visit(p);
for(auto child: p->child){
if(!child->visit)
DFS(child);
}
}
BFS 类似于树的层序遍历，1将起始顶点加入队列，2出队列一个元素，访问 3将该元素的相邻节点加入队列，重复23直到队列空
void BFS(Node* p){
queue q{};
q.push(p);
while(q.size()){
p=q.front();
q.pop();
visit(p);
for(auto child:p->child){
if(!child->visit)
q.push(child);
}
}
}
DFS BFS 的复杂度分析，首先都遍历了所有顶点，其次，访问了顶点的所有边。因此如果使用邻接矩阵，那么访问顶点所有边为n^2,而遍历顶点为n，因此时间复杂度O(n^2),如果用邻接表则访问所有边为E,因此为O(n+e) 对于稀疏图，适合用邻接表，对于稠密图，适合邻接矩阵。
判断图是否连通，任意选一个顶点，进行遍历，如果遍历后仍然有点未访问，则不连通。
最小生成树：即极小连同分量，且边的权之和最小。原则是贪心算法：不断选择最小且不形成回路的边。最小生成树不止一棵，但权值和一样。
两种方法，prim算法，保证不形成回路的方法就是不断往已经形成的连通分量里 新增边最小的顶点。从始至终都是一个连同分量，直到扩展到极小连通分量包含所有顶点。
kruskal：保证不形成回路的方法，不断将属于两个不同连同分量，且距离最小的顶点对连接起来。
最短路径
dijinstra： 贪心算法，有两个列表，一个记录已经加入最短路径的顶点，另一个记录未加入的。初始仅有起点加入。distance[n]负责记录点到起点的距离，初始时起点为0，不相连的为+∞。 path[n]记录最短路径时，上一个节点
每次从未加入的列表中选一个distanc最小的点加入，并更新与之相连距离。不断重复直到所有点加入。
void dijinstra(Node* start,vector<int>& distance,vector<int>& path){
init(distance);
init(path);
vector<int> exclude{};
init(exclude);
while(exclude.size()){
Node* tmp=pop_min_distance(exclude);
for(auto close:tmp){
if(distance[tmp]+e(tmp,close)<distance[close]){
distance[close]=\
distance[tmp]+e(tmp,close);
path[close]=tmp;
}
}
}
}
使用邻接矩阵时，n个顶点都要访问，每次找最小的顶点需要遍历n个，找所有相邻的边需要也遍历n个，因此时间复杂度为O(n^2)。使用邻接表也一样，因为总需要找最小顶点。
froyd,动态规划的方法，对于矩阵dist[n][n],初始状态 dst[i][j]= 0 (当i=j) / d(当i与j直接相连距离为d) /+无穷（ij不直接相连）。进行n次迭代，每次迭代考虑经过k点。原理是 dist[i][j]=min( dist[i,j] ,dist[i][k]+dist[k][j] ),即是经过k点与不经过k点的较小者。通过n此迭代，将i j之间经过所有点的路径都考虑，自然得到了最小值。
for(int k=0;k<n;j++){//考虑经过第k个点
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
if(dist[i][k]+dist[k][j]<dist[i][j]){
dist[i][j]=dist[i][k]+dist[k][j];
}
}
}
}
时间复杂度显然O(n^3),空间O(n^2)
0x07 查找
线状查找
顺序查找，遍历因此为O(n)，空间O(1),适合链表和顺序表
二分查找，有序的顺序表，时间复杂度O(logn)
分块查找，又称索引查找，将数据分成若干块，块内可以无序，但是块之间有序，记录每个块的边界值和索引值。
树状查找
二叉搜索树，对于每个节点，要求左儿子比他小，右儿子比他大。搜索时同样,查找算法
Node* find(Node* p,int tar){
if(!p) return nullptr;
if(p->val==tar) return p;
else if(tar<p->val) return find(p->l,tar);//左边查找的结果
else return find(p->r,tar);//右边查找的结果
}
插入：
Node* insert(Node* p,int tar){
if(!p){//没找到该节点，插入进去。
return new Node{tar};
}
if(tar<p->val) {//比当前节点小 去左子树做插入，并刷新关系
p->l=insert(p->l,tar);
}
else if(tar>p->val){//去右子树插入，刷新关系
p->r=insert(p->r,tar);
}
return p;//insert 返回插入后当前层的节点
}
删除： 删除有三种情况：①如果是叶节点，当然可以直接删除。②有一个子节点，直接删除让子节点代替 ③有两个节点，找最接近的那个叶节点代替（左子树的最大值，或者右子树最小值）
Node* find_left_clear(Node* p){
if(!p) return nullptr;
while(p->r){
p=p->r;
}
return p;
}
Node* Delete(Node*p,int tar){
if(!p) return nullptr;
if(p->val==tar){
if(p->l&&p->r){
Node* x=find_left_clear(p->l);
p->val=x->val;//交换位置
p->l=Delete(p->l,x->val);//
return p;
}else if(!p->l&&!p->r){
delete p;//记得释放
return nullptr;
}else{
Node *x=nullptr;
if(p->l) x=p->l;
else x=p->r;
delete p;
return x;
}
}else if(var>p->val){
p->r=Delete(p->r,tar);
}else{
p->l=Delete(p->l,tar);
}
return p;
}
平衡的二叉树查找插入删除时间复杂度都是O(logn),但问题就是容易在插入删除后不平衡。
查找种类，一种是静态查找，不怎么插入删除，适合使用顺序储存的二分查找。另一种是动态查找，需要插入删除，适合查找树或者散列查找
通过使用
0x08 平衡查找树
avl平衡二叉树
定义对于任意一个节点，左右子树高度相差不大于1。插入和删除会破坏这种平衡，因此需要调整。
插入：分为四种情况:
①新插入的节点是不平衡节点的左子树上的左孩子，需要LL旋转（右单旋）
a b
b -> d a
d //d是新插入节点，a是插入后不平衡节点，ll旋转
②是不平衡节点的右子树上的右孩子,需要RR旋转（左单旋），类似
③是不平衡节点的左子树上的右孩子，需要LR旋转，先左旋再右旋
a a c
b ->左旋 c ->右旋 b a
c b
④是不平衡节点的右子树上的左孩子，需要RL旋转，先右旋再左旋，类似不举例
删除
avl树的删除，也遵循二叉查找树的删除，删除后调整，值得注意的是，avl树的删除调整会向上传递
删除操作的四种旋转和插入的定义有所不同。从实际删除位置向上回溯，找到第一个不平衡节点X,找到X
的高度最高的子树根节点Y,找到Y的高度最高的子树根节点Z,由三者关系判定旋转，举例一条：
①Z是X的左子树上的左孩子，需要LL旋转右单旋转，其余三种和插入一样按照本条格式。
但是X平衡后并非结束，继续沿X往根节点回溯，重复上述过程，直到根节点也平衡。
插入删除查找 logn
红黑树
红黑树性质有5条，①节点非红即黑②根节点是黑（根节点不保存信息，虚构的）③叶节点是黑④不存在连续两个红色节点⑤任一叶节点到根节点路径上的黑色节点数量都相同，
这5条性质保证了红黑树的平衡（根到叶节点最长不大于最短的两倍），所有的一切都是根据上述5条推出来的。例如平衡性质：由于跟到叶的黑节点一样，因此差异主要在红色节点，但又不能连续两个红色节点，最多也就一个，或者干脆连续黑色节点，因此最长不可能大于2倍最短。
红黑树与avl树，红黑树的平衡要求更低，因此插入删除时的调整更少，跟适合插入操作多的场景
插入删除查找 logn
B树B+树
两者都是多路平衡查找树，通过对节点的子树个数进行约束，来确保平衡，同样插入删除会破坏平衡，要调整。
两者通常都用在磁盘的文件的查找上，因为是多路，所以大大降低了树高减少了磁盘访问次数
两者区别：①B树中非根节点索引指向下一级索引块，同时包含该所索引对应的数据的位置；而B+树非根节点只负责指向下一级索引块，因此下一级索引块仍然包含该索引，一直到叶节点，所有索引均在叶节点出现，并指向对应的数据位置。 ②由于B+树所有索引均在叶节点出现且有序，因此即可多路查找，又可顺序查找，非常适合数据库。
插入删除查找 logn
散列表
使用关键字进行运算，得到对应数据地址，理想状态 为O(1)的插入删除查找
散列方法：直接定址 除留余数 数字分析 （c++中的对象比较是否相等，就是用hash值）
冲突处理 不同关键字散列到同一个地址，虽然尽量设计好的hash函数仍无法避免，（本质和信息论有关，不可能用较小的信息表示较大的信息）。
开放定址法和散列表：前者通过对碰撞后的地址再处理，得到新的地址，后者通过链表，实现同一个地址装载多个数据。通过遍历链表查找。 常见的开放定址：线性探测，不断加+1 ;平方探测 不断+ （-1）^i * i^2
装载因子，hashmap（c++里的unordered_map）已经储存的记录数/hashmap长度，因子越大容易碰撞，导致效率降低。因此一般到达一定值，就重新分配空间，然后复制数据
c++中map使用红黑树
0x09 内部排序
基于插入的排序
插入排序：
void sort(vector<int>& v){
for(int i=1;i<v.size();i++){
int tar=v[i];
int j=i;
for( ;j-1>=0;j--){
if(tar<v[j-1]) v[j]=v[j-1];
else break;
}
v[j]=tar;
}
}
思路：从第二个元素开始，开始插入。插入的方法，依次与已有项X比较，小于则将X往后移项暂时插在X空出的位置，继续往前比较，如果大于等于，则停止往前，将该元素实际插入。
平均时间复杂度O(n^2) 最好O(n),当已经有序时。稳定
希尔排序：
void sort(vector<int>& v){
for(int k=v.size()/2;k>0;k/=2){
for(int i=k;i<v.size();i++){
int j=i;
int tar=v[i];
for( ;j-k>=0;j-=k){
if(tar<v[j-k]) v[j]=v[j-k];
else break;//最近写代码容易把break网络
}
v[j]=tar;
}
}
}
思路: 由上面可知，插入排序时越有序越快，因此希尔排序则先多次预排序，使得较为有序，最后跨度为1时排序较快。希尔排序的时间复杂度在O(N^1.4)左右，不稳定，因为跳着比较，容易将相同的两个元素不同处理（往前插入或者保持不动）
基于交换的排序
冒泡排序
void sort(vector<int>& v){
for(int i=1;i<v.size();i++){//只需n-1趟
bool flag=false;
for(int j=0;j<v.size()-i;j++){
if(v[j+1]<v[j]){
swap(v[j+1],v[j]);
flag=true;
}
}
if(!flag) break;//如果一趟下来没有交换过，说明已经有序。
}
}
思路：冒泡排序每次比较相邻的两个，不断向后移动到末尾，每一趟，都使的一个最大的元素被移到末尾，确定一个有序位置，一共需要n-1趟，如果有一趟没有交换，说明已经有序。 时间复杂度O(n^2) 有序时最好为O(n)，不稳定，因为两个相同最大元素，前面的那个会被移到最后
选择排序
void sort(vector<int>& v){
for(int i=0;i<v.size()-1;i++){
int max_pos=0;
for(int j=1;j<v.size()-i;j++){
if(v[j]>v[max_pos]){
max_pos=j;
}
}
swap(v[max_pos],v[v.size()-1-i]);
}
}
思路：选择排序类似于冒泡排序，不同点是，选择排序并不通过交换相邻获取最大，而是直接扫描最大，放在末尾，一共n-1趟。时间复杂度O(N^2),不受v元素排列情况影响，相较与冒泡排序，减少了交换次数，但是增加了扫描次数
快速排序
//partition 函数作用，给定一个值（pivot）和一个序列，要求一个插入位置，
//使得插入后序列左边小于该值，右边大于该值，使用双指针法
int partition(vector<int>&v,int left,int right){
int pivot=left;
int tar=v[pivot];
left++;
//循环条件，right>=left 边界条件是right==left 这个时候
//不能说明此时right就是我们要插入的位置，原因可能时left和right初始都指向同一个元素
while(right>=left){
//找到第一个大于tar的位置，right==left时也继续+，因为很可能v[right]也小于tar
while(right>=left && v[left]<=tar)left++;
//如果right>left时说明还有交换的必要
if(right>left) swap(v[left],v[right]);
//找到第一个小于tar的位置，right==left时也继续-因为可能v[left]也大于tar
while(right>=left&& v[right]>=tar) right--;
if(right>left) swap(v[left],v[right]);
}
swap(v[pivot],v[right]);
return right;//此时right即是需要插入的位置
}
void sort(vector<int>& v,int left,int right){
if(right<=left) return;
int mid=partition(v,left,right);
sort(v,left,mid-1);
sort(v,mid+1,right);
}
快速思路，使用二分法，选一个元素作为主元，将待排序列分为两部分，左边全部小于主元，右边全部大于主元，然后递归的对左右两边使用快排。
对于给定的一个元素和一个序列，如何找到一个位置将序列划分为左边小于元素右边大于元素，使用双指针法，l指针用来表示从左起第一个大于主元的元素位置，r指针从右起第一个小于的元素位置。在r>l时，元素可以交换，r<=l时则不能交换，并且r<l时应该出循环，此时r的位置即为主元应该插入的位置
时间复杂度O(nlog),由于使用栈，空间复杂度为栈深，O(logn),最坏情况下，（每次分为1和n-1）,时间复杂度O(n^2) 空间复杂度O(n)
堆排序
void heap_adjust(vector<int>& v,int p){
int parent=p;
int lchild=(parent+1)*2-1;
for( ;lchild<v.size() ; ){
int max_child_pos=lchild;
if(lchild+1<v.size()&&v[lchild+1]>v[lchild]) max_child_pos++;
if(v[parent]<v[max_child_pos]){
swap(v[parent],v[max_child_pos]);
parent=max_child_pos;
lchild=(parent+1)*2-1;
}else{
break;
}
}
}
void heap_init(vector<int>& v){
int child=v.size()-1;
int parent=(child+1)/2-1;
for(;parent>=0;parent--){
heap_adjust(v,parent);
}
}
void heap_push(vector<int>& v,int val){
v.push_back(val);
int child=v.size()-1;
int parent=(child+1)*2-1;
while(child>0&&v[child]>v[parent]){
swap(v[child],v[parent]);
child=parent;
parent=(child+1)*2-1;
}
}
int heap_pop(vector<int>& v){
int ret=v[0];
swap(v[0],v[v.size()-1]);
v.erase(v.size()-1);
heap_adjust(v,0);
return ret;
}
void sort(vector<int>&v){
heap_init(v);
int len=v.size();
for(int i=0;i<len;i++){
cout<<heap_pop(v)<<endl;
}
}
堆排序思路 先将底层构成子堆，然后不断向上构建，因为子堆是有序的，因此只需与子堆的堆顶比较，不断调整子堆堆定和当前堆顶。 构建堆的时间复杂度O(n)， 将堆顶全部输出的时间复杂度O(nlog)(每次输出一个需要调整，时间复杂度O（logn），n次) ，空间复杂度O(1),序列本身占用的空间不计入内。
堆这种结构很巧妙，算法中常用。
归并排序
int merge(vector<int>& src,vector<int>& dest,int l,int r){//返回当前层数 决定从哪个数组复制
if(r==l) return 1;
else if(r-l==1){
if(src[l]>src[r]) swap(src[l],src[r]);
return 1;
}
int mid=(l+r)/2;
int p1=l,p2=mid+1;
int d1=l;
int last_ret=merge(src,dest,l,mid);
merge(src,dest,mid+1,r);
vector<int>* v1=&src;
vector<int>* v2=&dest;
if(last_ret%2==0){
v1=&dest;
v2=&src;
}
for(;p1<=mid&&p2<=r;){
if((*v1)[p1]<(*v1)[p2]) {
(*v2)[d1]=(*v1)[p1];
p1++;
d1++;
}else{
(*v2)[d1]=(*v1)[p2];
d1++;
p2++;
}
}
while(p1!=mid+1) (*v2)[d1++]=(*v1)[p1++];
while(p2!=r+1) (*v2)[d1++]=(*v1)[p2++];
return last_ret+1;
}
vector<int>& sort(vector<int>& src,vector<int>& dest){
int ret=merge(src,dest,0,src.size()-1);
return ret%2==1?src:dest;
}
思路，归并排序和快速排序思路一样，也是用二分法，但是需要一个等长的空序列作为缓存，时间复杂度O(nlogn),空间复杂度O(n) (证明，每一趟将序列全部遍历一次，共遍历logn次，因此时间复杂度NlogN)
基数排序，又称桶排序，利用多关键字或者单关键字来排序，比如已知数字均为3位以内，那么可以先用各位在0-9的桶上排序，再用十位，再用百位。可以直到其时间复杂度为O(n)
只有基数排序能做到O(N)
0x0a 外部排序
外部排序，从硬盘读入数据，排序后再写回硬盘，由于内存并不能一次缓存全部数据，因此采用归并排序。现在假设有2000个记录，每个硬盘块能记录125个，因此一共记录在16个块，现在内存无法一次读入全部数据，如何进行排序？
考虑内存能读入全部数据时，采用快速排序等可以全部排序，然后依次输出，共计读16个块，写16个块。
现在不能读入全部内存，那么我们采用归并排序，将16个块，先分成8组，每两个进行归并， 对于每一组，读入内存，分别先排好序，再用双指针归并到输出缓冲区，缓冲区每次满一个块就写回到磁盘块。因此从16个单独记录变成8组记录 共计也是读16个块，写16个块（1组两个块了，8各组写回）。重复这个过程，共4轮，一共32*4=128次块读写。
优化
因此我们发现，外部排序的速度（磁盘读写次数）取决于轮数，如果我们采用多路归并，也就是将多个归并成1组，那么轮数大大减少，因此排序速度加快
但是当k（归并路数）太大时，内部排序时间会很大，因此采用败者树优化，败者树的主要原理是减少多路归并时比较次数，加快内部排序。
