线性表

顺序表

定义

//静态分配
#define MaxSize 50 //最大长度
typedef struct {
    ElemType data[MaxSize];//元素
    int length;//长度
}SqList;

//动态分配
#define InitSize 100 //表长度初始定义
typedef struct{
    ElemType *data;
    int MaxSize,length;
}SeqList;
//初始动态分配
L.data=(ElemType *)malloc(sizeof(InitSize));

动态分配不是链式存储，它同样也是顺序存储，物理结构没有发生变化，依然是随机存取。

基本操作

//线性表的基本操作
InitList(&L);//初始化表，构造一个空表
Length(L);//求表长，返回L的长度
LocateElem(L,e);//按值查找操作
GetElem(L,i);//按位查找，获取第i个位置的元素值
ListInsert(&L,i,e);//插入操作，在L的第i个位置插入指定元素e
ListDelete(&L,i,&e);//删除操作，删除第i个位置上元素,并用e返回删除元素值
PrintList(L);//输出操作
Empty(L);//判空操作
DestroyList(&L);//销毁操作，释放占用内存空间

链表

单链表结点定义

typedef struct LNode{
    ElemType data;//数据域
    struct LNode *next;//指针域
}LNode,*LinkList;

双链表结点定义

typedef struct DLNode{
    ElemType data;
    struct DLNode *prior;//指向前驱结点
    struct DLNode *next;//指向后继结点
}DLNode,*DLinkList;

单链表基本操作

建立单链表

//头插法建立单链表,逆向建立单链表
LinkList List_HeadInsert(LinkList &L){
    LNode *s;
    int x;
    L=(LinkList)malloc(sizeof(LNode));//创建头结点
    L->next=NULL;
    scanf("%d",&x);
    while(x!=111111){
        s=(LNode*)maloc(sizeof(LNode));//创建新结点
        s->data=x;
        s->next=L->next;//每次将新结点插入到头结点后面
        L->next=s;
        scanf("%d",&x);
    }
    return L;
}

//尾插法建立单链表,正向建立单链表
LinkList List_TailInsert(LinkList &L){
    int x;
    L=(LinkList)malloc(sizeof(LNode));
    LNode *s,*r=L;
    scanf("%d",&x);
    while(x!=1111){
        s=(LNode*)malloc(sizeof(LNode));
        s->data=x;
        r->next=s;
        r=s;
        scanf("%d",&x);
    }
    r->next=NULL;//尾结点指针置空
    return L;
}

按序号查找结点值

LNode *GetElem(LinkList L,int i){
    int count=1;
    LNode *p=L->next;
    if(i==0)
        return L;
    if(i<1)
        return NULL;
    while(p&&count<i){
        p=p->next;
        count++;
    }
    return p;
}

按值查找表结点

LNode *LocateElem(LinkList L,ElemType e){
    LNode *p=L->next;
    while(p->data!=e&&p!=NULL)
        p=p->next;
    return p;
}

前插结点

p=GetElem(L,i-1);
s->next=p->next;
p->next=s;

后插操作实现结点的前插

//将*s结点插入到*p结点之前
s->next=p->next;
p->next=s;
temp=p->data;
p->data=s->data;
s->data=temp;

删除结点

//找前驱实现删除结点
p=GetElem(L,i-1);
q=p->next;//q指向被删除结点
p->next=q->next;
free(q);
//通过删除后继来删除结点
q=p->next;
p->data=q->data;//与后继结点交换数据域
p->next=q->next;
free(q);

双链表

尾插法建立双链表

void createDLinkList(DLinkList &L){
    DLNode *s,*r;
    int x;
    L=(DLinkList)malloc(sizeof(DLNode));
    L->prior=NULL;
    L->next=NULL;
    r=L;
    scanf("%d",&x);
    while(x!=1111){
        s=(DLNode*)malloc(sizeof(DLNode));
        s->data=x;
        r->next=s;
        s->prior=r;
        r=s;
        scanf("%d",&x);
    }
    r->next=NULL;
    return L;
}

双链表按值找结点

DLNode *find_x(DLinkList L,ElemType x){
    DLNode *p=L->next;
    while(p!=NULL){
        if(p->data==x)
            break;
        p=p->next;
    }
    return p;
}

双链表插入结点

//p结点之后插入s
s->next=p->next;
s->prior=p;
p->next=s;
s->next->prior=s;

双链表删除结点

//删除p结点的后继结点
q=p->next;
p->next=q->next;
q->next->prior=p;
free(q);

循环链表

循环单链表和单链表区别:最后一个结点的指针不是NULL,而改为指向头结点;
循环双链表,头结点的prior指针还要指向表尾结点

