求归并排序算法！
归并排序。
1.这里，在把数组暂时复制到临时数组时，将第二个子数组中的顺序颠倒了一下。这样，两个子数组从两端开始处理，使得他们互相成为另一个数组的“检查哨”。 这个方法是由R.Sedgewick发明的归并排序的优化。
2.在数组小于某一阀值时，不继续归并，而直接使用插入排序，提高效率。这里根据Record的结构，将阀值定位 16。
#define THRESHOLD 16
typedef struct _Record{
int data; //数据
int key; //键值
}Record;
//供用户调用的排序 函数
void Sort(Record Array, Record TempArray, int left, int right){
TwoWayMergeSort(Array, TempArray, left, right);
}
//归并排序
void TwoWayMergeSort(Record Array, Record TempArray,
int left, int right)
{
if(right 《= left) return; //如果只含一个元素，直接返回
if( right-left+1 ){ //如果序列长度大于阀值，继续递归
int middle = (left + right)/2;
Sort(Array, TempArray, left, middle); //对左面进行递归
Sort(Array, TempArray, left, right, middle); //对右面进行递归
Merge(Array, TempArray, left, right, middle); //合并
}
else{
//如果序列长度小于阀值，采用直接插入排序，达到最佳效果
ImproveInsertSorter(&Array[left], right-left+1);
}
}
//归并过程
void Merge(Record Array, Record TempArray,
int left, int right, int middle)
{
int index1, index2; //两个子序列的起始位置
int k;
复制左边的子序列
for(int i=1; i《=middle; i++){
TempArray[i] = Array[i];
}
//复制右边的子序列，但顺序颠倒过来
for(int j=1; j《=right-middle; j++){
TempArray[right-j+1] = Array[j+middle];
}
//开始归并
for(index1=left, index2=right, k=left; k《=right; k++){
if(TempArray[index1].key《TempArray[index2].key){
Array[k] = TempArray[index++];
}
else{
Array[k] = TempArray[index2--];
}
}
}
//当长度小于阀值时 使用的直接插入排序的代码
void ImproveInsertSorter(Record Array, int size){
Record TempRecord; //临时变量
for(int i=1; i《size; i++){
TempRecord = Array[i];
int j = i-1;
//从i开始往前寻找记录i的正确位置
while(j》=0 && TempRecord.key《Array[j].key){
Array[j+1] = Array[j];
j = j-1;
}
Array[j+1] = TempRecord;
}
}
终于敲完了。。。 第一次回答问题， 只是觉得好玩`
解析一哈c语言中的kmp算法，bf算法,kr算法之间的联系与区别，尽量浅显易懂，谢谢！
三种算法联系：都是字符串匹配算法。
区别：
“KMP算法”：在匹配过程称，若发生不匹配的情况，如果next[j]》=0，则目标串的指针i不变，将模式串的指针j移动到next[j]的位置继续进行匹配；若next[j]=-1，则将i右移1位，并将j置0，继续进行比较。
“BF算法”是普通的模式匹配算法，BF算法的思想就是将目标串S的第一个字符与模式串P的第一个字符进行匹配，若相等，则继续比较S的第二个字符和P的第二个字符；若不相等，则比较S的第二个字符和P的第一个字符，依次比较下去，直到得出最后的匹配结果。
“KR算法”在每次比较时，用HASH算法计算文本串和模式串的HASH映射，通过比较映射值的大小来比较字符串是否匹配。但是考虑到HASH冲突，所以在映射值相同的时候，还需要近一步比较字符串是否相同。但是在每次比较时，需要计算HASH值，所以选择合适的HASH算法很重要。
略知一二！
以邻接表作存储结构实现求源点到其余各顶点的最短路径的Dijkstra算法
具体算法为：
//Dijkstra求单源最短路径
#include《stdio.h》
#define N 20 //图的顶点最多数
#define MAX 1000
#define MIN -1
typedef int ElemType;//图的顶点标识，这里为自然数
//图的结点结构
typedef struct ArcNode{
ElemType adjvex;//图的顶点 （该弧指向顶点的位置）
struct ArcNode *nextarc;//指向下一条弧的指针
int info//该弧权值
}ArcNode;
//表头结点表
typedef struct VertexNode{
ElemType data;
ArcNode *firstarc;
}VertexNode;
//图
typedef struct AdjList{
VertexNode vertex[N];
int vexnum;//图的顶点数
int arcnum;//弧数;
int kind;//图的种类（kind=1为有向图）
int dist[N];//图的路径长度
int path[N];//辅助数组
}AdjList;
//边
typedef struct{
int i;
int j;
int f;
}Side;
//邻接表法创建图
int CreateDAG(AdjList *L){
int i,j;
ArcNode *p=NULL;
//测试用例
Side S[N];
S.i=1;S.j=3;S.f=10;
S.i=1;S.j=5;S.f=30;
S.i=1;S.j=6;S.f=100;
S.i=2;S.j=3;S.f=5;
S.i=3;S.j=4;S.f=50;
S.i=4;S.j=6;S.f=10;
S.i=5;S.j=6;S.f=60;
S.i=5;S.j=4;S.f=20;
for(i=1;i《7;i++){
L-》vertex[i].data=i;
L-》dist[i]=MAX;//设为最大值，表示不可达
L-》path[i]=MIN;//设为最小值，表示尚未初始化
//L-》vertex[i].indegree=0;
L-》vertex[i].firstarc=NULL;
}
L-》kind=1;
L-》vexnum=6;
L-》arcnum=8;
for(i=0;i《8;i++){
p=(ArcNode *)malloc(sizeof(ArcNode));
p-》adjvex=S[i].j;
p-》info=S[i].f;
p-》nextarc=L-》vertex[(S[i].i)].firstarc;
L-》vertex[(S[i].i)].firstarc=p;
if(S[i].i==1){//初始顶点为1
L-》dist[(S[i].j)]=S[i].f;
//L-》path[(S[i].j)]=S[i].f;
}
// L-》vertex[(S[i].j)].indegree++;
}
return 1;
}
//输出邻接表存储
void PrintALGraph(AdjList *L){
ArcNode *p=NULL;
int i,k=0;
for(i=1;i《=L-》vexnum;i++){
k=L-》vertex[i].data;
printf(“V%d“,k);
// printf(“ 入度为%d 邻接点有 “,(L-》vertex[i].indegree));
p=L-》vertex[k].firstarc;
while(p!=NULL){
printf(“ -》%d“,p-》adjvex);
p=p-》nextarc;
}
printf(“\n“);
}
}
//Dijkstra求单源最短路径
void Dijkstra(AdjList *L){
int i=1,j,k=0;
Side s;
L-》path=0;
ArcNode *p=NULL;
while(k《10){
s.f=MAX;
for(i=1;i《=L-》vexnum;i++){
if(L-》path[i]!=MIN){
p=L-》vertex[i].firstarc;
if(p!=NULL){
while(p!=NULL){
if(s.f》p-》info&&L-》path[(p-》adjvex)]==MIN){
s.f=p-》info;
s.i=i;
s.j=p-》adjvex;
}
p=p-》nextarc;
}
}
}
}
if(s.f==MAX){
}else if(L-》dist[(s.j)]》L-》dist[(s.i)]+s.f){
L-》dist[(s.j)]=L-》dist[(s.i)]+s.f;
L-》path[(s.j)]=L-》dist[(s.j)];
}else{
L-》path[(s.j)]=L-》dist[(s.j)];
}
k++;
}
//输出
printf(“输出最短路径:\n“);
for(i=1;i《=L-》vexnum;i++){
if(L-》dist[i]==1000||i==1){
printf(“v1到v%d不存在最短路径\n“,i);
}else{
printf(“v1到v%d的最短路径是%d\n“,i,L-》dist[i]);
}
printf(“path is %d\n“,L-》path[i]);
}
}
int main(){
AdjList *L=(AdjList *)malloc(sizeof(AdjList));
if(CreateDAG(L)==1){
PrintALGraph(L);
Dijkstra(L);
}else{
printf(“创建失败\n“);
}
}
扩展资料：
要求带权有向图中某一顶点到其他各顶点的最短路径，常用Dijkstra算法，该算法基本思想是，先将图的顶点分为两个集合，一个为已求出最短路径的终点集合（开始为原点v1），另一个为还未求出最短路径的顶点集合（开始为除v1外的全部结点），然后按最短路径长度的递增顺序逐个将第二个集合的顶点加到第一组中。-归并排序
算法中使用dist数组，dist[i]表示目前已经找到、v1到vi的当前最短路径，否则为MAX；path数组，作为是否找到该点最短路径的标志，path[i]==MIN表示为未找到，否则为最短路径值。
