数据结构.期末复习.学习笔记（c语言）

《数据结构（第2版）》陈越
《数据结构（第2版）》（c语言版）严蔚敏
《C语言程序设计（第4版）》何钦铭

---

一、概论 + 二、基础

1. 基本概念

数据结构： 数据对象集+组织方法 组织方式，包括逻辑结构和物理存储结构
逻辑结构： 线性结构+非线形结构
物理结构（存储结构）： 顺序结构+非顺序结构
数据类型： 数据对象集+操作集
抽象数据类型（Abstract Data Type）： 描述数据类型的方法是不依赖于具体实现的，即是数据对象集和操作集的描述与存放数据的机器无关，与数据存储的物理结构无关，与实现操作的算法和编程语言均无关
时间复杂度T（n）： 根据算法写成的程序在执行时耗费时间的长度
空间复杂度S（n）： 根据算法写成的程序在执行时占用存储单元的长度

2. 四种逻辑结构及特点

线形 数据元素之间存在一对一的关系
树 数据元素之间存在一对多的关系
图 数据元素之间存在多对多的关系
集合 数据同属于一个集合但互相无关联性（eg unordered_set）

3. 算法的概念、特性

概念： 解决问题步骤的有限集合，通常用某一种计算机语言进行伪码描述
特性： 有穷性 确定性 可行性 输入项和输出项

4. 算法设计的4个要求

正确性 算法应能正确地解决问题
健壮性 算法应易于理解
易读性 算法应对非法输入进行处理
高效性 算法应在时间和空间上尽可能高效

---

三、线性结构

个人认为，只要重点掌握了顺序表和链式表的实现方式，以及其余线性结构所需实现的功能，基本可以写出全部线性结构代码

1.顺序表

线形表的顺序存储，指在一块存储空间顺序存放线性表的各元素

typedef int Position;
typedef struct LNode *List;
struct LNode {ElementType Data[MAXSIZE];Position Last;
};/* 初始化 */
List MakeEmpty()
{List L;L = (List)malloc(sizeof(struct LNode));L->Last = -1;return L;
}/* 查找 */
#define ERROR -1Position Find( List L, ElementType X )
{Position i = 0;while(i <= L->Last && L->Data[i]!= X) i++;if (i > L->Last)  return ERROR;else  return i; 
}/* 插入 */
bool Insert( List L, ElementType X, Position P ) 
{ /* 在L的指定位置P前插入一个新元素X */Position i;if ( L->Last == MAXSIZE-1) {printf("表满"); return false; }  if ( P<0 || P>L->Last+1 ) {printf("位置不合法");return false; } for( i=L->Last; i>=P; i-- )L->Data[i+1] = L->Data[i]; L->Data[P] = X;  L->Last++; return true; 
} /* 删除 */
bool Delete( List L, Position P )
{ /* 从L中删除指定位置P的元素 */Position i;if( P<0 || P>L->Last ) { printf("位置%d不存在元素", P ); return false; }for( i=P+1; i<=L->Last; i++ )L->Data[i-1] = L->Data[i]; L->Last--; return true;   
}

2.单链表

线性表的链式储存，不需要用地址连续的存储单元顺序存储线性表中各元素

typedef struct LNode *PtrToLNode;
struct LNode {ElementType Data;PtrToLNode Next;
};
typedef PtrToLNode Position;
typedef PtrToLNode List;/* 查找 */
#define ERROR NULLPosition Find( List L, ElementType X )
{Position p = L; /* p指向L的第1个结点 */while ( p && p->Data!=X )p = p->Next;if ( p )return p;elsereturn ERROR;
}/* 带头结点的插入 */
bool Insert( List L, ElementType X, Position P )
{ /* 这里默认L有头结点 */Position tmp, pre;for ( pre=L; pre&&pre->Next!=P; pre=pre->Next ) ;            if ( pre==NULL ) { printf("插入位置参数错误\n");return false;}else {tmp = (Position)malloc(sizeof(struct LNode)); tmp->Data = X; tmp->Next = P;pre->Next = tmp;return true;}
}/* 带头结点的删除 */
bool Delete( List L, Position P )
{ /* 这里默认L有头结点 */Position pre;/* 查找P的前一个结点 */        for ( pre=L; pre&&pre->Next!=P; pre=pre->Next ) ;            if ( pre==NULL || P==NULL) { printf("删除位置参数错误\n");return false;}else { pre->Next = P->Next;free(P);return true;}
}