静态链表

借助数组来描述线性表的链式存储,结点也有数据域和指针域.这里的指针是结点的相对地址(数组下标),又称游标,以next==-1作为结束的标志

#define MaxSize 50
typedef struct{
    ElemType data;//
    int next;//下一个元素的数组下标
}SLinkList[MaxSize];

栈

栈和队列是受限的线性表。（不可以随便读取栈或队列中间的某个数据）

栈的基本操作

入栈：先移动指针，再进栈。Stack[++top]=x
出栈：先取出元素，再移动指针。x=Stack[top—];

InitStack(&S);//初始化一个空栈,S.top=-1;
StackEmpty(S);//判栈空
Push(&S,x);//进栈,将x加入栈顶（栈未满情况下）
Pop(&S,&x);//出栈,弹出栈顶元素，并用x返回（栈非空的情况下）
GetTop(S,&x);//读栈顶元素，并用x返回（栈非空情况下）
DestoryStack(&S);//销毁栈，并释放栈S占用的存储空间

顺序栈

#define MaxSize 50
typedef struct{
    ElemType data[MaxSize];//存放栈中元素
    int top;//栈顶指针
}SqStack;

链栈

typedef struct Linknode{
    ElemType data;//数据域
    struct Linknode *next;//指针域
}*LiStack;

队列(Queue)

队列的基本操作

InitQueue(&Q);//初始化队列，构造一个空队列Q
QueueEmpty(Q);//判队列空
EnQueue(&Q,x);//入队,队列未满则将x加入队尾
DeQueue(&Q,&x);//出队，队列非空，删除队头元素，并用x返回
GetHead(Q,&x);//读队头元素，若队列非空将队头元素赋值给x

顺序队列

#define MaxSize 50//队列中最大元素个数
typedef struct {
    ElemType data[MaxSize];
    int front,rear;//队头指针和队尾指针
}SqQueue;

初始状态（队空条件）：Q.front==Q.rear==0
进队操作：先送值到队尾，再将队尾指针加1
出队操作：先取队头元素，再将队头指针加1

循环队列的基本操作

初始化：Q.front=Q.rear=0
队空：Q.front=Q.rear
队满：（Q.rear+1）%MaxSize==Q.front
入队：Q.data[Q.rear]=x;Q.rear=(Q.rear+1)%MaxSize;
出队：x=Q.data[Q.front];Q.front=(Q.front+1)%MaxSize;

链式队列

typedef struct{//链式队列结点
    ElemType data;
    struct LinkNode *next;
}LinkNode;
typedef struct{//链式队列
    LinkNode *front,*rear;
}LinkQuene;

队空：Q.rear==NULL或者Q.front==NULL
入队:Q->rear->next=p;Q->rear=p;
出队：p=Q->front;Q->front=p->next;x=p->data;free(p);

串

串的基本操作

StrAssign(&T,chars);//赋值操作。把串T赋值为chars。
StrCopy(&T,S);//复制操作。由串S复制得到串T。
StrEmpty(S);//判空操作。若S为空串，则返回TRUE，否则返回FALSE。
StrLength(S);//求串长。返回串S的元素个数。
ClearString(&S);//清空操作。将S清为空串。
DestroyString(&S);//销毁串。将串S销毁（回收存储空间）。
Concat(&T,S1,S2);//串联接。用T返回由S1和S2联接而成的新串
SubString(&Sub,S,pos,len);//求子串。用Sub返回串S的第pos个字符起长度为len的子串。
Index(S,T);//定位操作。若主串S中存在与串T值相同的子串，则返回它在主串S中第一次出现的位置；否则函数值为0。
StrCompare(S,T);//比较操作。若S>T，则返回值>0；若S=T，则返回值=0；若S<T，则返回值<0。

定长顺序存储表示

#define MAXLEN 255
typedef struct{
    char ch[MAXLEN];
    int length;
}SString;

变长顺序存储（堆分配存储表示）

typedef struct{
    char *ch;
    int length;
}HString;

串的模式匹配

子串的定位操作通常称为串的模式匹配，求的是子串（模式串）在主串中的位置

简单模式匹配（主串回溯）

int Index(SString S,SString T){
    int i=1,j=1,k=i;//k记录检查子串的起始位置
    while(i<=S.length&&j<=T.length){
        if(S.ch[i]==T.ch[j]){
            ++i;
            ++j;
        }
        else{
            i=++k;//匹配失败,从主串的下一位置开始匹配
            j=1;
        }
    }
    if(j>T.length)
        return k;
    else
        return 0;
}

KMP算法（主串不回溯）

