#include<stdio.h>
#include<stdlib.h>
struct node
{
int key;
}r[20];

struct rnode
{
int key;
int point;
};

main()
{
void print(struct node a[20],int n);
int creat();
void shell(struct node a[20],int n);
int hoare(struct node a[20],int l,int h);
void quick1(struct node a[20],int n);
void quick2(struct node a[20],int l,int h);
void heap(struct node a[20],int i,int m);
void heapsort(struct node a[20],int n);
void merges(struct node a[20],struct node a2[20],int h1,int mid,int h2);
void mergepass(struct node a[20],struct node a2[20],int l,int n);
void mergesort(struct node a[20],int n);
int yx(int m,int i);
int radixsort(struct rnode a[20],int n);
int num,l,h,c;
struct rnode 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)
        {
case 1:num=creat();print(r,num);break;
case 2:shell(r,num);print(r,num);break;
case 3:quick1(r,num);print(r,num);break;
case 4:l=0;h=num-1;quick2(r,l,h);
            printf("output quick2sort result:\n");
            print(r,num);break;
case 5:heapsort(r,num);break;
case 6:mergesort(r,num);print(r,num);break;
case 7:radixsort(s,num);
        }
    }
}//main end

void print(struct node a[20],int n)
{
int i;
for(i=0;i<n;i++)
        printf("%5d",a[i ].key);
    printf("\n");
}//print end

int creat()
{
int i,n;
    n=0;
    printf("input keys");
    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)//希尔排序
{
int i,j,k;
for(i=n;i>=1;i--)
        a[i].key=a[i-1].key;
    k=n/2;
while(k>=1)
    {
for(i=k+1;i<=n;i++)
        {
            a[0].key=a[i].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[i].key=a[i+1].key;
    printf("输出希尔排序的结果:\n");
}//shell end

////////////////////快速排序///////////////////////////

int hoare(struct node a[20],int l,int h)//分区处理函数
{
int i,j;
struct node x;
    i=l;
    j=h;
    x.key=a[i].key;
do
    {
while((i<j)&&(a[j].key>=x.key))
            j--;
if(i<j)
        {
            a[i].key=a[j].key;
            i++;
        }
while((i<j)&&(a[i].key<=x.key))
            i++;
if(i<j)
        {
            a[j].key=a[i].key;
            j--;
        }
    }while(i<j);
    a[i].key=x.key;
return(i);
}//hoare end

void quick1(struct node a[20],int n)
{
int i,l,h,tag,top;
int s[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,int h)//递归的快速排序
{
int i;
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)//调整堆的函数
{
struct node x;
int j;
    x.key=a[i].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[i].key=a[j].key;
            i=j;
            j=2*i;
        }
else
            j=m+1;
    }
    a[i].key=x.key;
}//heap end

void heapsort(struct node a[20],int n)//堆排序的主体函数
{
int i,v;
struct node x;
for(i=n;i>0;i--)
        a[i].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[i].key=a[i+1].key;
}//heapsort end

/////////////////堆排序函数结束///////////////////

//////////////////归并函数////////////////////////

void merges(struct node a[20],struct node a2[20],int h1,int mid,int h2)
//归并排序的核心算法
{
int i,j,k;
    i=h1;j=mid+1;k=h1-1;
while((i<=mid)&&(j<=h2))
    {
        k=k+1;
if(a[i].key<=a[j].key)
        {
            a2[k].key=a[i].key;
            i++;
        }
else
        {
            a2[k].key=a[j].key;
            j++;
        }
    }
while(i<=mid)
    {
        k++;
        a2[k].key=a[i].key;
        i++;
    }
while(j<=h2)
    {
        k++;
        a2[k].key=a[j].key;
        i++;
    }
}//merges end

void mergepass(struct node a[20],struct node a2[20],int l,int n)
//一趟归并
{
int j,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)
{
int l;
struct node 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位有效数字的算法
{
int x;
switch(i)
    {
case 1:x=m%10;break;
case 2:x=(m%100)/10;break;
case 3:x=(m%1000)/100;break;
case 4:x=(m%10000)/1000;break;
    }
return(x);
}//yx end

int radixsort(struct rnode a[20],int n)
{
int f[11],e[11],i,j,k,l,p,d,t;
for(i=1;i<=n;i++)
    {
        a[i].key=r[i-1].key;
        a[i].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 
                       
                    
                    
 
                      




鲜花




握手




雷人




路过




鸡蛋