线性结构的两种存储结构（顺序、链式）：

• 顺序表
• • 优点：存取速度快
• • 缺点：插入和删除操作效率低，需要优先分配内存空间，可能导致内存浪费或不足

• 链式表
  • 优点：插入和删除操作效率高，动态分配内存
  • 缺点：访问元素速度慢，实现相对复杂

3.循环链表+双向链表

实现代码与单链表类似，这里不过多赘述了

4.栈（后进先出）

只能在同一端进行插入删除操作
线形存储：

typedef int Position;
struct SNode {ElementType *Data; /* 存储元素的数组 */Position Top;      /* 栈顶指针 */int MaxSize;       /* 堆栈最大容量 */
};
typedef struct SNode *Stack;Stack CreateStack( int MaxSize )
{Stack S = (Stack)malloc(sizeof(struct SNode));S->Data = (ElementType *)malloc(MaxSize * sizeof(ElementType));S->Top = -1;S->MaxSize = MaxSize;return S;
}

链式存储：

typedef struct SNode *PtrToSNode;
struct SNode {ElementType Data;PtrToSNode Next;
};
typedef PtrToSNode Stack;Stack CreateStack( ) 
{ /* 构建一个堆栈的头结点，返回该结点指针 */Stack S;S = (Stack)malloc(sizeof(struct SNode));S->Next = NULL;return S;
}

线形入栈操作：

bool Push( Stack S, ElementType X )
{if ( S->Top == S->MaxSize-1 ) {printf("堆栈满");return false;}else {S->Data[++(S->Top)] = X;return true;}
}

链式入栈操作：

bool Push( Stack S, ElementType X )
{ /* 将元素X压入堆栈S */PtrToSNode TmpCell;TmpCell = (PtrToSNode)malloc(sizeof(struct SNode));TmpCell->Data = X;TmpCell->Next = S->Next;S->Next = TmpCell;return true;
}

线形出栈操作：

ElementType Pop( Stack S )
{if ( S->Top == -1 ) {printf("堆栈空");return ERROR; /* ERROR是ElementType的特殊值，标志错误 */}else return ( S->Data[(S->Top)--] );
}

链式出栈操作：

ElementType Pop( Stack S )  
{ /* 删除并返回堆栈S的栈顶元素 */PtrToSNode FirstCell;ElementType TopElem;if(S->Next == NULL  ) {printf("堆栈空"); return ERROR;}else {FirstCell = S->Next; TopElem = FirstCell->Data;S->Next = FirstCell->Next;free(FirstCell);return TopElem;}
}

5.队列（先进先出）

只能在一端插入，而在另一端删除
顺序存储：

typedef int Position;
struct QNode {ElementType *Data;     /* 存储元素的数组 */Position Front, Rear;  /* 队列的头、尾指针 */int MaxSize;           /* 队列最大容量 */
};
typedef struct QNode *Queue;Queue CreateQueue( int MaxSize )
{Queue Q = (Queue)malloc(sizeof(struct QNode));Q->Data = (ElementType *)malloc(MaxSize * sizeof(ElementType));Q->Front = Q->Rear = 0;Q->MaxSize = MaxSize;return Q;
}

链式存储：

typedef struct Node *PtrToNode;
struct Node { /* 队列中的结点 */ElementType Data;PtrToNode Next;
};
typedef PtrToNode Position;struct QNode {Position Front, Rear;  /* 队列的头、尾指针 */int MaxSize;           /* 队列最大容量 */
};
typedef struct QNode *Queue;

循环队列的判断条件都是在少用一个空间的前提下
循环队列判空：

