首页 | 新闻 | 新品 | 文库 | 方案 | 视频 | 下载 | 商城 | 开发板 | 数据中心 | 座谈新版 | 培训 | 工具 | 博客 | 论坛 | 百科 | GEC | 活动 | 主题月 | 电子展
返回列表 回复 发帖

C语言经典算法之各种排序法

C语言经典算法之各种排序法

#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);
}
返回列表