•     邻接矩阵的思想是，用一个二维矩阵来代表顶点和边，用矩阵的下标来代表顶点，矩阵edges[i][j]的值来代表i到j是否存在一条边。存在边记为1，不存在记为∞。
•     邻接矩阵中的一行1的个数就是该顶点的出度，一列1的个数就是该顶点的入度。

typedef struct
{
    int no;    //顶点的编号
    char info;    //顶点的其他信息 一般情况下不用写
}VertexType

typedef struct    //图的定义
{
    int edges[maxSize][maxSize];
    //邻接矩阵定义，如果是有权图，把int换成char
    int n,e;      //分别是顶点数目和边的条数
    VertexType vex[maxSize];//存放节点信息
}MGraph;            //图的邻接矩阵类型

void f(MGraph G)    //参数是表示图的结构体变量G
{
    int a=G.n;    //取图的顶点数赋值给a
    int b=G.e;    //取图的边数赋值给b
    if(G.edges[i][j]==1)    //判断i和j之间是否有边
}

• 邻接表的思想是把每个顶点和每个顶点的边存储成一个单链表的形式；图的邻接表分为两个部分，一是顶点表：用来存放顶点信息（一般是顶点的编号）和指向第一个边结点的指针（即指向直接相邻的顶点）；二是边表，其中的结点存放的也是该顶点的信息（编号），指针指向头结点的其他相邻接结点。（注意！）
• 需要注意的是，这样的存储结构每条边都会出现两次 

typedef struct ArcNode    //边表节点结构体
{
    int adjV;    //边结点的序号
    struct ArcNode*nextarc;    //指向下一个邻接结点的指针
    /*int info*/    //存储结点的一些信息
}ArcNode;
typedef struct    //头顶点的结构体
{
    int data;    //头结点的标号
    ArcNode*first;    //指向第一个邻接结点的指针
}VNode;
typedef struct    //图的邻接表结构体
{
    VNode adjList[maxSize];    //头结点数组
    int n,e;        //节点数量和边的条数
}AGraph

• 在有向表中，有邻接表也有逆邻接表。

1. 算法思想：一直往深处走，走不动就退回一个看能否接着往深处走
2. 算法执行过程：任取一个顶点，访问它，检查这个顶点的所有邻接顶点，递归的访问其中未被访问过的顶点。
3. 以邻接表为存储结构的图的深度优先搜索遍历算法

• 先复习一下邻接表的结构体表示吧~

• typedef struct ArcNode    //边结点、类似于树的孩子存储方式中的分支
  {
      int adjvex;    //这条边所指的顶点、即邻接顶点
      struct ArcNode*nextarc;    //指向下一个边结点的指针
  }ArcNode;
  typedef struct    //图的顶点结构体设计，与树的结点一样
  {
      int data;    //该顶点的编号
      ArcNode*firstarc;    //指向该顶点第一条边的指针
  }Vnode;
  typedef struct    //邻接表的结构体定义
  {
      VNode adjlist[maxSize];    //元素是顶点VNode类型的数组，下标包含了所有顶点的下标
      int n,e;    //图的顶点数目n和边的数目e
  }AGraph;

• DFS具体的代码实现

int visit[maxSize];
/*v是起点编号，visit[]是一个全局数组，用来标记顶点是否已经被访问过了，
visit的初始值为全0，当访问到一个节点是把visit的值置为1*/
void DFS(AGraph*G,int v)    //传入的参数是邻接表表示的图G和起点元素编号
{
    ArcNode*p;    //设置一个边指针p
    visit[v]=1;    //把第一个顶点标记为“已访问”
    Visiti[v];    //指的是各种访问操作
    p=G->adjlist[v].firstarc;    //通过定点元素编号取到这个顶点VNode型，再取
                                 //该顶点的第一条邻接的边指针（ArcNode型）
    while(p!=NULL)        //边指针不为空即顶点有邻接的顶点时
    {
        if(visit[p->adjvex]==0)        //若邻接的顶点没有被访问
                                       //这里的p->adjvex是取了边指向的顶点
            DFS(G,p->adjvex);          //就对此顶点再用DFS（递归的思想）
        p=p->nextarc;           //访问完一个边再访问下一条边
    }
}

