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

分析：

<1>多次运行之后统计，从乱序的时间消耗来看，基本符合理论分析 <2>由于加入了统计次数的代码，势必增加时间开销，这样统计出来的时间将有一定的误差。

假若比较次数和移动次数相差较多，则将产生较大的实验误差。 4. 总结

（1） 调试时出现的问题及解决的方法

在调试过程中，我遇到了一些困难。例如：循环的条件控制不正确。通过云阅读书本，我发现，错误的原因是没能正确理解概念。经过反复的尝试，不断对知识的理解，最终我将错误改正。

（2） 心得体会

通过此次实验，我对各这种排序有了更加直观和深刻的认识，对书本上介绍的各种算法有了更熟练的掌握。

在编程的过程中，我也遇到了一些困难，多是有关c++语法等方面的困难，通过不断的调试与查询资料，我对c++的一些语法更加了解，这对我以后的编程有很大的帮助。

（3） 下一步的改进

本程序代码设计时运用了递归的调用方式，效率还可以通过将其转换为栈模拟的方

式得以提高。

源代码：由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);

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);

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

/********************************************************简单插入排序