发布时间 : 2024/6/11 4:55:29 星期二 文章排序算法集合更新完毕开始阅读4a37d1e3caaedd3382c4d336

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

--------------------------------Code in C--------------------------------------- #include #include #include #include #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,\

fscanf(fp,\ while(!feof(fp)) { i++;

fscanf(fp,\ }

return (i-1); }

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

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

long min;//记录当前冠军的下标 for(i=1;pow(2,i-1)

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; ++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; } } } }

time++;//轮数加1 }

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

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

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

fp1=fopen(\为写入创建并打开文件sort.txt while(data[tag].num != MAX)//当最小值不是无穷大时 {

printf(\输出数据 fprintf(fp1,\写入数据 data[tag].num=MAX;//将当前冠军用无穷大替换 tag=Create(num);//返回下一个冠军的下标 } }

int main() {

int num; char name[10];

printf(\ gets(name);

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

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

printf(\ return 0; }

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

十、基数排序

基数排序又被称为桶排序。与前面介绍的几种排序方法相比较，基数排序和它们有明显的不同。 前面所介绍的排序方法都是建立在对数据元素关键字进行比较的基础上，所以可以称为基于比较的排序；

而基数排序首先将待排序数据元素依次“分配”到不同的桶里，然后再把各桶中的数据元素“收集”到一起。

通过使用对多关键字进行排序的这种“分配”和“收集”的方法，基数排序实现了对多关键字进行排序。

——————————————————————————————————————— 例：

每张扑克牌有两个“关键字”：花色和面值。其大小顺序为： 花色：§＜¨＜?＜a 面值：2＜3＜??＜K＜A

扑克牌的大小先根据花色比较，花色大的牌比花色小的牌大；花色一样的牌再根据面值比较大小。所以，将扑克牌按从小到大的次序排列，可得到以下序列： §2，?，§A，¨2，?，¨A，?2，?，?A，a2，?，aA 这种排序相当于有两个关键字的排序，一般有两种方法实现。

其一：可以先按花色分成四堆（每一堆牌具有相同的花色），然后在每一堆牌里再按面值从小到大的次序排序，最后把已排好序的四堆牌按花色从小到大次序叠放在一起就得到排序的结