|
- UID
- 852722
|
#include<stdio.h>
#include<stdlib.h>
struct node
{
intkey;
}r[20];
struct rnode
{
intkey;
intpoint;
};
main()
{
voidprint(struct node a[20],int n);
intcreat();
voidshell(struct node a[20],int n);
inthoare(struct node a[20],int l,int h);
voidquick1(struct node a[20],int n);
voidquick2(struct node a[20],int l,int h);
voidheap(struct node a[20],int i,int m);
voidheapsort(struct node a[20],int n);
voidmerges(struct node a[20],struct node a2[20],int h1,int mid,int h2);
voidmergepass(struct node a[20],struct node a2[20],int l,int n);
voidmergesort(struct node a[20],int n);
intyx(int m,int i);
intradixsort(struct rnode a[20],int n);
intnum,l,h,c;
structrnode s[20];
c=1;
while(c!=0)
{
printf(" 主菜单 \n");
printf(" 1 输入关键字，以-9999表示结束。\n");
printf(" 2 希尔排序 \n");
printf(" 3 非递归的快速排序 \n");
printf(" 4 递归的快速排序 \n");
printf(" 5 堆排序 \n");
printf(" 6 归并排序 \n");
printf(" 7 基数排序 \n");
printf("输入选择 (1--7,0表示结束): ");
scanf("%d",&c);
switch(c)
{
case1:num=creat();print(r,num);break;
case2:shell(r,num);print(r,num);break;
case3:quick1(r,num);print(r,num);break;
case4:l=0;h=num-1;quick2(r,l,h);
printf("outputquick2sort result:\n");
print(r,num);break;
case5:heapsort(r,num);break;
case6:mergesort(r,num);print(r,num);break;
case7:radixsort(s,num);
}
}
}//main end
void print(struct node a[20],int n)
{
inti;
for(i=0;i<n;i++)
printf("%5d",a.key);
printf("\n");
}//print end
int creat()
{
inti,n;
n=0;
printf("inputkeys");
scanf("%d",&i);
while(i!=-9999)
{
r[n].key=i;
n++;
scanf("%d",&i);
}
return(n);
}//creat end
void shell(struct node a[20],int n)//希尔排序
{
inti,j,k;
for(i=n;i>=1;i--)
a.key=a[i-1].key;
k=n/2;
while(k>=1)
{
for(i=k+1;i<=n;i++)
{
a[0].key=a.key;
j=i-k;
while((a[j].key>a[0].key)&&(j>=0))
{
a[j+k].key=a[j].key;
j=j-k;
}
a[j+k]=a[0];
}
k=k/2;
}
for(i=0;i<n;i++)
a.key=a[i+1].key;
printf("输出希尔排序的结果:\n");
}//shell end
////////////////////快速排序///////////////////////////
int hoare(struct node a[20],int l,int h)//分区处理函数
{
inti,j;
structnode x;
i=l;
j=h;
x.key=a.key;
do
{
while((i<j)&&(a[j].key>=x.key))
j--;
if(i<j)
{
a.key=a[j].key;
i++;
}
while((i<j)&&(a.key<=x.key))
i++;
if(i<j)
{
a[j].key=a.key;
j--;
}
}while(i<j);
a.key=x.key;
return(i);
}//hoare end
void quick1(struct node a[20],int n)
{
inti,l,h,tag,top;
ints[20][2];
l=0;h=n-1;tag=1;top=0;
do
{
while(l<h)
{
i=hoare(a,l,h);
top++;
s[top][0]=i+1;
s[top][1]=h;
h=h-1;
}
if(top==0)
tag=0;
else
{
l=s[top][0];
h=s[top][1];
top--;
}
}while(tag==1);
printf("输出非递归快速排序结果:\n");
}//quick end
void quick2(struct node a[20],int l,inth)//递归的快速排序
{
inti;
if(l<h)
{
i=hoare(a,l,h);
quick2(a,l,i-1);
quick2(a,i+1,h);
}
}//quick2 end
////////////////////快速排序结束////////////////////////
////////////////////堆排序函数//////////////////////////
void heap(struct node a[20],int i,int m)//调整堆的函数
{
structnode x;
intj;
x.key=a.key;
j=2*i;
while(j<=m)
{
if(j<m)
if(a[j].key>a[j+1].key)
j++;
if(a[j].key<x.key)
{
a.key=a[j].key;
i=j;
j=2*i;
}
else
j=m+1;
}
a.key=x.key;
}//heap end
void heapsort(struct node a[20],int n)//堆排序的主体函数
{
inti,v;
structnode x;
for(i=n;i>0;i--)
a.key=a[i-1].key;
for(i=n/2;i>=1;i--)
heap(a,i,n);
printf("输出堆排序结果:\n");
for(v=n;v>=2;v--)
{
printf("%5d",a[1].key);
x.key=a[1].key;
a[1].key=a[v].key;
a[v].key=x.key;
heap(a,1,v-1);
}
printf("%5d",a[1].key);
for(i=0;i<n;i++)
a.key=a[i+1].key;
}//heapsort end
/////////////////堆排序函数结束///////////////////
//////////////////归并函数////////////////////////
void merges(struct node a[20],struct nodea2[20],int h1,int mid,int h2)
//归并排序的核心算法
{
inti,j,k;
i=h1;j=mid+1;k=h1-1;
while((i<=mid)&&(j<=h2))
{
k=k+1;
if(a.key<=a[j].key)
{
a2[k].key=a.key;
i++;
}
else
{
a2[k].key=a[j].key;
j++;
}
}
while(i<=mid)
{
k++;
a2[k].key=a.key;
i++;
}
while(j<=h2)
{
k++;
a2[k].key=a[j].key;
i++;
}
}//merges end
void mergepass(struct node a[20],structnode a2[20],int l,int n)
//一趟归并
{
intj,i,h1,mid,h2;
i=0;
while((n-i)>=2*l)
{
h1=i;
mid=h1+l-1;
h2=i+2*l-1;
merges(a,a2,h1,mid,h2);
i=i+2*l;
}
if((n-i)<=l)
for(j=i;j<=n;j++)
a2[j].key=a[j].key;
else
{
h1=i;
mid=h1+l-1;
h2=n-1;
merges(a,a2,h1,mid,h2);
}
}//mergepass end
void mergesort(struct node a[20],int n)
{
intl;
structnode a2[20];
l=1;
while(l<n)
{
mergepass(a,a2,l,n);
l=2*l;
mergepass(a2,a,l,n);
l=2*l;
}
printf("输出归并排序的结果:\n");
}//mergesort end
///////////////归并函数结束///////////////
///////////////基数排序///////////////////
int yx(int m,int i)//分离关键字倒数第i位有效数字的算法
{
intx;
switch(i)
{
case1:x=m%10;break;
case2:x=(m%100)/10;break;
case3:x=(m%1000)/100;break;
case4:x=(m%10000)/1000;break;
}
return(x);
}//yx end
int radixsort(struct rnode a[20],int n)
{
intf[11],e[11],i,j,k,l,p,d,t;
for(i=1;i<=n;i++)
{
a.key=r[i-1].key;
a.point=i+1;
}
a[n].point=0;
p=1;
printf("输出关键字有效位数d\n");
scanf("%d",&d);
printf("输出基数排序的结果:\n");
for(i=1;i<=d;i++)
{
for(j=0;j<=10;j++)
{
f[j]=0;
e[j]=0;
}
while(p!=0)
{
k=yx(a[p].key,i);
if(f[k]==0)
{
f[k]=p;
e[k]=p;
}
else
{
l=e[k];
a[l].point=p;
e[k]=p;
}
p=a[p].point;
}
j=0;
while(f[j]==0)
j++;
p=f[j];t=e[j];
while(j<10)
{
j++;
while((j<10)&&(f[j]==0))
j++;
if(f[j]!=0)
{
a[t].point=f[j];
t=e[j];
}
}
a[t].point=0;
t=p;
while(t!=0)
{
printf("%5d",a[t].key);
t=a[t].point;
}
printf("\n");
}
return(p);
} |
|
