数据结构实验报告-排序

2023级数据构造试验报告学生姓名：班级：学号：日 期：2023年12月6日试验要求试验目的法的优劣，以及各种算法使用的状况。试验内容排序算法：1、插入排序2、希尔排序3、冒泡排序4、快速排序5、简洁选择排序6、堆排序〔选作〕7、归并排序〔选作〕8、基数排序〔选作〕9、其他程序分析存储构造存储构造:挨次存储构造示意图如下:核心算法思想：利用教材表达的根本算法思想，实现七种排序算法，统计其运行相关数据。将七种排序函数入口地址作为函数指针数组，实现快速调用和统计。使得程序代码可读性增、构造更加优化。关键算法思想描述和实现：1：实现七种算法的根本排序功能。1部记录排序完毕。2、希尔排序：先将整个序列分割成假设干个子列，分别在各个子列中运用直接插入排序，待整个序列根本有序时，再对全体记录进展一次直接插入排序。3、冒泡排序：两两比较相邻记录的关键码，假设反序则交换，直到没有反序记录为止。4、快速排序：首先选择一个基准，将记录分割为两局部，左支小于或等于基准，右支则大于基准，然后对两局部重复上述过程，直至整个序列排序完成。5、选择排序：从待排序的记录序列中选择关键码最小〔或最大〕的记录并将它与序列中〔或最大〕的记录并将它与序列中的其次个记录交换位置6、堆排序：通过建立大根堆或者小根堆，取出根节点，反复调整堆使之保持大根堆或者小根堆，直至最终序列有序。7止。C++实现：参看源代码的七个排序函数。2：猎取当前系统时间，准确到微秒，分别在代码运行前后调用记录前后时间，再相减即可得到代码运行时间。此处调用函数QueryPerformanceCounter用于得到高精度计时器的值。C++实现：longdoubleSort::GetNowTime(void){LARGE_INTEGER LONG64QPart;QueryPerformanceCounter(&litmp);QPart=litmp.QuadPart;return(longdouble)QPart;}3：试图寻求最简短的代码以实现多达七种排序算法的简洁调用统计。假设设计不合理，将使得主调函数的调用代码冗长，可读性变差。承受以下三种方法实现：①使用函数指针数组，分别指向各排序函数的入口地址，然后在Statistics函数中加以调用，使得排序函数运行在统计时间函数之间，这样使用一个for语句即可实现七种算法的一次性调用、时间统计、移动次数和比较次数统计。C++实现：voidStatistics(Sort&obj,inti,intj){obj.startTime=obj.GetNowTime;(obj.*pFunction[i])(obj.pRandom1);obj.endTime=obj.GetNowTime;obj.runtime[i][j]=obj.endTime-obj.startTime;}②使用两个数组实现乱序、挨次以及逆序数据的排序，大大节约了空间的消耗。根本memcpy函数拷贝到其次个数组里，其次个数组作为乱序序列的保存数组，每次对第一个数组进展排序，之后拷贝其次个数组中的乱序序列到第一个数组，实现各次乱序排列。只要算法正确〔第一步可以检验，之后挨次排列只需反复对第一个数组进展操作即可，再后列到第一组，对第一组反复排序即可。C++实现：请参看源代码。据状况下的移动次数和交换次数。在分别运行乱序、挨次和逆序数组排序时取出前两个数组的值写入第三个数组，然后置零连续统计。C++实现：请参看源代码。时间简洁度与空间简洁度：理论分析可以得出各种排序算法的时间简洁度和空间简洁度，如下表所示：排序方法平均状况最好状况最坏状况关心空间直接插入排序O(n2)O(n)O(n2)O(1)希尔排序O(nlogn)~O(n2)2O(n1.3)O(n2)O(1)起泡排序快速排序O(n2)O(nlogn)2O(n)O(nlogn)2O(n2)O(n2)O(1)O(logn)~O(n)2简洁选择排序O(n2)O(n2)O(n2)O(1)堆排序O(nlogn)2O(nlogn)2O(nlogn)2O(1)归并排序O(nlogn)2O(nlogn)2O(nlogn)2O(n)程序运行结果程序运行框图：实际测试和分析：图一参与了次数统计的运行结果〔100〕图一参与了次数统计的运行结果图二没有参与次数统计的运行结果图二没有参与次数统计的运行结果作如下分析：12假设比较次数和移动次数相差较多，则将产生较大的试验误差。故重写了代码，没有1000个乱序数据进展排序。可以看出时间有所削减。因而图二更加接近实际。3、本程序中的代码有的承受了递归的形式，假设考虑用栈来模拟的话，效率会有提升，所优化，因而还不能完全反映出每个算法的根本性能。总结1、在初期构思代码的时候，首先构造了各种算法的根本实现代码，封装成类，已经能够实需求，需要大量随机数，由于增加了随机函数发生器，满足各种测试条件的需求。之后考虑如何能简化代码以实现多达七种排序算法的简洁调用统计。此外还添加了一些列优化，特别是函数封装的方法，使得程序的构造变得更加合理，版面风格也变得好看，可读性增加。2、程序的优化是一个艰辛的过程，假设只是实现一般的功能，将变得简洁很多，当加上优化，不管是效率还是构造优化，都需要细心设计。这次做优化的过程中，遇到不少阻力。由于优化中用到很多类的封装和访问把握方面的学问弱点。因而以后要多花力气学习C++编程语言，必需要加强这方面的训练，这样才能在将编程思想和数据构造转换为代码的时候能得心应手。3、改进：本程序代码设计时运用了递归的调用方式，效率还可以通过将其转换为栈模拟的其他方式使得类的封装更加完善。附录源码：〔包括三个cpp文件〕//Main.cpp#include<iostream>usingnamespacestd;#include“Sort.h“#include<time.h>#include<string.h>staticint(Sort::*pFunction[7])(long int[])={&Sort::InsertSort,&Sort::ShellSort,&Sort::BubbleSort,&Sort::QuickSort,&Sort::SelectSort,&Sort::HeapSort,&Sort::MergeSort};char*funcName[7]={“1、插入排序:“,“2、希尔排序:“,“3、冒泡排序:“,“4、快速排序:“,“5、选择排序:“,“6、堆排序:“,“7、归并排序:“};/*****************************统计时间函数*****************************/voidStatistics(Sort&obj,inti,intj){obj.startTime=obj.GetNowTime;(obj.*pFunction[i])(obj.pRandom1);obj.endTime=obj.GetNowTime;obj.runtime[i][j]=obj.endTime-obj.startTime;}/****************************主调函数*********************************/intmain(void){cout<<“程序说明：\n110Max;\n2、\n\n“;Sortobj;obj.CreateData;memcpy(obj.pRandom1,obj.pRandom2,(Max+1)*sizeof(longint));inti(0),j(0);/*************************乱序序列*********************************/obj.SetTimesZero;for(i=0;i<7;i++){Statistics(obj,i,0);cout<<funcName[i]<<“\n“; //假设不输出各排序结果，请注释掉此两行obj.PrintArray(obj.pRandom1);if(i!=6)memcpy(obj.pRandom1,obj.pRandom2,(Max+1)*sizeof(longint));}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(longint));for(i=0;i<7;i++){Statistics(obj,i,2);memcpy(obj.pRandom1,obj.pRandom2,(Max+1)*sizeof(longint));}obj.RecordTimes(4);/************************统计排序数据******************************/obj.PrintStatistics(funcName);return0;}//Sort.cppconstintMax=10;classSort{public:Sort;~Sort;voidCreateData(void);intInsertSort(longint[]);intShellSort(longint[]);intBubbleSort(longint[]);intQuickSort(longint[]);intQuickSortRecursion(longint[],int,int);intQuickSortPatition(longint[],int,int);intSelectSort(longint[]);intHeapSort(longint[]);voidHeapSortSift(longint[],int,int);intMergeSort(longint[]);voidMerge(longint[],long int[],int,int,int);voidMergePass(longint[],long int[],int);longdoubleGetNowTime(void);voidPrintArray(longint*);voidSetTimesZero(void);voidRecordTimes(int);friendvoidStatistics(Sort&,int,int);voidPrintStatistics(char*[]);friendintmain(void);private:longint*pRandom1;longint*pRandom2;longdoubleruntime[7][3];intcomparetimes[7];intmovetimes[7];inttimestable[7][6];longdoublestartTime,endTime;};//Function.cpp#include“Sort.h“#include<iostream>#include<stdlib.h>#include<time.h>#include<string.h>#include<cstdio>#include<windows.h>#include<string>#include<iomanip>usingnamespacestd;/***********************************************************构造函数**********************************************************************/Sort::Sort{memset(timestable,0,sizeof(int)*7*6);}/***********************************************************构造数组**********************************************************************/voidSort::CreateData(void){pRandom1=newlongint[Max+1];pRandom2=newlongint[Max+1];srand((unsigned)time(NULL));for(inti=1;i<=Max;i++)pRandom2[i]=rand;cout<<“随机乱序数组如下：\n“; //假设不输出原始数组，请注释掉此两行PrintArray(pRandom2);}/********************************************************简洁插入排序*******************************************************************/intSort::InsertSort(longintparray[]){intj=0;for(inti=2;i<=Max;i++){parray[0]=parray[i];comparetimes[0]++;for(j=i-1;parray[0]<parray[j];j--){parray[j+1]=parray[j];movetimes[0]++;}parray[j+1]=parray[0];movetimes[0]+=2;}return0;}/**********************************************************希尔排序***********************************************************************/intSort::ShellSort(longintparray[]){intj=0;for(intd=Max/2;d>=1;d/=2){for(inti=d+1;i<=Max;i++){parray[0]=parray[i];comparetimes[1]++;for(j=i-d;j>0&&parray[0]<parray[j];j-=d){parray[j+d]=parray[j];movetimes[1]++;}parray[j+d]=parray[0];movetimes[1]+=2;}}return0;}/**********************************************************冒泡排序***********************************************************************/intSort::BubbleSort(longintparray[]){intexchange=Max;intbound,j;while(exchange){bound=exchange;exchange=0;for(j=1;j<bound;j++){comparetimes[2]++;if(parray[j]>parray[j+1]){parray[0]=parray[j];parray[j]=parray[j+1];parray[j+1]=parray[0];exchange=j;movetimes[2]+=3;}}}return0;}/***********************************************************快速排序**********************************************************************/intSort::QuickSort(longintparray[]){QuickSortRecursion(parray,1,Max);return0;}intSort::QuickSortRecursion(longintparray[],intfirst=1,intend=Max){if(first<end){intpivot=QuickSortPatition(parray,first,end);QuickSortRecursion(parray,first,pivot-1);//左侧子序列排序QuickSortRecursion(parray,pivot+1,end); //右侧子序列排序}return0;}intSort::QuickSortPatition(longintr[],intfirst,intend){inti=first;intj=end;inttemp;while(i<j){while(i<j&&r[i]<=r[j]){j--;comparetimes[3]++;} //右侧扫描if(i<j){tem