# 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();
}