bool IsEmpty( Queue Q )
{return (Q->Front == Q->Rear);
}

循环队列判满：

bool IsFull( Queue Q )
{return ((Q->Rear+1)%Q->MaxSize == Q->Front);
}

计算队列长度：

ElementType LengthQ( Queue Q )
{return ((Q->Rear-Q->Front+Q->MaxSize)%Q->Maxize);//加n是为了防止减成负数
}

数据入/出队：

bool AddQ( Queue Q, ElementType X )
{if ( IsFull(Q) ) {printf("队列满");return false;}else {Q->Rear = (Q->Rear+1)%Q->MaxSize;Q->Data[Q->Rear] = X;return true;}
}ElementType DeleteQ( Queue Q )
{if ( IsEmpty(Q) ) { printf("队列空");return ERROR;}else  {Q->Front =(Q->Front+1)%Q->MaxSize;return  Q->Data[Q->Front];}
}

---

四、树和二叉树

1.树

树： 非线形数据结构，由节点和边组成，用于表示元素之间的层次关系
结点的度： 一个结点拥有的子树的数量
结点的层次： 从根结点开始算，根节点位第一层，其子节点为第二层，以此类推
叶子结点： 度为0的节点
分支结点： 度不为0的节点
树的深度： 树中节点的最大层次

2.二叉树

二叉树的二叉链表存储结构
共有n+1个空指针域

typedef struct TNode *Position;
typedef Position BinTree; /* 二叉树类型 */
struct TNode{ /* 树结点定义 */ElementType Data; /* 结点数据 */BinTree Left;     /* 指向左子树 */BinTree Right;    /* 指向右子树 */
};

二叉树的树顺序存储结构
比较简单且不要求掌握，就不上代码了
从第一个节点开始画一颗完全二叉树，没有元素的位置用空节点补齐
二叉树： 每个结点最多有俩个子结点的树结构，分为左子树和右子树
满二叉树： 每一层的结点树都达到最大值的二叉树
完全二叉树： 除了最后一层外，每一层都满，且最后一层的结点都集中在左侧
二叉树遍历： 先序，后序，中序，层次遍历

void InorderTraversal( BinTree BT )
{if( BT ) {InorderTraversal( BT->Left );printf("%d ", BT->Data); InorderTraversal( BT->Right );}
}void PreorderTraversal( BinTree BT )
{if( BT ) {printf("%d ", BT->Data );PreorderTraversal( BT->Left );PreorderTraversal( BT->Right );}
}void PostorderTraversal( BinTree BT )
{if( BT ) {PostorderTraversal( BT->Left );PostorderTraversal( BT->Right );printf("%d ", BT->Data);}
}void LevelorderTraversal ( BinTree BT )
{ Queue Q; BinTree T;if ( !BT ) return; /* 若是空树则直接返回 */Q = CreatQueue();AddQ( Q, BT );while ( !IsEmpty(Q) ) {T = DeleteQ( Q );printf("%d ", T->Data); if ( T->Left )   AddQ( Q, T->Left );if ( T->Right )  AddQ( Q, T->Right );}
}

层序考的比较多
基本性质：

• 一个二叉树第i层的最大节点数是2的i-1次方
• 深度为k的二叉树右最大总节点数2的k次方减1
• n0=n2+1
• n1=0/1
• 具有n个节点的完全二叉树深度是lgn/lg2+1

3.森林

森林： 若干互不相交的树组成的集合
树，森林，二叉树的相互转化：
二叉树转森林：

拆分的时候把右子树，右子树的右子树，等等，全部割开
树转二叉树：

比较关键的一点其实就是一个节点的最左子节点是它的子节点，别的都是最左子节点的右子树
二叉搜索树： 插入和删除操作O（logN），左小右大
二叉平衡树： 查找幸运是O（logN），否则是O（N）

4.哈夫曼树

哈夫曼树： 带权路径长度最短的树，又叫最优二叉树

