北邮数据结构实验 第三次实验 排序

源代码：由3部分组成 //main.cpp

#include using namespace std; #include\#include #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 #include #include #include #include #include #include #include using namespace std;

/**********************************************************构造函数**********************************************************************/ 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页

序

序