常用的五种排序算法

用C语言实现的五种排序算法
直接插入排序、折半排序、希尔排序、选择排序、冒泡排序程序如下:
#include<stdio.h>
#define MAXSIZE 20
typedef int KeyType;
typedef struct
{
    KeyType key;
    int otherinfo;
}RedType;
typedef struct
{
    RedType r[MAXSIZE+1];
    int length;
}SqList;
bool LT(KeyType a,KeyType b)
{
    if(a<b) return true;
    else return false;
}
void InsertSort(SqList &L)
{
    int i,j;
    for(i=2;i<=L.length;++i)
        if(LT(L.r[i].key,L.r[i-1].key))
        {
            L.r[0]=L.r[i];
            L.r[i]=L.r[i-1];
            for(j=i-2;LT(L.r[0].key,L.r[j].key);--j)
                L.r[j+1]=L.r[j];
            L.r[j+1]=L.r[0];
        }
}
void BInsertSort(SqList &L)
{
    int i,j,m,low,high;
    for(i=2;i<=L.length;i++)
    {
        L.r[0]=L.r[i];
        low=1;high=i-1;
        while(low<=high)
        {
            m=(low+high)/2;
            if(LT(L.r[0].key,L.r[m].key)) high=m-1;
            else low=m+1;
        }
        for(j=i-1;j>=high+1;--j) L.r[j+1]=L.r[j];
        L.r[high+1]=L.r[0];
    }
}
void ShellInsert(SqList &L,int 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[0]=L.r[i];
            for(j=i-dk;j>0 && LT(L.r[0].key,L.r[j].key);j-=dk)
                L.r[j+dk]=L.r[j];
            L.r[j+dk]=L.r[0];
        }
}
void ShellSort(SqList &L,int dlta[],int t)
{
    int k;
    for(k=0;k<t;++k)
        ShellInsert(L,dlta[k]);
}
int SelectMinKey(SqList &L,int i)
{
    int j,min;
    min=i;
    for(j=i+1;j<=L.length;j++)
        if(L.r[j].key<L.r[min].key) min=j;
    return min;
}
void SelectSort(SqList &L)
{
    int i,j;
    for(i=1;i<L.length;++i)
    {
        j=SelectMinKey(L,i);
        if(i!=j)
        {
            L.r[0]=L.r[i];
            L.r[i]=L.r[j];
            L.r[j]=L.r[0];
        }
    }
}
void BubbleSort(SqList &L)
{
    int i,j;
    for(i=1;i<L.length;i++)
    {
        for(j=1;j<L.length-i+1;j++)
            if(L.r[j].key>L.r[j+1].key)
            {
                L.r[0]=L.r[j];
                L.r[j]=L.r[j+1];
                L.r[j+1]=L.r[0];
            }
    }
}
void Inputnum(int n,SqList &L)
{
    int i;
    for(i=1;i<n+1;i++)
        scanf("%d",&L.r[i].key);
}
void Outputnum(int n,SqList &L)
{
    int i;
    for(i=1;i<n+1;i++)
        printf("%d\t",L.r[i].key);
    printf("\n");
}
void main()
{
    SqList L;
    int method,i,t;
    int dlta[10];
    printf("Please input the length of numbers:");
    scanf("%d",&L.length);
    printf("Please input %d numbers",L.length);
    Inputnum(L.length,L);
    printf("The numbers you have input are:\n");
    Outputnum(L.length,L);
    printf("\nSorting Methods:\n--------------------------------");
    printf("\n1.Straight Insertion Sort\n2.Binary Insertion Sort\n");
    printf("3.Shell's Sort\n4.Selection Sort\n5.Bubble Sort\n");
    printf("--------------------------------\n");
    printf("Please select the method of sorting:");
    scanf("%d",&method);
    switch(method)
    {
        case 1:
            InsertSort(L);
            printf("After insert Sorting,the numbers are:\n");
            break;
        case 2:
            BInsertSort(L);
            printf("After binary insert sorting,the numbers are:\n");
            break;
        case 3:
            printf("Please input the quantity of Sorting:");
            scanf("%d",&t);
            printf("Please input %d increments:",t);
            for(i=0;i<t;i++) scanf("%d",&dlta[i]);
            ShellSort(L,dlta,t);
            printf("After Shell's sorting,the numbers are:\n");
            break;
        case 4:
            SelectSort(L);
            printf("After select sorting,the numbers are:\n");
            break;
        case 5:
            BubbleSort(L);
            printf("After bubble sorting,the numbers are:\n");
            break;
    }
    Outputnum(L.length,L);
}




文章来自: 本站原创
引用通告: 查看所有引用 | 我要引用此文章
Tags: 数据结构 C语言
相关日志:
评论: 0 | 引用: 0 | 查看次数: -
发表评论
昵 称:
密 码: 游客发言不需要密码.
内 容:
验证码: 验证码
选 项:
虽然发表评论不用注册,但是为了保护您的发言权,建议您注册帐号.