画起来比较麻烦，可以想象从所有没用过的节点中取出权值最小的俩个，组成一个新的权值放回原集合，继续重复这一操作，最后一定会组成一个哈夫曼树。
带权路径长度（WSL）： 所有圆形的数字相加
哈夫曼编码： 往左走是0往右走是1，走到它所组成的字符串就是它的编码

5.堆

堆： 一种特殊的队列，取出需要按照元素的优先级大小，与元素进入队列的先后顺序无关。最常见状态是一颗完全二叉树

typedef struct HNode *Heap; /* 堆的类型定义 */
struct HNode {ElementType *Data; /* 存储元素的数组 */int Size;          /* 堆中当前元素个数 */int Capacity;      /* 堆的最大容量 */
};
typedef Heap MaxHeap; /* 最大堆 */
typedef Heap MinHeap; /* 最小堆 */#define MAXDATA 1000  /* 该值应根据具体情况定义为大于堆中所有可能元素的值 */MaxHeap CreateHeap( int MaxSize )
{ /* 创建容量为MaxSize的空的最大堆 */MaxHeap H = (MaxHeap)malloc(sizeof(struct HNode));H->Data = (ElementType *)malloc((MaxSize+1)*sizeof(ElementType));H->Size = 0;H->Capacity = MaxSize;H->Data[0] = MAXDATA; /* 定义"哨兵"为大于堆中所有可能元素的值*/return H;
}bool Insert( MaxHeap H, ElementType X )
{ /* 将元素X插入最大堆H，其中H->Data[0]已经定义为哨兵 */int i;if (H->Size == H->Capacity ) { printf("最大堆已满");return false;}i = ++H->Size; /* i指向插入后堆中的最后一个元素的位置 */for ( ; H->Data[i/2] < X; i/=2 )H->Data[i] = H->Data[i/2]; /* 上滤X */H->Data[i] = X; /* 将X插入 */return true;
}#define ERROR -1 /ElementType DeleteMax( MaxHeap H )
{ /* 从最大堆H中取出键值为最大的元素，并删除一个结点 */int Parent, Child;ElementType MaxItem, X;if (H->Size == 0) {printf("最大堆已为空");return ERROR;}MaxItem = H->Data[1]; /* 取出根结点存放的最大值 *//* 用最大堆中最后一个元素从根结点开始向上过滤下层结点 */X = H->Data[H->Size--]; /* 注意当前堆的规模要减小 */for( Parent=1; Parent*2<=H->Size; Parent=Child ) {Child = Parent * 2;if( (Child!=H->Size) && (H->Data[Child]<H->Data[Child+1]) )Child++;  /* Child指向左右子结点的较大者 */if( X >= H->Data[Child] ) break; /* 找到了合适位置 */else  H->Data[Parent] = H->Data[Child];}H->Data[Parent] = X;return MaxItem;
} void PercDown( MaxHeap H, int p )
{ /* 下滤：将H中以H->Data[p]为根的子堆调整为最大堆 */int Parent, Child;ElementType X;X = H->Data[p]; /* 取出根结点存放的值 */for( Parent=p; Parent*2<=H->Size; Parent=Child ) {Child = Parent * 2;if( (Child!=H->Size) && (H->Data[Child]<H->Data[Child+1]) )Child++;  /* Child指向左右子结点的较大者 */if( X >= H->Data[Child] ) break; /* 找到了合适位置 */else  H->Data[Parent] = H->Data[Child];}H->Data[Parent] = X;
}void BuildHeap( MaxHeap H )
{ int i;/* 从最后一个结点的父节点开始，到根结点1 */for( i = H->Size/2; i>0; i-- )PercDown( H, i );
}

---

五、查找

1.基本概念

查找表： 同一类型的数据元素构成的集合，主要用于查询和检索操作。
关键字： 数据元素中某个数据项的值
静态查找表： 查找过程中不需要修改数据的查找表
动态查找表： 查找过程中需要修改数据的查找表
平均查找长度（ASL）： 在确定给定值时，和给定值进行比较的关键字个数的期望

	平均查找长度	时间复杂度	空间复杂度