next[j]的含义是：在子串的第j个字符与主串发生失配时，则跳到子串的next[j]位置重新与主串当前位置进行比较;next[1]=0,next[2]=1;

//求next值
void get_next(String T,int next[]){
    int i=1,j=0;
    next[1]=0;
    while(i<T.length){
        if(j==0||T.ch[i]==T.ch[j]){
            ++i;
            ++j;
            next[i]=j;
        }
        else
            j=next[j];
    }
}
//KMP算法
int Index_KMP(String S,String T,int next[]){
    int i=1,j=1;
    while(i<=S.length&&j<=T.length){
        if(j==0||S.ch[i]==T.ch[j]){
            ++i;
            ++j;
        }
        else
            j=next[j];
    }
    if(j>T.length)
        return i-T.length;
    else
        return 0;
}
//KMP算法改进,修正next数组，使用nextval数组
void get_nextval(String T,int nextval[]){
    int i=1,j=0;
    nextval[i]=0;
    while(i<T.length){
        if(j==0||T.ch[i]==T.ch[j]){
            ++i;
            ++j;
            if(T.ch[i]!=T.ch[j])
                nextval[i]=j;
            else
                nextval[i]=nextval[j];
        }
        else
            j=nextval[j];
    }
}

树与二叉树（非常非常重要）

二叉树的链式存储

typedef struct BiTNode{
    ElemType data;
    struct BiTNode *lchild,*rchild;//左右孩子指针
}BiTNode,*BiTree;

线索二叉树的存储结构

ltag==0,表示lchild指向的是结点的左孩子，ltag==1,表示lchild指向的是结点的前驱；
rtag==0,表示rchild指向的是结点的右孩子，rtag==1,表示rchild指向的是结点的后继.

typedef struct ThreadNode{
    ElemType data;
    struct ThreadNode *lchild,*rchild;
    int ltag,rtag;//左右线索标志
}ThreadNode,*ThreadTree;

树的存储结构

双亲表示法

#define MAX_Tree_Size 100
typedef struct{
    ElemType data;
    int parent;//双亲位置域
}PTNode;
typedef struct{
    PTNode nodes[MAX_Tree_Size];//双亲表示
    int n;//结点数
}PTree;

孩子兄弟表示法

typedef struct CSNode{
    ElemType data;
    struct CSNode *firstchild,*nextsibing;//第一个孩子和右兄弟指针
}CSNode,*CSTree;

*并查集存储结构和基本操作

通常用树或森林的双亲表示作为并查集的存储结构，每个子集合以一棵树表示。所有表示子集合的树，构成全集合的森林，存放在双亲表示数组内。通常用数组元素的下标代表元素名，用根结点的下标代表子集合名，根结点的双亲结点为负数。

#define SIZE 100
int UFSets[SIZE];//集合元素数组（双亲指针数组）
//初始化,S即为并查集
void Initial(int S[]){
    for(int i=0;i<SIZE;i++)
        s[i]=-1;
}
//Find操作（在并查集S中查找并返回包含元素x的根）
int Find(int S[],int x){
    while(S[x]>=0)
        x=S[x];
    return x;//根的S[]小于0
}
//Union操作（求两个不相交子集合的并集）
void Union(int S[],int Root1,int Root2){
    //要求Root1和Root2是不同的，且表示子集合的名字
    S[Root2]=Root1;    //将根Root2链接到另一根Root1下面
}

二叉树的遍历

先序遍历

根结点——>左子树——>右子树

递归

void PreOrder(BiTree T){
    if(T!=NULL){
        visit(T);
        PreOrder(T->lchild);
        PreOrder(T->rchild);
    }
}

非递归

void PreOrder(BiTNode *bt){
    if(bt!=NULL){
        BiTNode *Stack[maxsize];//定义一个栈
        int top=-1;
        BiTNode *p;
        Stack[++top]=bt;//根结点入栈
        while(top!=-1){
            p=Stack[top--];
            visit(p);
            if(p->rchild!=NULL)//注意让右孩子先入栈
                Stack[++top]=p->rchild;
            if(p->lchild!=NULL)
                Stack[++top]=p->lchild;
        }
    }
}

中序遍历

递归

void InOrder(BiTree T){
    if(T!=NULL){
        InOrder(T->lchild);
        visit(T);
        InOrder(T->rchild);
    }
}

非递归

void InOrder(BiTNode *bt){
    if(bt!=NULL){
        BiTNode *Stack[maxsize];
        int top=-1;
        BiTNode *p;
        p=bt;
        while(top!=-1||p!=NULL){
            while(p!=NULL){
                Stack[++top]=p;
                p=p->lchild;
            }
            if(top!=-1){
                p=Stack[top--];
                visit(p);
                p=p->rchild;
            }
        }
    }
}

