排序(希尔,快速,堆排序等)

#include"stdio.h"

#include"math.h"

#include"stdlib.h"

#include"malloc.h"

#define Maxsize 10000000

#define N 20

#define EQ(a,b) ((a)==(b))

#define LT(a,b) ((a)<(b))

#define LQ(a,b) ((a)<=(b))

#define LEN sizeof(SqList)

#define Maxr 10

#define MAXNUM 100000000

typedef struct node{

int key;

int num;

}node;

typedef struct {

struct node r[Maxsize+1];

long length;

}SqList,*qSqList;

typedef struct node2{

struct node r;

struct node2 *next;

}RecType;

long shifttimes;//统计移动次数

long comparetimes;//统计比较次数

qSqList creat(char filename[])//读入文件并且将数据保存

{

FILE *fp;

long i;

qSqList L;

L=(qSqList)malloc(LEN);

L->length=0;

if((fp=fopen(filename,"r"))==NULL)//文件不存在时终止程序{

printf("cannot open file\n");

exit(0);

}

for(i=1;i

{

fscanf(fp,"%ld (%d)",&(L->r[i].key),&(L->r[i].num));

if(L->r[i].key<0)

break;

L->length++;//记录读入的数据长度

}

fclose(fp);

return(L);

}

void Print2(qSqList L)//将序列输出到指定的文件中

{

long i;

FILE *fp;

char filename[N];

printf("\n\t请输入存储文件名：");

scanf("%s",filename);//输入将要储存的文件名

fp=fopen(filename,"w");

for(i=1;i<=L->length;i++)//将链表中数据逐一写入文件中

{

fprintf(fp,"%d (%d)\n",L->r[i].key,L->r[i].num);

}

fclose(fp);

}

void Print(qSqList L)//打印数据个数以及排序过程中的比较次数和移动次数{

printf("\n\t数据个数:%ld",L->length);

printf("\n\t比较次数:%ld",comparetimes);

printf("\n\t移动次数:%ld",shifttimes);

}

struct node Min1(struct node a,struct node b)//比较两接点关键字的大小{

struct node temp;

if(a.key>b.key)

temp=b;

else

temp=a;

comparetimes++;

return(temp);

}

qSqList shellinsert(qSqList L,int dk)//对顺序表以dk为增量作直接插入排序

{

int i,j;

for(i=dk+1;i<=L->length;i++)

{

if(LT(L->r[i].key,L->r[i-dk].key))//将L->r[i]插入到有序增量子表

{

L->r[0]=L->r[i];//将L->r[i]暂时存储在L->r[0]

shifttimes++;

for(j=i-dk;j>0&&j<(L->r[0].key,L->r[j].key);j-=dk)//记录后移，查找插入位置

{

L->r[j+dk]=L->r[j];

comparetimes++;

shifttimes++;

}

if(j>0)

comparetimes++;

L->r[j+dk]=L->r[0];//插入

shifttimes++;

}

comparetimes++;

}

// Print(L);

return(L);

}

qSqList shell(qSqList L)//希尔排序

{

int i,t=0;

int k;

for(t=0;LQ(pow(2,t),(L->length+1));t++);

t=t-1;

// printf("%d",t);

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

{

k=(int)pow(2,t-i+1)-1;//计算排序增量

L=shellinsert(L,k);

}

Print(L);

Print2(L);

return(L);

}

long Quicksort(qSqList L,long low,long high)//交换顺序表L中子表L->r[low..high]的记录，使枢轴记录到位，并返回其所在位置

