当前位置：首页 > 北邮数据结构实验 第三次实验 排序
源代码：由3部分组成 //main.cpp
#include
static int (Sort::*pFunction[7])(long int [])={&Sort::InsertSort,&Sort::ShellSort,&Sort::BubbleSort,&Sort::QuickSort,&Sort::SelectSort,&Sort::HeapSort,&Sort::MergeSort}; char *funcName[7]={\、插入排序:\、希尔排序:\、冒泡排序:\、快速排序:\、选择排序:\、堆 排 序:\、归并排序:\
/*****************************统计时间函数*****************************/ void Statistics(Sort &obj,int i,int j) {
obj.startTime=obj.GetNowTime(); (obj.*pFunction[i])(obj.pRandom1); obj.endTime=obj.GetNowTime();
obj.runtime[i][j]=obj.endTime-obj.startTime; }
/****************************主调函数*********************************/ int main() {
Sort obj;
obj.CreateData();
memcpy(obj.pRandom1,obj.pRandom2,(Max+1)*sizeof(long int)); int i(0),j(0);
/*************************乱序序列*********************************/ obj.SetTimesZero(); for(i=0;i<7;i++) {
Statistics(obj,i,0);
cout< memcpy(obj.pRandom1,obj.pRandom2,(Max+1)*sizeof(long int)); } obj.RecordTimes(0); /*************************顺序序列*********************************/ obj.SetTimesZero(); for( i=0;i<7;i++) Statistics(obj,i,1); 第13页 obj.RecordTimes(2); /*************************逆序序列*********************************/ obj.SetTimesZero(); for(i=1;i<=Max;i++) obj.pRandom2[i]=obj.pRandom1[Max+1-i]; memcpy(obj.pRandom1,obj.pRandom2,(Max+1)*sizeof(long int)); for(i=0;i<7;i++) { Statistics(obj,i,2); memcpy(obj.pRandom1,obj.pRandom2,(Max+1)*sizeof(long int)); } obj.RecordTimes(4); /************************统计排序数据******************************/ obj.PrintStatistics(funcName); return 0; } //Sort.h const int Max =50; class Sort { public: Sort(); ~Sort(); void CreateData(void); int InsertSort(long int []); int ShellSort(long int []); int BubbleSort(long int []); int QuickSort(long int []); int QuickSortRecursion(long int [], int ,int); int QuickSortPatition(long int [], int , int ); int SelectSort(long int []); int HeapSort(long int []);//堆排序 void HeapSortSift(long int [], int , int );//筛选 int MergeSort(long int []); void Merge(long int [],long int [], int , int , int );//归并排序 void MergePass(long int [],long int [] , int ); long double GetNowTime(void); void PrintArray(long int*); void SetTimesZero(void); void RecordTimes(int); 第14页 friend void Statistics(Sort &,int ,int); void PrintStatistics(char *[]); friend int main(void); private: long int *pRandom1; long int *pRandom2; long double runtime[7][3]; int comparetimes[7]; int movetimes[7]; int timestable[7][6]; long double startTime,endTime; }; //Function.cpp #include\#include /**********************************************************构造函数**********************************************************************/ Sort::Sort() { memset(timestable,0,sizeof(int)*7*6); } /***********************************************************构造数组**********************************************************************/ void Sort::CreateData() { pRandom1=new long int[Max+1]; pRandom2=new long int[Max+1]; srand((unsigned)time(NULL)); for(int i = 1; i <= Max;i++ ) pRandom2[i]=rand(); cout<<\随机乱序数组如下：\\n\ //输出原始数组 PrintArray(pRandom2); } /********************************************************简单插入排序 第15页 *******************************************************************/ int Sort::InsertSort(long int parray[]) { int j=0; for(int i =2; i <= Max;i++) { parray[0]=parray[i]; comparetimes[0]++;//比较次数统计 for(j=i-1;parray[0] parray[j+1]=parray[j]; movetimes[0]++;//移动次数统计 } parray[j+1]=parray[0]; movetimes[0]+=2; } return 0; } /**********************************************************希尔排***********************************************************************/ int Sort::ShellSort(long int parray[]) { int j=0; for(int d=Max/2;d>=1;d/=2) { for(int i=d+1;i<=Max;i++) { parray[0]=parray[i]; comparetimes[1]++; for(j=i-d;j>0 && parray[0] parray[j+d]=parray[j]; movetimes[1]++; } parray[j+d]=parray[0]; movetimes[1]+=2; } } return 0; } /**********************************************************冒泡排***********************************************************************/ int Sort::BubbleSort(long int parray[]) { 第16页 序 序搜索更多关于： 北邮数据结构实验 第三次实验 排序 的文档
本文作者：...共分享92篇相关文档