顺序查找	(n+1)/2	O(n)	O(1)
折半查找	lg(n+1)/lg(2)-1	O(logn)	O(1)
分块查找	/二者之间	O(m+n)	O(m)

2.折半查找

折半查找要求元素有序排列，并且使用顺序存储结构
参考博客：二分算法部分
比较简单，就不赘述了，参考博客是之前的c++二分算法
折半查找判定树： 判定n个数的比较过程，从根节点开始存放下标，左小右大，从1开始向下取整，要求能够画出

3.散列

散列表： 通过哈希函数将关键字映射到表中一个位置的查找结构
散列地址： 散裂表中的某个地址
同义词： 具有相同散列地址的俩个元素
装填因子： 填入表中元素个数n/散列表空间大小m
散列函数：

• 直接定址法 h(key)=a*key+b
• 除留余数法 h(key)=key%p
• 数字分析法 h(key)=atoi(key+7)

冲突： 不同的关键字映射到同一个散列地址上

• 线形探测法 hi=(h(s)+x),x=1,2,3… （一次聚集）
• 平方探测法 hi=(h(s)+x),x=1,-1,4,-4… (二次聚集)
• 双散列探测法 x选为i*h2(key)
• 再散裂法 加倍扩大散列表
• 分离链接法 将相应位置上冲突的所有关键词存储在同一个单链表中

平均查找次数（ASL）

分离链接法

typedef struct TblNode *HashTable; /* 散列表类型 */
struct TblNode {   /* 散列表结点定义 */int TableSize; /* 表的最大长度 */List Heads;    /* 指向链表头结点的数组 */
};HashTable CreateTable( int TableSize )
{HashTable H;int i;H = (HashTable)malloc(sizeof(struct TblNode));H->TableSize = NextPrime(TableSize);/* 以下分配链表头结点数组 */H->Heads = (List)malloc(H->TableSize*sizeof(struct LNode));/* 初始化表头结点 */for( i=0; i<H->TableSize; i++ ) {H->Heads[i].Data[0] = '\0';H->Heads[i].Next = NULL;}return H;
}Position Find( HashTable H, ElementType Key )
{Position P;Index Pos;Pos = Hash( Key, H->TableSize ); /* 初始散列位置 */P = H->Heads[Pos].Next; /* 从该链表的第1个结点开始 *//* 当未到表尾，并且Key未找到时 */ while( P && strcmp(P->Data, Key) )P = P->Next;return P; /* 此时P或者指向找到的结点，或者为NULL */
}bool Insert( HashTable H, ElementType Key )
{Position P, NewCell;Index Pos;P = Find( H, Key );if ( !P ) { /* 关键词未找到，可以插入 */NewCell = (Position)malloc(sizeof(struct LNode));strcpy(NewCell->Data, Key);Pos = Hash( Key, H->TableSize ); /* 初始散列位置 *//* 将NewCell插入为H->Heads[Pos]链表的第1个结点 */NewCell->Next = H->Heads[Pos].Next;H->Heads[Pos].Next = NewCell; return true;}else { /* 关键词已存在 */printf("键值已存在");return false;}
}void DestroyTable( HashTable H )
{int i;Position P, Tmp;/* 释放每个链表的结点 */for( i=0; i<H->TableSize; i++ ) {P = H->Heads[i].Next;while( P ) {Tmp = P->Next;free( P );P = Tmp;}}free( H->Heads ); /* 释放头结点数组 */free( H );        /* 释放散列表结点 */
}

---

六、图

1.基本概念

顶点、弧、弧头、弧尾： 顶点是基本单位，也称为节点，弧是连接俩个顶点的线段。在有向图中弧的起点叫弧头，终点叫弧尾
有向图、无向图、有向网、无向网： 有向图跟无向图的区别在于边是否有方向，图和网的区别在于边是否有权重
完全图、有向完全图： 存在所有的弧
顶点的度、入度、出度： 度指与该边关联的所有边的数量
路径、回路（环）： 路径指从一个顶点到另一个顶点所经过的序列，首尾相同的叫做回路
连通图、强连通图： 无向图中任意俩个节点是连通的就叫连通图，有向图中任意俩个节点间互相有路径叫强连通图
连通分量、强连通分量:
强连通分量必须互相可以走到，强连通图中只有自身一个强连通分量

