排序算法总结大全(10种)(2)

堆排序可通过树形结构保存部分比较结果，可减少比较次数。

八、拓扑排序

例 ：学生选修课排课先后顺序

拓扑排序：把有向图中各顶点按照它们相互之间的优先关系排列成一个线性序列的过程。

方法：

在有向图中选一个没有前驱的顶点且输出

从图中删除该顶点和所有以它为尾的弧

重复上述两步，直至全部顶点均已输出（拓扑排序成功），或者当图中不存在无前驱的顶点（图中有回路）为止。

---------------------------------------Code--------------------------------------

void TopologicalSort()/*输出拓扑排序函数。若G无回路，则输出G的顶点的一个拓扑序列并返回OK，否则返回ERROR*/

{

int indegree[M];

int i,k,j;

char n;

int count=0;

数据结构中的10种排序算法总结

Stack thestack;

FindInDegree(G,indegree);//对各顶点求入度indegree[0....num]

InitStack(thestack);//初始化栈

for(i=0;i<G.num;i++)

Console.WriteLine("结点"+G.vertices[i].data+"的入度为"+indegree[i]);

for(i=0;i<G.num;i++)

{

if(indegree[i]==0)

Push(thestack.vertices[i]);

}

Console.Write("拓扑排序输出顺序为：");

while(thestack.Peek()!=null)

{

Pop(thestack.Peek());

j=locatevex(G,n);

if (j==-2)

{

Console.WriteLine("发生错误，程序结束。");

exit();

}

Console.Write(G.vertices[j].data);

count++;

for(p=G.vertices[j].firstarc;p!=NULL;p=p.nextarc)

{

k=p.adjvex;

if (!(--indegree[k]))

Push(G.vertices[k]);

}

}

if (count<G.num)

Cosole.WriteLine("该图有环，出现错误，无法排序。");

else

Console.WriteLine("排序成功。");

}

----------------------------------------Code-------------------------------------- 算法的时间复杂度O（n+e）。

数据结构中的10种排序算法总结

九、锦标赛排序

锦标赛排序的算法思想与体育比赛类似。

首先将n个数据元素两两分组，分别按关键字进行比较，得到n／2个比较的优胜者(关键字小者)，作为第一步比较的结果保留下来，

然后对这n／2个数据元素再两两分组，分别按关键字进行比较， ，如此重复，直到选出一个关键字最小的数据元素为止。

--------------------------------Code in C--------------------------------------- #include <stdio.h>

#include <stdlib.h>

#include <string.h>

#include <math.h>

#define SIZE 100000

#define MAX 1000000

struct node

{

long num;//关键字

char str[10];

int lastwin;//最后胜的对手

int killer;//被击败的对手

long times;//比赛次数

}data[SIZE];

long CompareNum=0;

long ExchangeNum=0;

long Read(char name[])//读取文件a.txt中的数据，并存放在数组data[]中；最后返回数据的个数 {

FILE *fp;

long i=1;

fp=fopen(name,"rw");

fscanf(fp,"%d%s",&data[i].num,data[i].str);

while(!feof(fp))

数据结构中的10种排序算法总结

i++;

fscanf(fp,"%d%s",&data[i].num,data[i].str);

}

return (i-1);

}

long Create(long num)//创建胜者树，返回冠军（最小数）在数组data[]中的下标

{

int i,j1,j2,max,time=1;

long min;//记录当前冠军的下标

for(i=1;pow(2,i-1)<num;i++)

;

max=pow(2,i-1);//求叶子结点数目

for(i=1;i<=max;i++)//初始化叶子结点

{

data[i].killer=0;

data[i].lastwin=0;

data[i].times=0;

if(i>num)

data[i].num=MAX;

}

for(i=1;i<=max;i+=2)//第一轮比赛

{

++CompareNum;

if(data[i].num <= data[i+1].num)

{

data[i].lastwin = i+1;

data[i+1].killer=i;

++data[i].times;

++data[i+1].times;

min=i;

}

else

{

data[i+1].lastwin=i;

data[i].killer=i+1;

数据结构中的10种排序算法总结

++data[i].times;

++data[i+1].times;

min=i+1;

}

}

j1=j2=0;//记录连续的两个未被淘汰的选手的下标

while(time <= (log(max)/log(2)))//进行淘汰赛

{

for(i=1;i<=max;i++)

{

if(data[i].times==time && data[i].killer==0)//找到一名选手

{

j2=i;//默认其为两选手中的后来的

if(j1==0)//如果第一位置是空的，则刚来的选手先来的

j1=j2;

else//否则刚来的选手是后来的，那么选手都已到场比赛开始

{

++CompareNum;

if(data[j1].num <= data[j2].num)//先来的选手获胜

{

data[j1].lastwin = j2;//最后赢的是j2

data[j2].killer=j1;//j2是被j1淘汰的

++data[j1].times;

++data[j2].times;//两选手场次均加1

min=j1;//最小数下标为j1

j1=j2=0;//将j1，j2置0

}

else//同理

{

data[j2].lastwin=j1;

data[j1].killer=j2;

++data[j1].times;

++data[j2].times;

min=j2;

j1=j2=0;

}

数据结构中的10种排序算法总结

}

}

}

time++;//轮数加1

}

return min;//返回冠军的下标

}

void TournamentSort(long num)//锦标赛排序

{

long tag=Create(num);//返回最小数下标

FILE *fp1;

fp1=fopen("sort.txt","w+");//为写入创建并打开文件sort.txt

while(data[tag].num != MAX)//当最小值不是无穷大时

{

printf("%d %s\n",data[tag].num,data[tag].str);//输出数据

fprintf(fp1,"%d %s\n",data[tag].num,data[tag].str);//写入数据

data[tag].num=MAX;//将当前冠军用无穷大替换

tag=Create(num);//返回下一个冠军的下标

}

}

int main()

{

int num;

char name[10];

printf("Input name of the file:");

gets(name);

num=Read(name);//读文件

TournamentSort(num);//锦标赛排序

printf("CompareNum=%d\nExchangeNum=%d\n",CompareNum,ExchangeNum);

return 0;

}

------------------------------------------Code-------------------------------------

十、基数排序

数据结构中的10种排序算法总结

基数排序又被称为桶排序。与前面介绍的几种排序方 …… 此处隐藏：3166字，全部文档内容请下载后查看。喜欢就下载吧 ……