{

int pivotkey;

pivotkey=L->r[low].key;//用序列的第一个记录作枢轴记录

while(low

{

while(lowr[high].key>=pivotkey)//将比枢轴记录小的记录交换到低端

{

comparetimes++;

high--;

}

comparetimes++;

L->r[0]=L->r[low];

shifttimes++;

L->r[low]=L->r[high];

shifttimes++;

L->r[high]=L->r[0];

shifttimes++;

while(lowr[low].key<=pivotkey)//将比枢轴记录大的记录交换到高端

{

comparetimes++;

low++;

}

comparetimes++;

L->r[0]=L->r[low];

shifttimes++;

L->r[low]=L->r[high];

shifttimes++;

L->r[high]=L->r[0];

shifttimes++;

}

return(low);//返回枢轴所在位置

}

qSqList Quick2(qSqList L,long low,long high)//对顺序表L中的子序列L.r[low..high]作快速排序{

long pivot;

if(low

{

pivot=Quicksort(L,low,high);//将序列一分为二

Quick2(L,low,pivot-1);//对低位子表递归排序

Quick2(L,pivot+1,high);//对高位子表递归排序

}

return(L);

}

qSqList Quick(qSqList L)//对顺序表作快速排序

{

long low,high;

low=1;//将第一个数据所在位置定义为低位

high=L->length;//将最后一个数据所在位置定义为高位

L=Quick2(L,low,high);//对顺序表作快速排序

Print(L);

Print2(L);

return(L);

}

void TourSort(SqList *L,long n)//锦标赛排序

{

qSqList Lp;

long i=0,t=1,k=1,w;

while(t

{

t=(long)pow(2,i);

i++;

}

t=2*t;

Lp=(qSqList)malloc((sizeof(SqList)));

Lp->length=t-1;

for(i=t-1;i>=t/2;i--)

{

if(k>n)

Lp->r[i].key=MAXNUM;

else

{

Lp->r[i]=L->r[k];

}

shifttimes++;

k++;

}

i=t-1;

while(i!=1)

{

Lp->r[i/2]=Min1(Lp->r[i],Lp->r[i-1]);

i-=2;

comparetimes++;

shifttimes++;

}

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

{

L->r[i]=Lp->r[1];

shifttimes++;

w=1;

while(w

{

if(Lp->r[2*w].key==Lp->r[w].key)

w*=2;

else

w=2*w+1;

}

Lp->r[w].key=MAXNUM;//将其赋为最大值

shifttimes++;

if(w%2)

Lp->r[w/2]=Lp->r[w-1];

else

Lp->r[w/2]=Lp->r[w+1];

shifttimes++;

while(w!=1)

{

if(w%2)

Lp->r[w/2]=Min1(Lp->r[w],Lp->r[w-1]);

else

Lp->r[w/2]=Min1(Lp->r[w],Lp->r[w+1]);

comparetimes++;

shifttimes++;

w/=2;

}

}

Print(L);

Print2(L);

}

void Heapadjust(qSqList L,long s,long m)//调整L->[s]的关键字，使L->r[s..m]成为一个大顶堆{

long j;

struct node rc;

rc=L->r[s];

for(j=2*s;j<=m;j*=2)//沿key较大的接点向下筛选

{

if(jr[j].key,L->r[j+1].key))//j为key较大的记录的下标

{

j++;

comparetimes++;

}

if(!LT(rc.key,L->r[j].key))

{

comparetimes++;

break;

}

L->r[s]=L->r[j];//rc插入位置s

shifttimes++;

s=j;

}

L->r[s]=rc;//插入

shifttimes++;

}

qSqList Heap(qSqList L)//堆排序

{

long i;

for(i=L->length/2;i>0;--i)//把L建成大顶堆

Heapadjust(L,i,L->length);

for(i=L->length;i>1;--i)//将堆顶记录和当前未经排序子序列中最后一个记录交换

{

L->r[0]=L->r[1];

L->r[1]=L->r[i];

L->r[i]=L->r[0];

shifttimes=shifttimes+3;

Heapadjust(L,1,i-1);//将L重新调整为大顶堆

}

Print(L);

Print2(L);

return(L);

}

void Merge(qSqList L,int low,int m,int high)//将两个有序表R[low..m]he R[m+1..high]归并为一个有序表R[low,high]

{

int i=low,j=m+1,k=0;//k是temp的下标，i,j分别为第1，2段的下标

struct node *temp;

temp=(struct node*)malloc((high-low+1)*sizeof(struct node));//用于临时保存有序序列while(i<=m&&j<=high)//在第1段和第2段均未扫描完时循环

{

if(LT(L->r[j].key,L->r[i].key))//将第1段中的记录放入temp中

{

temp[k]=L->r[j];

j++;

k++;

}

else//将第2段中的记录放入temp中

{

temp[k]=L->r[i];

k++;

i++;

}

}

while(i<=m)//将第1段余下的部分复制到temp

{

temp[k]=L->r[i];

k++;

i++;

}

while(j<=high)//将第2段余下的部分复制到temp

{

temp[k]=L->r[j];

k++;

j++;

}

for(k=0,i=low;i<=high;i++,k++)//将temp复制回L中

{

L->r[i]=temp[k];

}

}

void MSort(qSqList L,int low,int high)//二路归并排序

{

int m;

if (low

{

m=(low+high)/2;

MSort(L,low,m);

MSort(L,m+1,high);

Merge(L,low,m,high);

}

}

void Merging(qSqList L)//归并排序

{

MSort(L,1,L->length);

Print2(L);

}

void Radixsort(qSqList L)//基数排序

{

int g,i,j,k,d=2;

struct node2 *p,*s,*t,*head[10],*tail[10];//定义各链队的首尾指针for(i=1;i<=L->length;i++) //建立链表

{

s = (struct node2*)malloc(sizeof(struct node2));

s->r.key = L->r[i].key;

s->r.num= L->r[i].num;

if(i==1)

{

t = s;

p = s;

g++;

}

else

{

t->next = s;

t = s;

g++;

}

t->next = NULL;

}

d=1;

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

{

for(j=0;j<10;j++)

{

head[j] = tail[j] = NULL;

} //初始化各链队首、尾指针

while(p!=NULL)//对于原链表中的每个结点循环{

k = p->r.key/d;

k = k%10;

if(head[k]==NULL)//进行分配

{

head[k]=p;

tail[k]=p;

}

else

{

tail[k]->next=p;

tail[k]=p;

}

p = p->next;//取下一个待排序的元素}

p=NULL;

for(j=0;j<10;j++)//对每一个链队循环

{

if(head[j]!=NULL)//进行搜集

{

if(p == NULL)

{

p = head[j];

t = tail[j];

}

else

{

t->next=head[j];

t = tail[j];

}

}

}

t->next=NULL;//最后一个结点的next置为空

d=d*10;

}

i=1;

while(p!=NULL)

{

L->r[i] = p->r;

i++;

p=p->next;

}

Print2(L);

}

char chmenu()//对排序方法进行选择{

char ch;

printf("\n\t请选择排序方法:"

"\n\t*************"

"\n\t1.Shell排序"

"\n\t2.Quick排序"

"\n\t3.锦标赛排序"

"\n\t4.堆排序"

"\n\t5.归并排序"

"\n\t6.基排序"

"\n\t7.结束"

"\n\t*************");

do{

printf("\n\tplease choose (1-7):");

getchar();

ch=getchar();

} while(!(ch>'0'&&ch<'8'));

return(ch);

}

void main()

{

int a=1;

FILE *fp;

char ch,filename[N];

qSqList L;

while(a)

{

printf("\n\t请输入读入文件名:");//输入要读入的文件名scanf("%s",filename);

if((fp=fopen(filename,"r"))==NULL)

{

printf("cannot open the file\n");

exit(0);

}

L=creat(filename);

while(1)

{

if((ch=chmenu())=='7')

break;

switch(ch)

{

case'1':

{

shifttimes=comparetimes=0;

shell(L);

}

break;

case'2':

{

shifttimes=comparetimes=0;

Quick(L);

}

break;

case'3':

{

shifttimes=comparetimes=0;

TourSort(L,L->length);

}

break;

case'4':

{

shifttimes=comparetimes=0;

Heap(L);

}

break;

case'5':

{

shifttimes=comparetimes=0;

Merging(L);

}

break;

case'6':

{

shifttimes=comparetimes=0;

Radixsort(L);

}

break;

}

}

printf("\n\t***************"

"\n\t1.继续读入文件"

"\n\t0.结束"

"\n\t***************");

do{

printf("\n\tplease choose (0-1):");

getchar();

scanf("%d",&a);

}while(!(a==1||a==0));

}

}

本文来源：https://www.bwwdw.com/article/ci8q.html