后序遍历

递归

void PostOrder(BiTree T){
    if(T!=NULL){
        PostOrder(T->lchild);
        PostOrder(T->rchild);
        visit(T);
    }
}

非递归

//两个栈实现
void PostOrder(BiTNode *bt){
    if(bt!=NULL){
        BiTNode *Stack1[maxsize];
        int top=-1;
        BiTNode *Stack2[maxsize];
        int top2=-1;
        BiTNode *p=NULL;
        Stack1[++top1]=bt;
        while(top1!=-1){
            p=Stack1[top1--];
            Stack2[++top2]=p;//输出改为入Stack2
            if(p->lchild!=NULL)
                Stack1[++top1]=p->lchild;
            if(p->rchild!=NULL)
                Stack1[++top1]=p->rchild;
        }
        while(top2!=-1){
            //出栈序列即为后序遍历序列
            p=Stack2[top2--];
            visit(p);
        }
    }
}
//一个栈实现,在二叉树的存储结构中增加一个是否访问的tag域，初始为0
void PostOrder(BiTree T){
    InitStack(S);
    p=T;
    while(p||!StackEmpty(S)){
        if(p){
            Push(S,p);
            p=p->lchild;
        }
        else{
            Pop(S,p);
            if(p->rchild&&(p->rchild).tag==0){
                Push(S,p);
                p=p->rchild;
            }
            else{
                visit(p);
                p.tag=1;
                p=NULL;
            }
        }
    }
}

层次遍历

借助队列

void LevelOrder(BiTree T){
    InitQueue(Q);
    BiTree p;
    EnQueue(Q,T);
    while(isEmpty(Q)){
        DeQueue(Q,p);
        visit(p);
        if(p->lchild!=NULL)
            EnQueue(Q,p->lchild);
        if(p->rchild!=NULL)
            EnQueue(Q,p->rchild);
    }
}
//定义循环队列，进行辅助操作
void LevelOrder(BiTNode *bt){
    int front,rear;
    BTNode *Q[maxsize];
    front=rear=0;
    BTNode *p;
    if(bt!=NULL){
        rear=(rear+1)%maxsize;
        Q[rear]=bt;
        while(front!=rear){//队列非空
            front=(front+1)%maxsize;
            p=Q[front];
            visit(p);
            if(p->lchild!=NULL){
                rear=(rear+1)%maxsize;
                Q[rear]=p->lchild;
            }
            if(p->rchild!=NULL){
                rear=(rear+1)%maxsize;
                Q[rear]=p->rchild;
            }
        }
    }
}

中序线索二叉树的构造和遍历

图(非常重要)

图的存储结构

邻接矩阵法

#define MaxVertexNum 100 //顶点数目最大值
typedef char VertexType;//顶点数据类型
typedef int EdgeType;//带权图中边上权值的数据类型
typedef struct{
    VertexType Vex[MaxVertexNum];//顶点表
    EdgeType Edge[MaxVertexNum][MaxVertexNum];//邻接矩阵，边表
    int vexnum,arcnum;//当前顶点数和弧数
}MGraph;

邻接表法

#define MaxVertexNum 100 
typedef struct ArcNode{    //边表结点
    int adjvex;//该弧所指向顶点的位置
    struct ArcNode *next;//指向下一条弧的指针
    InfoType info;//网的边权值
}ArcNode;
 typedef struct VNode{    //    顶点表结点
     VertexType data;//顶点信息
     ArcNode *first;//指向第一条依附该顶点的弧的指针
 }VNode,AdjList[MaxVertexNum];
typedef struct{
    AdjList vertices;//邻接表
    int vexnum,arcnum;//图的顶点数和弧数
}ALGraph;

图的基本操作

Adjacent(G,x,y);//判断图G是否存在边<x,y>
Neighbors(G,x);//列出G中与结点x邻接的边
InsertVertex(G,x);//在G中插入顶点x
DeleteVertex(G,x);//从G中删除顶点x
AddEdge(G,x,y);//向图G中添加<x,y>这条边
RemoveEdge(G,x,y);//从图G中删除<x,y>这条边
FirstNeighbor(G,x);//求G中顶点x的第一个邻接点，若有则返回顶点号，否则返回-1
NextNeighbor(G,x,y);//返回除y后顶点x的下一个邻接点，若y是x的最后一个邻接点则返回-1
Get_edge_value(G,x,y);//获取G中边<x,y>的权值
Set_edge_value(G,x,y,v);//设置G中边<x,y>对应的权值为v

图的遍历

广度优先搜索