• 子图：连通分量应该是原图的子图
• 连通：连通分量本身应该是连通的
• 极大顶点数：连通子图含有极大顶点数，即再加入其他顶点将会导致子图不连通
• 极大边数：具有极大顶点数的连通子图包含依附于这些顶点的所有边

生成树、最小生成树、拓扑排序：

• G有n-1条边，且没有环
• G有n-1条边，且是连通的
• G的每一对顶点有且只有一条路径相连
• G是连通的，但删除任何一条边都会使它不连通

如果有向图恰有一个顶点的入度为0，其余的顶点入度为1，则是生成树。最小生成树指权重和最小。

AOV网、AOE网、关键路径、最短路径:

• 图中的边表示活动的先后关系，有向边(v,w)意味着活动v必须在活动w开始之前完成。这种顶点表示活动或任务的图称为AOV（Activity On Vertex）网，一般对应拓扑排序
• 图中的顶点表示事件，有向边表示活动的，权值表示活动的持续时间的有向无环带权图称为AOE（Activity On Edge）网
• 关键路径是从源点到汇点的最长路径，也是整个工程的最短完成时间。（工程概念）关键路径上的活动是关键活动，源点表示入度为0的点，汇点是出度为0的点
• 最短路径顾名思义是权值和最小的路径，求单源最短路Dijkstra，多源最短路Floyd，Dijkstra
  算法不要求掌握，但要学会画表
  
  贴一张同学问我的题目，虽然上一次的f已经是自己的最优解了，但它不是当次操作的最优解，所以不能作为终点。要注意每一次i只会有一个终点，也只有已经是终点的点才可以出现在别人的路径上，不要忘记写Vj和点集S

2. 深度和广度优先遍历（DFS/BFS）

具体算法学习C++版 搜索与搜索剪枝

3. 能用普里姆（Prim）算法和克鲁斯卡尔（Kruskal）

这里考算法可能性也不大，重点掌握应用

• Prim
  1. 选定一个结点，加入集合S
  2. 找出所有连接集合S内外各一个点的权值最小的边
  3. 把此边所对应的点加入集合S
  4. 重复2，3直到所有点进入S
• Krusial
  1. 每次选取一条边加入集合，与此同时把边首尾俩点加入点集S
  2. 这条边必须至少包含一个点不在点集内
  3. 重复1，2直到所有点进入S

---

七、排序

稳定性： 相同的俩个元素在排序后相对顺序没有改变，则该排序是稳定的。

	最佳	最差	时间复杂度	空间复杂度	稳定性
