#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    輸入關(guān)鍵字，以-9999表示結(jié)束。\n");
        printf("   2    希爾排序                     \n");
        printf("   3    非遞歸的快速排序             \n");
        printf("   4    遞歸的快速排序               \n");
        printf("   5    堆排序                       \n");
        printf("   6    歸并排序                     \n");
        printf("   7    基數(shù)排序                     \n");
        printf(" 輸入選擇    (1--7,0表示結(jié)束):         ");
        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("輸出希爾排序的結(jié)果:\n");
}//shell end

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

int hoare(struct node a[20],int l,int h)//分區(qū)處理函數(shù)
{
    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("輸出非遞歸快速排序結(jié)果:\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

////////////////////快速排序結(jié)束////////////////////////

////////////////////堆排序函數(shù)//////////////////////////

void heap(struct node a[20],int i,int m)//調(diào)整堆的函數(shù)
{
    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)//堆排序的主體函數(shù)
{
    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("輸出堆排序結(jié)果:\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

/////////////////堆排序函數(shù)結(jié)束///////////////////

//////////////////歸并函數(shù)////////////////////////

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("輸出歸并排序的結(jié)果:\n");
}//mergesort end

///////////////歸并函數(shù)結(jié)束///////////////

///////////////基數(shù)排序///////////////////

int yx(int m,int i)//分離關(guān)鍵字倒數(shù)第i位有效數(shù)字的算法
{
    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("輸出關(guān)鍵字有效位數(shù) d\n");
    scanf("%d",&d);
    printf("輸出基數(shù)排序的結(jié)果:\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);
}

標(biāo)簽：

版權(quán)申明：本站文章部分自網(wǎng)絡(luò)，如有侵權(quán)，請聯(lián)系：west999com@outlook.com
特別注意：本站所有轉(zhuǎn)載文章言論不代表本站觀點(diǎn)！
本站所提供的圖片等素材，版權(quán)歸原作者所有，如需使用，請與原作者聯(lián)系。