bool visited[Max_Vertex_Num];//访问标记数组
LinkQueue q;
void BFSTrave(Graph G){
    for(int i = 0; i < G.vexnum;++i){
        visited[i] = false;    //访问标记数组初始化        
    }
    InitQueue(q);    //初始化辅助队列Q
    for(int i = 0; i < G.vexnum; i++){    //从0个顶点开始遍历 
        if(!visited[i])    //对每个连通分量调用一次BFS 
            BFS(G,i);    //vi未访问过，从vi开始BFS 
    } 
}
void BFS(Graph G,int v){    //从顶点v出发，广度优先遍历G 
    visit(v);    //访问初始顶点v 
    visited[v] = true;    //对v做已访问标记
    EnQueue(q,v);    //顶点v入队列q 
    while(!isEmpty(q)){
        DeQueue(q,v);    //顶点v出队列q
        for(int w = FirstNeighbor(G,v); w >= 0; w = NextNeighbor(G,v,w)){
            //检测v所有邻接点
            if(!visited[w]){//w为v尚未访问的邻接顶点 
                visit(w);
                visited[w] = true;//对w做已访问标记
                EnQueue(Q,w);    //顶点w入队列 
            } 
        } 
    } 
}

深度优先搜索

bool visited[Max_Vertex_Num];
void DFSTraverse(Graph G){
    for(int v = 0; v < G.vexnum; v++){
        visited[v] = false;    //初始化已访问标记 
    }
    for(int v = 0; v <    G.vexnum; v++){
        if(!visited[v])
            DFS(G,v);
    } 
} 
void DFS(Graph G,int v){//从顶点v出发，深度优先遍历图G 
    visit(v);
    visited[v] = true;
    for(int w = FirstNeighbor(G,v); w >= 0; w = NextNeighbor(G,v,w)){
        if(!visited[w])    //w为v尚未访问的邻接顶点 
            visit(w);
            DFS(G,w);
    } 
}

图的应用

最小生成树

Prim算法

void Prim(MGraph g,int v0,int &sum){
    int lowcost[maxsize],vset[maxsize],v;
    int i,j,k,min;
    v=v0;
    for(i=0;i<g.vexnum;++i){
        lowcost[i]=g.edges[v0][i];
        vset[i]=0;
    }
    vset[i]=1;//将v0并入树中
    sum=0;//累计权值
    for(i=0;i<g.vexnum-1;++i){
        min=INF;//INF为一个已经定义的比图中所有边权值都大的常量
        //选出侯选边中的最小者
        for(j=0;j<g.vexnum;++j){
            if(vset[j]==0&&lowcost[j]<min){
                min=lowcost[j];
                k=j;
            }
            vset[k]=1;
            v=k;
           sum+=min;
            //以刚并入的顶点更新侯选边
            for(j=0;j<g.vexnum;++j){
                if(vset[j]==0&&g.edges[v][j]<lowcost[j])
                    lowcost[j]=g.edges[v][j];
            }
        }
    }

Kruskal算法

typedef struct{
    int a,b;//一条边相连的两个顶点
    int w;//边的权值
}Road;
Road road[maxsize];
int v[maxsize];//定义并查集数组
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;
    N=g.vexnum;
    E=g.arcnum;
    sum=0;
    for(i=0;i<N;++i)
        sort(road,E);//对road数组的边按权值从小到大排列
    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;
        }
    }
}

最短路径

Dijkstra算法

Floyd算法

拓扑排序

关键路径

查找

顺序查找

typedef struct{//查找表的数据结构
    ElemType *elem;//元素存储空间基址，建表时按实际长度分配，0号单元留空
    int TableLen;//表的长度
}SSTable;
//一般线性表的顺序查找
int Search_Seq(SSTable ST,ElemType key){
    ST.elem[0]=key;//哨兵
    for(i=ST.TableLen;ST.elem[i]!=key;--i);//从后往前找
    return i;//若表中不存在关键字为key的元素，将查找到i为0时退出循环
}

ASL（成功）=（n+1）/2
ASL（失败）=n+1
有序表的顺序查找：ASL（成功）=（n+1）/2；ASL（失败）=n/2+n/(n+1)；

折半查找

//仅适用于有序的顺序表
int Binary_Search(SeqList L,ElemType key){
    int low=0,high=L.TableLen-1,mid;
    while(low<=high){
        mid=(low+high)/2;
        if(L.elem[mid]==key)
            return mid;
        else if(L.elem[mid]>key)
            high=mid-1;
        else
            mid=low+1;
    }
    return -1;//查找失败返回-1
}

分块查找

