实验报告实验四排序

数据结构实验报告

实验名称： 实验四——题目二 学生姓名： 武文齐 班 级： 2011211113 班内序号： 05 学 号： 2011210363

1．实验要求

使用简单数组实现下面各种排序算法，并进行比较。 排序算法：

1、插入排序 2、希尔排序 3、冒泡排序 4、快速排序 5、简单选择排序 6、堆排序（选作） 7、归并排序（选作） 8、基数排序（选作） 9、其他

要求：

1、测试数据分成三类：正序、逆序、随机数据

2、对于这三类数据，比较上述排序算法中关键字的比较次数和移动次数（其中关键字交换计为3次移动）。

3、对于这三类数据，比较上述排序算法中不同算法的执行时间，精确到微秒（选作）

4、对2和3的结果进行分析，验证上述各种算法的时间复杂度

编写测试main()函数测试线性表的正确性。

第1页

2. 程序分析

2.1代码

（包括三个cpp文件） //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();

第2页

}

obj.runtime[i][j]=obj.endTime-obj.startTime;

/****************************主调函数*********************************/ int main(void) {

cout<<\程序说明：\\n1、默认产生10个随机数，如需加大数据量，请修改常量Max;\\n2、

默认打印排序的结果以显示算法正确与否，如果想不打印，请注释相关语句。\\n\\n\

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++) { }

obj.RecordTimes(0);

/*************************顺序序列*********************************/

第3页

Statistics(obj,i,0);

cout<

memcpy(obj.pRandom1,obj.pRandom2,(Max+1)*sizeof(long int));

//如果不输出各排序结果，请注释掉此两行

}

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++) { }

obj.RecordTimes(4);

/************************统计排序数据******************************/ obj.PrintStatistics(funcName);

Statistics(obj,i,2);

memcpy(obj.pRandom1,obj.pRandom2,(Max+1)*sizeof(long int));

return 0;

//Sort.h

第4页

const int Max =10; 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);

第5页

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库实验报告实验四排序在线全文阅读。