选择排序	O(n^2)	O(n^2)	O(n^2)	O(1)	✖️
堆排序	O(n*log(n))	O(n*log(n)	O(n*log(n)	O(1)	✖️
插入排序	O(n)	O(n^2)	O(n^2)	O(1)	☑️
希尔排序	O(n)	O(n^s)	O(nlogn)	O(1)	✖️
冒泡排序	O(n)	O(n^2)	O(n^2)	O(1)	☑️
快速排序	O(n*log(n))	O(n^2)	O(n*log(n))	O(logn)	✖️
归并排序	O(nlogn)	O(nlogn)	O(nlogn)	O(n)	☑️
桶排序	O(nlogn)	O(nlogn)	O(nlogn)	O(1)	☑️
基数排序	O(n*d)	O(n*d)	O(n*d)	O(n)	☑️

1.选择排序

简单选择排序： 在未排序的序列中选出最小的元素和序列的首位元素交换，接下来在剩下的未排序序列中再选出最小元素与序列的第二位元素交换，以此类推
必须掌握，多出函数题

void Swap(ElementType *a,ElemenType *b){ElementType t = *a,*a = *b,*b = t;
}void SimpleselectionSort(ElementType A[], int N) {int i,j,min;for (i = 0; i < N-1; i++) {//寻找最小元素min = i;for (j = i+1; j < N; j++) {if(A[j] < A[min]) min = j;//min记录最小元素位置Swap(&A[i],&A[min]);}}
}

堆排序：
与树的堆及其操作相类似，多出代码填空题

void Swap( ElementType *a, ElementType *b )
{ElementType t = *a; *a = *b; *b = t;
}void PercDown( ElementType A[], int p, int N )
{ /* 将N个元素的数组中以A[p]为根的子堆调整为最大堆 */int Parent, Child;ElementType X;X = A[p]; /* 取出根结点存放的值 */for( Parent=p; (Parent*2+1)<N; Parent=Child ) {Child = Parent * 2 + 1;if( (Child!=N-1) && (A[Child]<A[Child+1]))Child++; if( X >= A[Child] ) break; else  A[Parent] = A[Child];}A[Parent] = X; //合适位置
}void HeapSort( ElementType A[], int N ) 
{ /* 堆排序 */int i;for ( i=N/2-1; i>=0; i-- )PercDown( A, i, N );for ( i=N-1; i>0; i-- ) {/* 删除最大堆顶 */Swap( &A[0], &A[i] ); PercDown( A, 0, i );}
}

2.插入排序

**简单插入排序：**将待排序的一组序列分为已排好序的和未排好序的俩个部分。初始状态时，已排序序列仅包含第一个元素，未排序序列中的元素为除去第一个以外的N-1个元素，此后将未排序序列中的元素逐一插入到已排序的序列中。

 void InsertionSort(ElementType A[], int N) {int p,i;ElementType Tmp;for (p = 1; p < N; p++) {Tmp = A[p];//取出未排序序列中的第一个元素for (i = p; i > 0 && A[i-1] > Tmp; i--) {A[i] = A[i-1]; //依次与已排序序列中元素比较并右移}A[i] = Tmp;}}

希尔排序： 将整个待排序的记录序列分割成若干个子序列分别进行直接插入排序（每个子序列中元素的间距相等），直到整个序列中的记录基本有序后，再对全体记录进行一次直接插入排序
掌握应用即可，无具体代码

3.交换排序

冒泡排序： 相邻元素俩俩比较，若前者大于后者则交换，一轮下来最大的元素会移动到末尾。重复操作直到全部有序（这一轮没有交换说明已经有序）
快速排序：

1. 选择一个主元pivotloc
2. 分左右俩部分进行快排，将大于主元的放在右边，小于主元的放在左边
3. 以最低位置的数作为枢轴，从右往左找，high–，第一个小于枢轴的数字放在low位置，再从左往右找，low++，第一个大于枢轴的数字放在high位置
4. 若low<high，则交换位置
5. 重复3，4直到high和low错位，将基准与此时low的位置交换

void Swap(int *a,int *b) {int t = *a; *a = *b; *b = t;
}int Partition ( SqList L,int low,  int  high ){int temp = L.elem[low];L.elem[0] = L.elem[low];while(low < high){while(low<high && L.elem[high]>=temp) high--;L.elem[low] = L.elem[high]; //这里枢轴消失了while(low<high && L.elem[low]<=temp) low++;L.elem[high] = L.elem[low];//反复交换}L.elem[low] = L.elem[0];//枢轴放在最终low的位置return low;
}void Qsort ( SqList  L,int low,  int  high ) 
{ int  pivotloc;if(low<high){  pivotloc = Partition(L, low, high ) ;Qsort (L, low, pivotloc-1) ; Qsort (L, pivotloc+1, high );}
}

4.归并排序

归并排序： 将大小为n的序列看成n个长度为1的子序列，接下来将相邻子序列俩俩进行归并排序，形成n/2（+1）个长度为2（或1）的有序子序列，循环直到剩下一个长度为n的序列

5.基数排序

不要求掌握
桶排序： 将数组构建成一个最大堆或最小堆，每次取出堆顶元素与最后一个元素交换，调成堆结构，重复此过程直到全部有序
基数排序： 按数字位的顺序依次进行排序，d是数字的位数

---