各种排序算法

[c++]代码库
#define MAXSIZE 20
#define LT(a,b) ((a)<(b))
typedef int KeyType;
typedef int InfoType;
typedef struct
{
    KeyType key;
    InfoType otherinfo;
} RedType;
typedef struct
{
    RedType r[MAXSIZE+1];
    int length;
} SqList;
 
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];
            for ( j=i-1; 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;
    int low,high,m;
    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];
    }
}
 
/* QuickSort related function */
int Partition ( SqList *L,int low,int high )
{
    int pivotkey;
    L->r[0]=L->r[low];
    pivotkey=L->r[low].key;
    while ( low<high )
    {
        while ( low<high&&L->r[high].key>=pivotkey ) --high;
        L->r[low]=L->r[high];
        while ( low<high&&L->r[low].key<=pivotkey ) ++low;
        L->r[high]=L->r[low];
    }
    L->r[low]=L->r[0];
    return low;
}
void QSort ( SqList *L,int low,int high )
{
    int pivotloc;
    if ( low<high )
    {
        pivotloc=Partition ( L,low,high );
        QSort ( L,low,pivotloc-1 );
        QSort ( L,pivotloc+1,high );
    }
}
void QuickSort ( SqList *L )
{
    QSort ( L,1,L->length );
}                    /* End QuickSort related function*/
 
/*SelectSort related function */
int SelectMinKey ( SqList L,int i )
{
    int k;
    int j;
    k=i;
    for ( j=i; j<L.length+1; j++ )
        if ( L.r[k].key>L.r[j].key )
            k=j;
    return k;
}
void SelectSort ( SqList *L )
{
    RedType t;
    int i,j;
    for ( i=1; i<L->length; ++i )
    {
        j=SelectMinKey ( *L,i );
        if ( i!=j )
        {
            t=L->r[i];
            L->r[i]=L->r[j];
            L->r[j]=t;
        }
    }
}           /*End SelectSort related function */
 
 
typedef SqList HeapType;
void HeapAdjust ( HeapType *H,int s,int m )
{
    RedType rc;
    int j;
    rc=H->r[s];
    for ( j=2*s; j<=m; j*=2 )
    {
        if ( j<m&&LT ( H->r[j].key,H->r[j+1].key ) ) ++j;
        if ( !LT ( rc.key,H->r[j].key ) ) break;
        H->r[s]=H->r[j];
        s=j;
    }
    H->r[s]=rc;
}
void HeapSort ( HeapType *H )
{
    RedType t;
    int i;
    for ( i=H->length/2; i>0; --i )
        HeapAdjust ( H,i,H->length );
    for ( i=H->length; i>1; --i )
    {
        t=H->r[1];
        H->r[1]=H->r[i];
        H->r[i]=t;
        HeapAdjust ( H,1,i-1 );
    }
}
 
main()
{
    int a[]={49,38,65,97,76,13,27,49};
    int i,k;
    SqList s;
    printf ( "\nThe record to be sort:\n" );
    for ( i=1; i<9; i++ )
    {
        s.r[i].key=a[i-1];
        printf ( "%d  ",a[i-1] );
    }
    s.length=i-1;
    printf ( "\n\t1,InsertSort\n\t2,BInsertSort\n\t3,QuickSort\n\t4,SelectSort\n" );
    printf ( "\t5,HeapSort\n\tPress 1..5 to select a function\n" );
    scanf ( "%d",&k );
    switch ( k )
    {
    case 1:
        InsertSort ( &s );
        break;
    case 2:
        BInsertSort ( &s );
        break;
    case 3:
        QuickSort ( &s );
        break;
    case 4:
        SelectSort ( &s );
        break;
    case 5:
        HeapSort ( &s );
        break;
    default:
        printf ( "No function which you select.\n" );
    }
    printf ( "\nThe records be sorted:\n" );
    for ( i=1; i<9; i++ )
        printf ( "%d  ",s.r[i].key );
    printf ( "\n\n\tPress any key to exit.\n" );
    getch();
}
用户注册

用户登录

发表随想

该用户最新代码

编程随想

[c++]代码库

网友评论 (发表评论)

回复评论

发表评论：

评论须知：

扫码下载

输入口令后可复制整站源码
