+

数据结构课程设计：冒泡、快速排序的比较

# include "stdio.h"
# include "stdlib.h"
# include "string.h"
# include "time.h"


# define   MAXSIZE   200    /*可排序表的长度*/
# define   TRUE      1
# define   FALSE     0

typedef  int  BOOL;

typedef struct StudentData
{    
    int num;             /* this is a key word*/
}Data;


typedef struct LinkList  /*建立一个顺序表*/
{
    int  Length;
    Data Record[MAXSIZE];/*表的长度*/
}LinkList;

int  RandArray[MAXSIZE];

/******************随机生成函数************************/

void  RandomNum()
{
    int i;
    srand((int)time( NULL ));
    for(i=0; i<MAXSIZE; i++)   
    RandArray[i]=(int)rand();
    return;
}

/******************************************************/

void InitLinkList(LinkList* L)   /*建立的顺序表*/
{
    int i;
    memset(L,0,sizeof(LinkList));
    RandomNum();
    for(i=0; i<MAXSIZE; i++)
    L->Record[i].num=RandArray[i];
    L->Length=i;
}

BOOL LT(int i, int j,int* CmpNum)   /*若表中第i个元素小于第j个元素，则返回True，否则Flase*/
{
    (*CmpNum)++;    /*关键字比较次数加1*/
    if (i<j) return TRUE;
    return FALSE;
}

void  Display(LinkList* L)   /*显示可排序表*/
{
    FILE* f;
    int i;
    if((f=fopen("SortRes.doc","w"))==NULL)
    {
        printf("can''t open file\n");
        exit(0);
    }
    for (i=0; i<L->Length; i++)
    fprintf(f,"%d\n",L->Record[i].num);
    fclose(f);
}


/****************冒泡排序****************************/
void BubbleSort(LinkList* L, int* CmpNum, int* ChgNum)  /*进行冒泡排序，返回关键字比较次数和移动次数*/
{
    int i,j;
    Data temp;
    for (i=0; i<MAXSIZE-1;i++)
    {
        for(j=0; j<MAXSIZE-i-1;j++)
        {
        if(!LT(L->Record[j].num,L->Record[j+1].num,CmpNum))
        {
            (*ChgNum)++;
             memcpy(&temp,&L->Record[j],sizeof(Data));
             memcpy(&L->Record[j],&L->Record[j+1],sizeof(Data));
             memcpy(&L->Record[j+1],&temp,sizeof(Data));
        }
        }
    }
}


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

int  Partition (LinkList* L, int low, int high, int* CmpNum, int* ChgNum)   /*进行快速排序，返回关键字比较次数和移动次数*/
{
    Data  Temp;
    int   PivotKey;
    memcpy(&Temp,&L->Record[low],sizeof(Data));
    PivotKey=L->Record[low].num;
    while (low < high)
    {
        while (low<high && L->Record[high].num >= PivotKey)
        {
            high--;
            (*CmpNum)++;
        }
        (*ChgNum)++;
        memcpy(&L->Record[low],&L->Record[high],sizeof(Data));
        while (low<high && L->Record[low].num <= PivotKey) 
        {
            low++;
            (*CmpNum)++;
        }
        (*ChgNum)++;
        memcpy(&L->Record[high],&L->Record[low],sizeof(Data));
    }
    memcpy(&L->Record[low],&Temp,sizeof(Data));
    return  low;
}


void  QSort (LinkList* L, int low, int high, int* CmpNum, int* ChgNum)
{
    int    PivotLoc=0;
    if (low < high)
    {
        PivotLoc=Partition(L,low,high,CmpNum,ChgNum);
        QSort(L,low,PivotLoc-1,CmpNum,ChgNum);
        QSort(L,PivotLoc+1,high,CmpNum,ChgNum);
    }
}

void  QuickSort (LinkList* L, int* CmpNum, int* ChgNum)
{
    QSort(L,0,L->Length-1,CmpNum,ChgNum);
}

/*********************************************/

void  SelectSort()
{
    printf("\n      1. BubbleSort.");
    printf("\n      2. QuickSort.");
    printf("\n \t\t\t\t   Please Select Num:");
}
/*********************************************/ 


void main()
{   
    int select=0;
    int CmpNum[6],ChgNum[6];
    LinkList  L;
    InitLinkList(&L);

    memset(CmpNum,0,sizeof(CmpNum));
    memset(ChgNum,0,sizeof(ChgNum));
    
    SelectSort();
    scanf("%d",&select);
    switch (select)
    {
     case    1:
               BubbleSort(&L,&CmpNum[select],&ChgNum[select]);
               printf("\tBubbleSort:");
               printf("\n\n\tCompare number=%d\tChange number=%d",CmpNum[select],ChgNum[select]);
               break;

    case    2:
               QuickSort(&L,&CmpNum[select],&ChgNum[select]);
               printf("\tQuickSort:");
               printf("\n\n\tCompare number=%d\tChange number=%d",CmpNum[select],ChgNum[select]);
               break;
   
    default:
               printf("\n Input  error !");
    }
    
    Display(&L);
    printf("\n\n\tTest over, please press enter!\n");
    getchar();
    getchar();
}