typedef struct{//索引表
    ElemType maxvalue;
    int low,high;//记录某块中第一个和最后一个元素的位置
}indexElem;
indexElem index[maxsize];//定义索引表

将长度为n的查找表均匀地分为b块，每块有s个记录，在等概率情况下，若在块内和索引表中均采用顺序查找，
则平均查找长度为: ASL=L1+Ls=(b+1)/2+(s+1)/2=(s^2+2s+n)/2s;
平均查找长度最小值为n^(1/2)+1;若对索引表采用折半查找，则平均查找长度为

散列表

散列表（Hash Table），⼜称哈希表。是⼀种数据结构，特点是：数据元素的关键字与其存储地址直接相关
通过散列函数建立关键字和存储地址的关系 Addr=H(Key)。

常见的散列函数

设计目标：让不同关键字的冲突尽可能少
1.除留余数法
除留余数法 —— H(key) = key % p
2.直接定址法
H(key)=key或者H(key)=a*key+b
3.数字分析法
数字分析法 —— 选取数码分布较为均匀的若⼲位作为散列地址
4.平方取中法
平⽅取中法——取关键字的平⽅值的中间⼏位作为散列地址。

处理冲突的方法

1.拉链法
⽤拉链法（⼜称链接法、链地址法）处理“冲突”：把所有“同义词”存储在⼀个链表中
eg:假设散列表长为m，散列函数为H（K）,用链地址处理冲突。试编写输入一组关键字构造散列表的算法(2019年)