• 这里如果把图的深度遍历中所经过的边留下，其余的边删掉就形成了图的深度优先搜索生成树

• 贪心算法：“贪”：每一步都要最好的；“好”：权重最小的边

• 需要约束：只能用图里有的边、只能正好用掉V-1条边、不能有回路

1、prim算法----让一颗小树长大（适合稠密图）

（1)算法思想

    先构造一个根节点，然后一个一个收录顶点，从未收录的顶点中收录dist最小者；每收录进一个顶点，检查它的每个邻接点W，是否V的收录使W的dist变小了？如果变小则更新dist的值。这样的V不存在时，跳出循环。跳出循环有两种情况：

• 顶点全部收录完毕----------算法执行成功

• 未收录的顶点里面全都是dist=无穷大的点，即图不连通

• 而什么叫收录一个顶点到生成树呢？ 就是把结点到树的距离dist[V]设置成0*

Q：dist要怎么初始化呢？

• A：dist的初始值是顶点到根节点的距离，那么，若dist和根节点有直接相连的边，初始化为边的权重；否则应该初始化为正无穷。*

（2）伪码实现

（3）时间复杂度 T=O(|V|2) 对于稠密图比较合算

2、Kruskal算法---------将森林合并成树（适合稀疏图）

（1）算法思想

    把图的每一个结点都看作是一棵树，每次收录不是收录结点，而是收录权值最小的边。只要这条边符合要求（不构成回路、没有超过V-1条），就把他收录，并把收录进的边和它所连接的结点看作生成树。

（2）伪码实现

（3）时间复杂度-----------T=O(|E|log|E|)

void Prim(MGraph g,int v0,int &sum)
{
    int i,j,k;
    int v,min;
    v=v0;
    int vset[maxSize],lowcost[maxSize];
    for(i=0;i<g.n;++i)
    {
        vset[i]=0;
        lowcost[i]=g[v0][i];
    }
    vset[v0]=1;
    sum=0;
    for(i=0;i<g.n-1;++i)
    {
        min=INF;        //INF是一个已经定义的比图中所有边的权值都大的数
        for(j=0;j<g.n;++j)
            if(vset[j]==0&&lowcost[j]<min)
            {
                min=lowcost[j];
                k=j;
            }
        vset[k]=1;
        sum+=min;
        v=k;
        for(j=0;j<g.n;++j)
            if(vset==0&&g.edges[v][j]<lowcost[j])
                lowcost[j]=g.edges[v][j];
    }
}

typedef struct    //图的边结点结构体定义
{
    int a,b;    //这条边连接的两个顶点
    int w;    //边的权值
}Road；
Road road[maxSize];    //    构建一个边结构体数组来存储图（新的数据结构！）
int v[maaxSize];    //定义一个并查集
int getRoot(int a)
{
    while(a!=v[a])
        a=v[a];
    return a;
}
void Kruskal(MGraph g,int &sum,Road road[])
{
    int i;
    int N,E,a,b;
    E=g.e;
    N=g.n;
    for(i=0;i<N;++i)
        v[i]=i;
    
    sort(road,E);
    for(i=0;i<E;++i)
    {
        a=getRoot(road[i].a);
        b=getRoot(road[i].b);
        if(a!=b)
        {
            v[a]=b;
            sum+=road[i].w;
        }
    }
}

