冒泡、快速排序算法比较程序.zip_快速排序算法_排序算法比较_数据结构课程设计

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