typedef struct HNode{
    int data;
    struct HNode *next;
}HNode,*Hlist;
void CreateHlist(Hlist L[],int m){
    int i,x;
    HNode *s;
    for(i=0;i<m;i++)
        L[i]=NULL;
    scanf("%d",&x);
    while(x!='#'){
        h=H(x);
        s=(HNode*)malloc(sizeof(HNode);
        s->data.key=x;
        s->next=L[h];
        L[h]=x;                 
        scanf("%d",&x);
    }   
}

其余处理冲突的方法见：https://www.yuque.com/docs/share/462a297a-7443-4e9b-9ad9-c32b07763dee?# 《散列查找》

排序

内部排序

内部排序指的是排序期间元素全部存放在内存中的排序

评价指标：1.稳定性：关键字相同的元素经过排序后相对顺序是否会发生改变
2.时间复杂度和空间复杂度

插入排序

算法思想：每次将⼀个待排序的记录按其关键字大小插入到前⾯已排好序的子序列中，直到全部记录插入完成。

直接插入排序

顺序查找找到应插入的位置，仅适用于顺序表，链表

//用哨兵
void InsertSort(ElemType A[],int n){
    int i,j;
    for(i=2;i<=n;i++){//依次将A[2]~A[n]插入到前面已排序序列
        if(A[i]<A[i-1]){//关键字小于前驱
            A[0]=A[i];//复制为哨兵
            for(j=i-1;A[0]<A[j];--j)//从后往前查找待插位置
                A[j+1]=A[j];
            A[j+1]=A[0];//复制到插入位置
        }
    }
   //不用哨兵
    void InsertSort(ElemtType A[],int n){
        int i,j,temp;
        for(i=1;i<n;i++){
            if(A[i]<A[i-1]){
                temp=A[i];
                for(j=i-1;j>=0&&A[j]>temp;--j)//检查前面已排好的序列
                    A[j+1]=A[j];
                A[j+1]=temp;
            }
        }

算法效率分析
空间复杂度：O(1)
最好时间复杂度（全部有序）：O(n)
最坏时间复杂度（全部逆序）：O(n^2)
平均时间复杂度：O(n^2)
算法稳定性：稳定

折半插入排序

思路：先⽤折半查找找到应该插⼊的位置，再移动元素

当 low>high 时折半查找停⽌，应将 [low, i-1] 内的元素全部右移，并将 A[0] 复制到 low 所指位置;
当 A[mid]==A[0] 时，为了保证算法的“稳定性”，应继续在 mid 所指位置右边寻找插⼊位置;

//折半插入排序
void InsertSort(int A[],int n){
    int i,j,low,high,mid;
    for(i=2;i<=n;i++){
        A[0]=A[i];
        low=1;
        high=i-1;
        while(low<=high){    //折半查找 默认递增有序
            mid=(low+high)/2;
            if(A[mid]>A[0])
                high=mid-1;//查找左半子表
            else low=mid+1;    //查找右半子表
        }
        for(j=i-1;j>=high+1;--j)
            A[j+1]=A[j];//统一后移元素
        A[high+1]=A[0];
    }
}

希尔排序

希尔排序：先将待排序表分割成若⼲形如 L[i, i + d, i + 2d,…, i + kd] 的“特殊”⼦表，对各个⼦表分别进⾏直接插⼊排序。缩⼩增量d，重复上述过程，直到d=1为⽌。
先追求表中元素部分有序，再逐渐逼近全局有序

//希尔排序
void ShellSort(int A[],int n){
    int d,i,j;
    //A[0]只是暂存单元，不是哨兵，当j<=0,插入位置已到
    for(d=n/2;d>=1;d=d/2;)//步长变化
        for(i=d+1;i<=n;++i)
            if(A[i]<A[i-d]){//需要将A[i]插入有序增量子表
                A[0]=A[i];    //暂存A[0]
                for(j=i-d;j>0&&A[0]<A[j];j-=d)
                    A[j+d]=A[j];//记录后移
                A[j+d]=A[0];    //插入
            }
}

稳定性：不稳定！
适⽤性：仅适⽤于顺序表，不适⽤于链表

交换排序

冒泡排序

从后往前（或从前往后）两两⽐较相邻元素的值，若为逆序（即A[i-1]>A[i]），则交换它们，直到序列⽐较完。称这样过程为“⼀趟”冒泡排序。
若某⼀趟排序没有发⽣“交换”，说明此时已经整体有序。

//冒泡排序
void swap(int &a,int &b){    //交换
    int temp=a;
    a=b;
    b=temp;
}
void BubbleSort(int A[],int n){
    for(int i=0;i<n-1;i++){
        bool flag=false;    //表示本趟冒泡是否发生交换的标志
        for(int j=n-1;j>i;j--)
            if(A[j-1]>A[j]){//若为逆序
                swap(A[j-1],A[j]);
                flag=true;
            }
        if(flag==false)
            return;//本趟遍历后没有发生交换，说明表已经有序
    }
}

稳定性：稳定
适用性：顺序表，链表都可以
最好时间复杂度（全部有序）：O(n)
最坏时间复杂度（全部逆序）：O(n^2)
平均时间复杂度：O(n^2)

快速排序

算法思想：在待排序表L[1…n]中任取⼀个元素pivot作为枢轴（或基准，通常取⾸元素），通过⼀趟排序将待排序表划分为独⽴的两部分L[1…k-1]和L[k+1…n]，使得L[1…k-1]中的所有元素⼩于pivot，L[k+1…n]中的所有元素⼤于等于pivot，则pivot放在了其最终位置L(k)上，这个过程称为⼀次“划分”。然后分别递归地对两个⼦表重复上述过程，直⾄每部分内只有⼀个元素或空为⽌，即所有元素放在了其最终位置上。

//用第一个元素将待排排序序列分成左右两部分
int Partition(int A[],int low,int high){
    int pivot=A[low];    //用第一个元素作为枢轴
    while(low<high){    //用low、high搜索枢轴的最终位置
        while(low<high&&A[high]>=pivot)
            --high;
        A[low]=A[high];//比枢轴小的元素移动到左端
        while(low<high&&A[low]<=pivot)
            ++low;
        A[high]=A[low];    //比枢轴大的元素移动到右端
    }
    A[low]=pivot;    //枢轴元素存放到最终位置
    return low;        //返回存放枢轴的最终位置
}
//快速排序
void QuickSOort(int A[],int low,int high){
    if(low<high){//递归跳出的条件
        int pivotpos=Partition(A,low,high);    //划分
        QuickSort(A,low,pivotpos-1);    //划分左子表
        QuickSort(A,pivotpos+1,high);    //划分右子表
    }
}

空间复杂度=O(递归层数)
时间复杂度=O(n*递归层数)
最好时间复杂度=O(nlog2n)
最坏时间复杂度=O(n^2)
平均时间复杂度=O(nlog2n)

最好空间复杂度=O(log2n)
最坏空间复杂度=O(n)

快速排序是所有内部排序算法中平均性能最优的排序算法;
稳定性：不稳定

选择排序

选择排序：每⼀趟在待排序元素中选取关键字最⼩（或最⼤）的元素加⼊有序⼦序列

简单选择排序

算法思想：每⼀趟在待排序元素中选取关键字最⼩的元素加⼊有序⼦序列，n个元素的简单选择排序需要 n-1 趟处理；

//简单选择排序
void SelectSort(int A[],int n){
    for(int i=0;i<n-1;i++){    //一共进行n-1趟
        int min=i;            //记录最小位置元素
        for(int j=i+1;j<n;j++){ //在A[i...n-1]中选择最小的元素
            if(A[j]<A[min])
                min=j;        //更新最小元素位置
            if(min!=i)
                swap(A[i],A[min]);    
        }
    }
    //交换函数
    void swap(int &a,int &b){
        int temp=a;
        a=b;
        b=temp;
    }

空间复杂度：O（1）
时间复杂度：O（n^2）
稳定性：不稳定
适⽤性：既可以⽤于顺序表，也可⽤于链表

堆排序

若n个关键字序列L[1…n] 满⾜下⾯某⼀条性质，则称为堆（Heap）：
① 若满⾜：L(i)≥L(2i)且L(i)≥L(2i+1) （1 ≤ i ≤n/2 ）—— ⼤根堆（⼤顶堆）
② 若满⾜：L(i)≤L(2i)且L(i)≤L(2i+1) （1 ≤ i ≤n/2 ）—— ⼩根堆（⼩顶堆）
思路：把所有⾮终端结点都检查⼀遍，是否满⾜⼤根堆的要求，如果不满⾜，则进⾏调整，检查当前结点是否满⾜ 根≥左、右;若不满⾜，将当前结点与更⼤的⼀个孩⼦互换;若元素互换破坏了下⼀级的堆，则采⽤相同的⽅法继续往下调整（⼩元素不断“下坠”）

//建立大根堆
void BuildMaxHeap(int A[],int len){
    for(int i=len/2;i>0;i--)    //从后往前调整所有非终端结点
        HeadAdjust(A,i,len);
}
//将以k为根的子树调整为大根堆
void HeadAdjust(int A[],int k,int len){
    A[0]=A[k];    //A[0]暂存子树的根节点
    for(int i=2*k;i<=len;i*=2){    //沿key较大的子结点向下筛选
        if(i<len&&A[i]<A[i+1])
            i++;                //取key较大的子结点的下标
        if(A[0]>=A[i])
            break;            //筛选结束
        else{
            A[k]=A[i];    //将A[i]调整到双亲结点上
            k=i;        //修改k值，一遍继续向下筛选
        }
    }
    A[k]=A[0];        //被筛选结点的值放入最终位置
}
//堆排序的完整逻辑
void HeapSort(int A[],int len){
    BuildMaxHeap(A,len);    //初始建堆
    for(int i=len;i>1;i--){    //n-1趟的交换和建堆过程
        swap(A[i],A[1]);    //堆顶元素和堆底交换
        HeadAdjust(A,1,i-1);    //将剩余的待排序元素整理成堆
    }
}

对于⼩根堆：
新元素放到表尾，与⽗节点对⽐，若新元素⽐⽗节点更⼩，则将⼆者互换。新元素就这样⼀路“上升”，直到⽆法继续上升为⽌；被删除的元素⽤堆底元素替代，然后让该元素不断“下坠”，直到⽆法下坠为⽌；

归并排序

m路归并，每选出⼀个元素需要对⽐关键字 m-1 次
核⼼操作：把数组内的两个有序序列归并为⼀个

int *B=(int *)malloc((n+1)*sizeof(int));    //辅助数组B
//A[low...mid]和A[mid+1...high]各自有序，将两个部分归并
void Merge(int A[],int low,int mid,int high){
    int i,j,k;
    for(k=low;k<=high;k++)
        B[k]=A[k];
    for(i=low,j=mid+1,k=i;i<=mid&&j<=high;k++){    //    归并
        if(B[i]<=B[j])    //两个元素相等时，优先使⽤靠前的那个（稳定性）
            A[k]=B[i++];    //将较小值复制到A中
        else
            A[k]=B[i++];
    }
    while(i<=mid)
        A[k++]=B[i++];        //没有归并完的部分复制到尾部
    while(j<=high)
        A[k++]=B[j++];
}
 //归并排序
void MergeSort(int A[],int low,int high){
    if(low<high){
        int mid=(low+high)/2;    //从中间划分
        MergeSort(A,low,mid);    //左半部分归并排序
        MergeSort(A,mid+1,high);//右半部分归并排序
        MergeSort(A,low,mid,high);//归并
    }
}

基数排序

https://www.yuque.com/docs/share/a00edd79-fbd3-448b-8d7c-2a1758bb2f5e?# 《基数排序》

外部排序

https://www.yuque.com/docs/share/c37bcda9-cd8d-4add-99da-b38ab458fd3b?# 《外部排序》
https://www.yuque.com/docs/share/ef1b16bc-df98-481c-80d7-949e6835db4c?# 《败者树》
https://www.yuque.com/docs/share/5fde9340-7153-4b64-b848-e224d20fb8ae?# 《置换—选择排序》
https://www.yuque.com/docs/share/964da5c6-0966-443d-8cf9-5a42599cdb2e?# 《最佳归并树》