void printfPath(int path[],int a)    //输出到某个顶点a的路径
{{
    int stack[maxSize],top=-1;
    while(path[a]!=-1)
    {
        stack[++top]=a;
        a=path[a]
    }
    stack[++top]=a;
    while(top!=-1)
        cout<<stack[top--]<<" ";
    cout<<endl;
}

void Dijkstra(MGraph g,int v,int&path[],int &dist[])
{
    int i,j;
    int set[maxSize];
    int min,u;
    for(i=0;i<g.n;++i)
    {
        dist[i]=g.edges[v][i];
        if(dist[i]<INF)
            path[i]=v;
        else
            path[i]=-1;
        set[v]=0;
    }
    set[v]=1;path[v]=-1;
    /*初始化结束*/
    /*开始关键操作*/
    for(i=0;i<g.n-1;++i)
    {
        min=INF;
        /*找出一个dist最小的点，加入到最短路径里*/
        for(j=0;j<g.n;++j)
            if(set[j]==0&&dist[j]<min)
            {
                min=dist[j];
                u=j;
            }
        set[u]=1;
        /*看新加入的顶点对j的最短路径有没有影响*/
        for(j=0;j<g.n;++j)
            if(set[j]==0&&dist[u]+g.edges[u][j]<dist[j])
            {
                dist[j]=dist[u]+g.edges[u][j];
                path[j]=u;
            }
    }
}

void printfPath(int u,int v,int path[][max],int A[][max])
{
    if(A[u][v]==INF)
        cout<<"NONE"<<endl;
    else
    {
        if(path[u][v]==-1)
            直接输出边<u,v>;
        else
        {
            mid=path[u][v];
            printfPath(u,mid,A);
            printfPath(mid,v,A);
        }
    }
}

void Floyd(MGraph *g,int Path[][maxSize],int A[][maxSize])
{
    int j,k,i;
    for(i=0;i<g->n;++i)
    {
        for(j=0;j<g->n;++j)
        {
            Path[i][j]=-1;
            A[i][j]=g->edges[i][j];
        }
    }
    for(k=0;k<g->n;++k)
        for(i=0;i<g->n;++i)
            for(j=0;j<g->n;++j)
                if(A[i][j]>A[i][k]+A[k][j])
                {
                    A[i][j]=A[i][k]+A[k][j];
                    Path[i][j]=k;
                }
}

六、拓扑排序

1、AOV网（Activity On Vertex network）

     以顶点表示活动，以边表示活动的先后次序且没有回路的有向图。

2、拓扑排序核心算法（时间复杂度O(n+e））

（1）对邻接表表头结构定义修改，加上一个统计结点入度的计数器

typedef struct
{
    char data;
    int count;
    ArcNode *firstarc;
}VNode;

（2）拓扑排序的代码如下

int topsort(AGraph*G)    //用邻接表，因为邻接表很容易查到顶点引出的边
{
    int i,j,n=0;
    int stack[maxSize];int top=-1;    //定义并初始化栈
    ArcNode *p;
    for(i=0;i<G->n;++i)    //这个循环将图中所有入度为0的顶点入栈
    {
        if(G->adjlist[i].count==0)
            stack[++top]=i;
    }
/*关键操作开始*/
    while(top!=-1)    //栈中的元素逐个出栈
    {
        i=stack[top--];
        ++n;
        cout<<"i"<<" ";    //输出拓扑序列
        p=G->adjlist[i].firstarc;
        while(p!=NULL)    //这个循环实现了将所有由顶点引出的边所指向的顶点的入度减一，并将这个过程中入度变成0的顶点入栈
        {
            j=p->adjvex;
            --G->adjlist[j].count;
            if(G->adjlist[j].count==0)
                stack[++top]=j;
            p=p->nextarc;
        }
    }
    if(n==G->n)
        return 1;
    else
        return 0;
}

注意：

（1）拓扑排序序列可能不唯一；

（2）若AOV网中考察各顶点的出度并以下列步骤进行排序，则将这种排序称为逆拓扑排序，输出的结果称为逆拓扑有序序列

        ①在网中选择一个没有后继的顶点（出度为0）输出

        ②在网中删除该顶点，并删除所有到达该顶点的边

        ③重复上述两部，直到AOV网中已无出度为0的顶点为止

（3）当图中无环的时候，还可以采用DFS的方法进行拓扑排序，由于图中无环，当由图中某顶点出发进行深度优先遍历时，最先退出算法的顶点为出度为0的顶点，他是拓扑有序序列中的最后一个顶点，因此，按照DFS算法的先后次序记录下的顶点序列即为逆向的拓扑有序序列

（4）拓扑排序算法的时间复杂度为O(n+e)，每个顶点都入栈一次，每条边都被删除一次

七、关键路径

1、AOE网（Activity On Edge network）

    活动在边上的网：边表示活动，有权值。顶点表示事件，事件是图中新活动开始或者旧活动结束的标志。

    对于一个工程的AOE网，只有一个入度为0的顶点（源点）表示工程的开始，一个出度为0的顶点（汇点），表示工程的结束。

2、关键路径核心算法

    在AOE网中，从源点到汇点的所有路径中，具有最大路径长度的路径称为关键路径。完成整个工期的最短时间就是关键路径长度所代表的时间，关键路径上的活动称为关键活动。

    关键路径的概念代表了一个最长（图中最长路径），一个最短（工程要完成需要的最短时间）

3、手工求解关键路径的一般方法

（1）根据图求出拓扑有序序列a和逆拓扑有序序列b

（2）根据序列a和b分别求出每个事件的最早发生时间和最迟发生时间

（3）求出每个活动的最早发生时间和最迟发生时间

（4）最早发生时间和最迟发生时间相同的活动即为关键活动，关键活动所连成的路径即为关键路径 

王道补充

有向无环图DAG可以用来描述含有公共子式的表达式

第八章 排序

一、插入排序

1、直接插入排序

①执行流程

②算法思想

void InsertSort(int R[],int n)
{
    int i,j;    //两层循环
    int temp;        //暂存当前的待排元素
    for(i=1;i<n;++i)    //对每个元素
    {
        temp=R[i];       //暂存当前待排元素，防止元素被覆盖
        j=i-1;
    /*这个循环完成了从待排关键字之前的关键字开始扫描，如果大于待排关键字，则后移一位*/
        while(j>=0&&temp<R[j])    //比当前元素大的元素后移
        {
            R[j+1]=R[j];
            --j;
        }
        R[j+1]=temp;
    }
}

③算法复杂度分析

Ⅰ时间复杂度

    最坏O(n²）；最好O(n)；平均O(n²)

Ⅱ空间复杂度

       O(1)

2、折半插入排序

①执行流程

②算法思想

    只是在查找插入位置的时候使用了二分法来比较，移动元素的次数还是不变的，所以最坏的时间复杂度还是n²

③算法复杂度分析

Ⅰ时间复杂度

    最好情况O(nlogn) 最坏情况O(n²)

Ⅱ空间复杂度

O(1)

3、希尔排序

①执行流程

②算法思想

    缩小增量排序。增量序列的选择影响着排序算法的效率。

void ShellSort(int R[],int n)
{
    int i,j,gap;
    int temp;
    for(gap=n/2;gap>0;gap=gap/2)    //对每一组增量进行操作，直到增量减小为1
    {
        for(i=gap;i<n;++i)    //对每一个分组的第二个元素开始进行插入排序
        {            //第一个元素认为是有序的了,是分组进行的先第一组，然后第二组*/
            temp=R[i];//先暂存序列的第一个元素因为要为这个元素找到合适的位置插入；
            for(j=i;j>=gap&&R[j-gap]>R[j];j-=gap)    //比较待排元素i元素前面的
                                        //元素值是不是比i位置的小，注意这里的步长是gap
                R[j]=R[j-gap];    //把数值更大的往后移，因为用temp暂存了初始j（即i）位置上的值，所以覆盖掉也没关系
            R[j]=temp;    //把temp即待插入的元素插入到循环跳出（即要么j<gap,已经没有
                          //元素可比或前面的有序序列中已经前面的比后面的小
        }
    }
}

③算法复杂度分析

    算法复杂度与增量的选取有关

    希尔排序增量的选取应该注意的地方：

        ①增量序列的最后一个值一定取1

        ②增量序列中的值应尽量没有除1以外的公因子（即要互质）

Ⅰ时间复杂度

    eg.n/2、n/4、...2、1：复杂度O(n²)

    eg.帕培尔诺夫和斯塔舍维奇提出的2^k-1、...、65、33、17、9、5、3、1：复杂度O(n^1.5)

Ⅱ空间复杂度 

    O(1)

二、选择排序

1、简单选择排序

①执行流程

②算法思想：从头到尾扫描序列，找出最小的关键字和第一个关键字交换；在剩下的关键字中反复进行这种选择和交换。

viod SelectSort(int R[],int n)
{
    int i,j,k;
    int temp;
    for(i=0;i<n;++i)
    {
        k=i;
        for(j=i+1;j<n;++j)
            if(R[j]<R[k])
                k=j;        //找出了序列中的最小值是第k个元素
        temp=R[i];
        R[i]=R[k];
        R[k]=temp;
    }
}

③算法复杂度分析

Ⅰ时间复杂度

    没有好坏，一定是两层循环O(n²)

Ⅱ空间复杂度

    o(1)

2、堆排序

（1）堆

    ①堆的逻辑结构：是一个完全二叉树，它的任何一个非叶子结点的值都不大于（或不小于）其左右孩子结点的值。根据父结点的是大还是小，可以分成最大堆（大顶堆）、最小堆（小顶堆）。

    ②堆的存储结构：用一个顺序数组来存储，父结点位置为i时，左孩子结点位置为2i+1,右孩子结点位置为2i+2（结点下标在数组中从0开始；如果从1开始，就是2i和2i+!）最后一个非叶结点的编号为[n/2」-1（向下取整）

    ③建堆

    ④插入节点

    ⑤删除结点：删掉头结点，然后用最后一个结点A替代头结点，对A进行调整

    ⑥时间复杂度O(h)是堆的高度！

（2）堆排序

①调整函数

/*这个函数是调整堆成为一个最大堆的函数*/
void Shift(int R[],int low,int high)//这里规定数组下标从1开始
{
    int i=low,j=2*i;    //R[j]是R[i]的孩子结点
    int temp=R[i];    //待调整的结点
    while(j<=high)
    {
        if(j<high&&R[j+1]>R[j])    //有右孩子并且右孩子更大
        ++j;        //使j指向两个孩子中更大的那个
        if(R[j]>temp)
        {
           R[i]=R[j];
           i=j;        //换完之后必须向下走，看看下面是不是又有要调整的地方。
           j=2*i;
        }
        else
           break;
    }
    R[i]=temp;        //被调整结点的值放入最终位置
}

②堆排序函数

/*这个函数是堆排序函数*/
void heapSort(int R[],int n)    //根据最大堆进行排序的代码
{
    int i;
    int temp;
    for(i=n/2;i>=1;--i)
        Shift(R,i,n);
    for(i=n;i>=2;--i)    //只需要进行n-1次循环即可，最后一个不用再排
    {
        temp=R[1];
        R[1]=R[i];
        R[i]=temp;
        Shift(R,1,n-1);
    }
} 

（3）算法性能分析

    ①时间复杂度：O(nlogn) 

    ②空间复杂度：O(1)

三、交换排序

1、冒泡排序

①执行流程

②算法思想：若前面的数比后面的大，就进行一次交换；每一趟排序都是最大的那个数被排到了尾部。

void BubbleSort(int R[],int n)
{
    int i,j,flag;
    int temp;
    for(i=n-1;i>=1;--i)    //每次排序前i个元素，因为后面的元素已经有序啦
    {
        flag=0;    //这一句初始化的定义不可以放到循环外面！！！ 
        for(j=0;j<i;++j)
        {
            if(R[j]<R[j+1])
            {
                temp=R[j+1];
                R[j+1]=R[j];
                R[j]=temp;
                flag=1;
            }
        }
        if(flag==0)
            return;    //表示没有发生关键字交换，即序列已经是有序的了
    }
}

③算法复杂度分析

Ⅰ时间复杂度

    最好情况：本来就是有序，只扫描了一趟，比较了一趟O(n)，否则O(n²)

Ⅱ空间复杂度

    O(1)

2、快速排序

①算法概述

分而治之：选一个主元，分成两大块（一块大于主元，一块小于主元），递归地处理两块的数据。处理时候的排序是通过“交换”来实现的，交换的是i和j的位置，不是相邻的元素，所以一次可能消除多对逆序对，并且经过一趟排序以后，主元的位置就是它最后在有序序列中的位置，不用再移动了。

void quickSort(int R[],int low,int high)
{
    int i=low,j=high;    //low和high作为传参是全局变量，定义i，j做函数内的循环变量
    int temp;
    while(low<high)    //递归函数的出口，当待排序列等于一时就退出递归
    {
        temp=R[low];    //这里选取第一个元素为主元，暂存他的值
        while(i<j)    //i<j时，进行i、j指针的移动和元素比较
        {
            while(i<j&&R[j]>=temp)
                --j;    //j顺次前移，直到找到比主元小的值（非正常）
            if(i<j)
            {
                R[i]=R[j];    //把找到的这个比主元小的值换到i的位置（即左边
                i++;    //i就往右边再移一位
            }
            while(i<j&&R[i]<=temp)
                ++i;    //i顺次后移，直到找到比主元temp大的值（非正常）
            if(i<j)
            {
                R[j]=R[i];    //把找到的这个比主元大的值换到左边（即刚刚非正常的j的位置
                --j;
            }
        }
        R[i]=temp;    //把temp放在排好序的地方。
        quickSort(R,low,i-1);    //递归
        quickSort(R,i+1,high);
        }
    }
}

②关键细节

Ⅰ.选主元:eg.取头、中、尾的中位数

③适用于大规模的数据 

④算法复杂度分析

Ⅰ时间复杂度

    最好情况O(nlogn) 最坏情况O(n²)

Ⅱ空间复杂度

    因为是递归的，所以占用了系统栈：O(log₂n)

四、归并排序（稳定） NlogN 

（1）有序子列的归并

五、基数排序

（1）桶排序

（2）基数排序（进制的基数）

①次位优先LSD（可以实现从小到大的排序）；

    主位优先MSD

②多关键字的排序

eg：把次关键字看作是个位，主关键字看作是更高位

次位优先，先按照个位数放进桶里，再按照十位数放进桶里，最后就是有序的

另：表排序；复杂度分析 

物理排序：N个数字的排列由若干独立的环组成；所以可以对每个环进行操作。判断table[i]=i是，环结束

                复杂度：最坏T=（mN），m是每个元素的复制时间。

六、外部排序

1、概念与流程

（1）基本概念：对外存中的记录进行排序（外存中记录的规模太大了），将内存作为工作空间来辅助外存数据的排序。

（2）流程解析：归并排序

    k路归并：假设待排序的序列有n个记录，把它分成m个规模比较小的记录段（记录段的长度不一定相同），然后每k个记录段为一组（一共m/k组），进行k路归并排序。然后得到m/k组有序的记录段，再按照每k个为一组，进行k路归并排序，直到排序完成。用了k个内存空间。（若k=2，就是二路归并排序啦）

（3）重要子算法

    1）置换-选择排序

        ①概念：适用于初始归并段规模、高效、不受内存空间限制的排序算法。

        ②算法思想、操作流程：根据缓存区的大小，从外存读入记录；（eg.缓存区的大小是4,那就先读入4个记录）

            然后从缓存区中选出一个最小的输出（假设要进行升序排序）写回外存，用下一个记录替代这条记录，输出的部分就是当前生成的归并段的一部分（需要注意的是，归并段应该是递增的）

            因此，如果新输入的记录比现在输出生成的归并段的最大值要小的话，就不能输出，要选第二小的输出，如果还是小，选第三小的，以此类推重复进行上述操作

            直到缓冲区的所有元素都比归并段的最大值小，那么这一段归并段生成完毕，开始生成下一段归并段。

        ③注意：限制排序算法的内存空间，就是指这里的缓冲区。

                      由上述算法不难发现，得到的归并段的长度不一定相同，再用最佳归并树来让归并操作的次数最少。

     2）最佳归并树

        ①概念：每个记录在每趟归并中需要两次I/O操作（读一次，写一次），读写操作是很慢的，因此尽可能的减少归 并  次数可以有效的提高排序的速度。这里用到的用来减少归并次数的数据结构是“最佳归并树”。

        ②算法思想、操作流程：

            树的结点代表当前归并段的长度；树的带权路径长度的两倍就是整个归并操作需要的I/O次数；对于初始归并段，其结点的路径长度就等于其参加归并的次数。

            因此，为了使I/O操作最少，要生成最佳归并树，可以用赫夫曼树的构造方法。对于k路归并算法，构造k叉赫夫曼树。

    3）败者树

        ①概念：用来在当前的k个值中选出最值，败者树可以提高这一过程的效率；是选择树（类似于堆）

        ②算法思想、操作流程：

            A.建立败者树    （时间复杂度是k）

                Ⅰ.用每个结点的编号值作为他的父结点，构成了k个树，再把这些树合并；

                Ⅱ.合并的规则（以构建最小值败者树为例：关键值大的是败者）：比较序号所指的关键字的大小，然后以败者的序号为根节点组成新树，胜者的序号作为这棵新树的父结点。以此类推，当所有结点都并入树中的时候，树的根结点指的记录值是最小的。

                Ⅲ.需要注意的是，这里是以序号为根节点来建立败者树的，不是用记录值。

            B.调整败者树    （时间复杂度只有树的高度，即log

                Ⅰ.就是局部重新构造败者树的过程，所以时间复杂度只有树的高度；

败者树中含有两种不同类型的结点

第一种：叶子结点，其值为从当前参与归并的归并段中读入的段首记录。叶子结点的个数为当前参与归并的归并段数，即k路归并叶子数为k

第二种：非叶结点，都是度为2的结点，其值为叶子结点的序号，同时也指示了当前参与选择的记录所在的归并段

由序号构造结点的好处是不仅可以找到记录值，还可以找到其所在的归并段，以便下一个记录读入内存取代刚选出的值

外部排序的归并排序有两个基本阶段，分别是生成初始归并段和从归并序列中选出最小值；m个归并段进行k路归并需要的归并趟数是[log_km]向上取整

k路归并败者树高度为[logk]+1因此利用败者树从k个记录里选出最值需要进行[log2k]次比较，即时间复杂度是O(log2k)，k路归并败者树的时间复杂度为O(klog2k)

七、排序算法的比较

复杂的排序算法	最好时间复杂度	平均时间复杂度	最坏时间复杂度	空间复杂度	稳定性
希尔排序（插入排序）		O(nlog2n)			不稳定
堆排序	O(nlog2n)	O(nlog2n)	O(nlog2n)		不稳定
归并排序	O(nlog2n)	O(nlog2n)	O(nlog2n)	O(n)
快速排序	O(nlog2n)	O(nlog2n)	O(n2)	O(log2n)	不稳定
基数排序		O(d(n+rd))		O(rd)
简单的排序算法
插入类排序 直接插入排序	O(n)	O(n2)
交换类排序 冒泡排序	O(n)	O(n2)
选择类排序 简单选择排序		O(n2)			不稳定

快希归堆是平均时间复杂度为nlogn

快希选堆是不稳定的排序算法

经过一趟排序，能够保证一个关键字达到了最终的位置：交换类：起泡排序，快速排序；选择类：简单选择，堆排序

关键字比较次数与原始序列无关：简单选择排序，折半插入排序

排序算法的排序趟数与原始序列有关：交换类的排序

借助于“比较”进行排序的算法，在最坏情况下的时间复杂度至少为O(nlog₂n)

选择排序算法小结

（1）若待排元素数目较少，则可以用简单选择排序/直接插入排序

（2）若文件的初始状态已按关键字基本有序，则选用直接插入排序/冒泡排序

（3）若待排元素n较大，则应采用时间复杂度为O(nlog₂n)的 快、希、归、堆；堆排序需要的辅助空间少于快速排序，且不会出现快速排序可能出现的最坏情况；

若又要求采用稳定的时间复杂度为O(nlog₂n)的排序，则只能用归并排序；可以先用直接插入排序求得较长的有序子文件，再两两归并，直接从单个记录开始进行两两归并的而算法不是很好

（4）基于比较的排序方法中，每次比较两个关键字的大小之后，仅出现两种可能的转移，因此可以用一棵二叉树来描述比较判定过程，由此可以证明，当文件的n个关键字随机分布时，任何借助于“比较”的排序算法，至少需要O(nlog2n)的时间

（5）若待排元素的数目n很大，记录的关键字位数较少且可以分解时，采用基数排序好

（6）当记录本身信息量较大时，为避免耗费大量时间移动记录，可用链表作为存储结构

int Search(int R[],int n,int key)    //一维数组进行查找
{
    int i;
    for(i=0;i<n;++i)
        if(intR[i]==key)
            return i;
    return 0;
}
LNode *Search(LNode *head,int key)    //基于链表的查找
{
    LNode*p=head;
    while(p!=NULL)
    {
        if(p->data==key)
            return p;
        else
            p=p->next;
    }
    return NULL;
}

int Bsearch(int R[],int low,int high,int key)
{
    int mid;
    while(low<=high)    //子表长度大于等于1的时候进行循环
    {
        mid=(low+high)/2;
        if(R[mid]==key)
            return mid;
        else if(R[mid]>key)
            high=mid-1;
        else
            low=mid+1;
    }
    return -1;
}

typedef struct    //结构体定义
{
    int key;
    int low,high;
}indexElem;
indexElem index[maxSize];

typedef struct BTNode
{
    int key;    //这里把data改成了key，表示关键字
    struct BTNode*lchild;
    struct BTNode*rchild;
}BTNode；

（2）基本算法（查找，插入，构造，删除） 

/*BTNode*BSTSearch(BTNode*bt,int key)
{
    BTNode*p=head;
    while(p!=NULL)
    {
        if(p->key==key)
            return p;
        else if(p->key>key)
            p=p->lchild;
        else
            p=p->rchile;
    }
    return NULL;
}*/    //不知对错？？？？？？对啦！！！！！！！！！！好牛牛！！！！但不怎么考，常考是下面的递归

BTNode*BSTSearch(BTNode *bt,int key)
{
    if(bt==NULL)
        return NULL;
    else
    {
        if(bt->key==key)
            return bt;
        else if(key<bt->key)
            return BSTSearch(bt->lchild,key);    //因为是递归地，所以必须逐层的返回值给上一层
        else
            return BSTSearch(bt->rchile,key);
    }
}

int BSTInsert(BTNode *&bt,int key)    //这里的要用引用型！
{
    if(bt==NULL)
    {
        bt=(BTNode*)malloc(sizeof(BTNode));
        bt->key=key;
        bt->lchild=rchild=NULL;
        return 1;
    }
    else
    {
        if(bt->key==key)
            return 0;
        else if(bt->key>key)
            return BSTInsert(bt->lchild,key);
        else
            return BSTInsert(bt->rchild,key);
        }
}

void CreateBST(BTNode*&bt,int key[],int n)
{
    int i;
    bt=NULL;
    for(i=0;i<n;++i)
        BSTInsert(bt,key[i]);
}

（2）平衡二叉树的建立