《2022年北邮数据结构实验第三次实验排序总结.docx》由会员分享，可在线阅读，更多相关《2022年北邮数据结构实验第三次实验排序总结.docx（43页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、精选学习资料 - - - - - - - - - 数据结构试验报告1试验要求1 试验目的通过挑选下面两个题目之一,学习、实现、对比各种排序算法,把握各种排序算法的优 劣,以及各种算法使用的情形；2 试验内容 使用简洁数组实现下面各种排序算法,并进行比较；排序算法：1、插入排序 2、希尔排序 3、冒泡排序 4、快速排序 5、简洁挑选排序 6、堆排序（选作）7、归并排序（选作）8、基数排序（选作）9、其他 要求：1、测试数据分成三类：正序、逆序、随机数据 2、对于这三类数据,比较上述排序算法中关键字的比较次数和移动次数（其 中关键字交换计为 3 次移动）；3、对于这三类数据,比较上述排序算法中不同
2、算法的执行时间,精确到微秒（选作）4、对 2 和 3 的结果进行分析,验证上述各种算法的时间复杂度 编写测试 main 函数测试排序算法的正确性；2. 程序分析2.1 储备结构 次序表 : 示意图：a0 a1 a2 a3 a4 a5 a6 a7 2.2 关键算法分析（1）测试数据的产生：正序、逆序、随机数据 用两个数组实现乱序、次序以及逆序数据的排序；基本思想为：随机序列产生一个指定长度的乱序序列,然后通过第 1 页memcpy函数拷贝到第名师归纳总结 - - - - - - -第 1 页,共 23 页精选学习资料 - - - - - - - - - 二个数组里, 其次个数组作为乱序序列的储存
3、数组,每次对第一个数组进行排序,之后拷贝其次个数组中的乱序序列到第一个数组,实现各次乱序排列；只要算法正确 （第一步可以检验）,之后次序排列只需反复对第一个数组进行操作即可,再后用其次个数组储存逆 序数组, 然后同样在每次排序之后复制其次数组储备的乱序序列到第一组,对第一组反复 排序即可； pRandom1=new long intMax+1;pRandom2=new long intMax+1; srandunsignedtimeNULL; forint i = 1; i = Max;i+ pRandom2i=rand; memcpyobj.pRandom1,obj.pRandom2,Max
4、+1*sizeoflong int; （2）排序算法：插入排序： 依次将待排序的序列中的每一个记录插入到从前排序好的序列中,直到全 部记录排序完毕；/1/int j=0; /2/ forint i =2; i = Max;i+ parray0=parrayi;comparetimes0+; /4/parrayj+1=parray0;movetimes0+=2; 示意图：r1,r2,r3, ,ri- 1,ri,ri+1, ,rn有序区待插入无序区希尔排序：先将整个序列分割成如干个子列,分别在各个子列中运用直接插入排序,待整个序列基本有序时,再对全体记录进行一次直接插入排序；int Sort:Sh
5、ellSortlong int parray int j=0; forint d=Max/2;d=1;d/=2 forint i=d+1;i0 & parray0parrayj;j-=d parrayj+d=parrayj; movetimes1+; parrayj+d=parray0; movetimes1+=2; return 0; 冒泡排序：两两比较相邻记录的关键码,假如反序就交换,直到没有反序记录为止；int Sort:BubbleSortlong int parray 第 2 页名师归纳总结 - - - - - - -第 2 页,共 23 页精选学习资料 - - - - - - -
6、- - int exchange=Max; int bound,j; whileexchange bound=exchange; exchange=0; forj=1;jparrayj+1 parray0=parrayj; parrayj=parrayj+1; parrayj+1=parray0; exchange=j; movetimes2+=3; return 0; 示意图：r1,r2,r3, ,ri- 1,ri,ri+1, ,rn反序就交换有序区快速排序：第一挑选一个基准,将记录分割为两部分,左支小于或等于基准,右支就 大于基准,然后对两部分重复上述过程,直至整个序列排序完成；int S
7、ort:QuickSortlong int parray QuickSortRecursionparray,1, Max;return 0; int Sort:QuickSortRecursionlong int parray, int first=1, int end=Max if firstend int pivot=QuickSortPatitionparray, first, end; QuickSortRecursionparray, first, pivot-1;/左侧子序列排序 QuickSortRecursionparray, pivot+1, end; /右侧子序列排序ret
8、urn 0; int Sort:QuickSortPatitionlong int r, int first, int end int i=first;int j=end; int temp; while ij while ij & ri= rj j-; comparetimes3+; / 右侧扫描 if ij temp=ri; / 将较小记录交换到前面 ri=rj; rj=temp; i+; movetimes3+=3; 第 3 页名师归纳总结 - - - - - - -第 3 页,共 23 页精选学习资料 - - - - - - - - - while ij & ri= rj i+; co
9、mparetimes3+; / 左侧扫描 if ij temp=rj; rj=ri; ri=temp; / 将较大记录交换到后面 j-; movetimes3+=3; 为轴值记录的最终位置 return i; /i示意图：r1,r2,r3, ,ri- 1,ri,ri+1, ,rn rri 挑选排序： 从待排序的记录序列中挑选关键码最小（或最大） 的记录并将它与序列中的第一个记录交换位置；然后从不包括第一个位置上的记录序列中挑选关键码最小（或最大）的记录并将它与序列中的其次个记录交换位置；int Sort:SelectSortlong int parray int i,j,index,temp;
10、 如此重复,直到序列中只剩下一个记录为止； for i=1; iMax; i+ /对 n 个记录进行n-1 趟简洁挑选排序 index=i; for j=i+1; j=Max; j+ comparetimes4+; / 在无序区中选取最小记录 if parrayjparrayindex index=j; if index.=i temp=parrayi; parrayi=parrayindex; parrayindex=temp; movetimes4+=3; 第 4 页名师归纳总结 - - - - - - -第 4 页,共 23 页精选学习资料 - - - - - - - - - 示意图：r
11、1,r2,r3, ,ri- 1,ri,ri+1, ,rn反序就交换 有序区堆排序： 通过建立大根堆或者小根堆,小根堆,直至最终序列有序；int Sort:HeapSortlong int parray int i; for i=Max/2; i=1; i- HeapSortSiftparray, i, Max ; for i=1; iMax; i+ parray0=parrayMax-i+1; parrayMax-i+1=parray1; parray1=parray0; movetimes5+=3; HeapSortSiftparray, 1, Max-i; return 0; 取出根节点,
12、 反复调整堆使之保持大根堆或者void Sort:HeapSortSiftlong int parray, int k, int m int i,j; i=k; j=2*i; / 置 i 为要筛的结点,j 为 i 的左孩子 while j=m / 挑选仍没有进行到叶子 if jm & parrayjparrayj comparetimes5+; break; / 根结点已经大于左右孩子中的较大者 else 第 5 页名师归纳总结 - - - - - - -第 5 页,共 23 页精选学习资料 - - - - - - - - - parray0=parrayi; parrayi=parrayj;
13、 parrayj=parray0; movetimes5+=3; i=j; j=2*i; /被筛结点位于原先结点j 的位置归并排序： 将如干个有序序列两两归并,止；int Sort:MergeSortlong int parray long int r1Max+1; int h1; while hMax 直至全部待排序的记录都在一个有序序列为 MergePassparray, r1, h; / 归并 h=2*h; MergePassr1, parray, h; h=2*h; return 0; void Sort:Mergelong int parray, long int r1, int s
14、, int m, int t / 一次归并 int i=s; int j=m+1; int k=s; while i=m & j=t comparetimes6+; movetimes6+; if parrayi=parrayj r1k+=parrayi+; else r1k+=parrayj+; if i=m 第 6 页名师归纳总结 - - - - - - -第 6 页,共 23 页精选学习资料 - - - - - - - - - while i=m r1k+=parrayi+; movetimes6+; else while j=t r1k+=parrayj+; movetimes6+;
15、void Sort:MergePasslong int parray, long int r1, int h / 一趟归并 int i1,k; while i=Max-2*h+1 Mergeparray, r1, i, i+h-1, i+2*h-1; i+=2*h; if iMax-h+1 Mergeparray, r1, i, i+h-1, Max; else for k=i; k=Max; k+ r1k=parrayk; movetimes6+; （3）比较上述排序算法中关键字的比较次数和移动次数：使用函数指针数组,分别指向各排序函数的入口地址,然后在forStatistics函数中加以调
16、用,使得排序函数运行在统计时间函数之间,这样使用一个语句即可实现算法的一次性调用、时间统计、移动次数和比较次数统计；void StatisticsSort &obj,int i,int j obj.startTime=obj.GetNowTime; obj.*pFunctioniobj.pRandom1; obj.endTime=obj.GetNowTime; obj.runtimeij=obj.endTime-obj.startTime; 建立两个数组分别统计运行次数,再统一使用一个数组记录七种算法在三种不同数据情形下的移动次数和交换次数；在分别运行乱序、 次序和逆序数组排序时取出前两个数组
17、的值写入 第三个数组,然后置零连续统计；4 算法的执行时间：第 7 页名师归纳总结 - - - - - - -第 7 页,共 23 页精选学习资料 - - - - - - - - - 猎取当前系统时间,精确到微秒,分别在代码运行前后调用记录前后时间,再相减即可得到代码运行时间；此处调用函数QueryPerformanceCounter用于得到高精度计时器的值；long double Sort:GetNowT33ime LARGE_INTEGER litmp; LONG64 QPart; QueryPerformanceCounter&litmp; QPart=litmp.QuadPart; r
18、eturn long doubleQPart; （5）各种算法的时间复杂度与空间复杂度：3. 排序方法平均情形最好情形最坏情形帮助空间直接插入排序O n 2 O n O n 2 O1 希尔排序O nlog 2n O n 2 O n1.3 O n 2 O1 起泡排序O n 2 O n O n 2 O1 快速排序O nlog 2n O nlog 2n O n 2 Olog2n O n 简洁挑选排序O n 2 O n 2 O n 2 O1 堆排序O nlog 2n O nlog 2n O nlog 2n O1 归并排序O nlog 2n O nlog 2n O nlog 2n O n 程序运行结果（
19、1）流程图：开头产生随机数组乱序数组七种排序和统计次序数组七种排序和统计 第 8 页名师归纳总结 - - - - - - -第 8 页,共 23 页精选学习资料 - - - - - - - - - 逆序数组七种排序和统计输出统计结果结 束（2）测试条件：本试验中随机产生的数据量为 50 （3）测试结论运行结果：第 9 页名师归纳总结 - - - - - - -第 9 页,共 23 页精选学习资料 - - - - - - - - - 第 10 页名师归纳总结 - - - - - - -第 10 页,共 23 页精选学习资料 - - - - - - - - - 第 11 页名师归纳总结 - - -
20、 - - - -第 11 页,共 23 页精选学习资料 - - - - - - - - - 分析：多次运行之后统计,从乱序的时间消耗来看,基本符合理论分析由于加入了统计次数的代码,势必增加时间开销,这样统计出来的时间将有肯定的误差；假如比较次数和移动次数相差较多,就将产生较大的试验误差；4. 总结（1）调试时显现的问题及解决的方法在调试过程中,我遇到了一些困难；例如：循环的条件掌握不正确；通过云阅读书 本,我发觉,错误的缘由是没能正确懂得概念；经过反复的尝试,不断对学问的理 解,最终我将错误改正；（2）心得体会 通过此次试验,我对各这种排序有了更加直观和深刻的熟悉,对书本上介绍的各种 算法有了
21、更娴熟的把握；在编程的过程中,我也遇到了一些困难,多是有关c+语法等方面的困难,通过不断的调试与查询资料,我对 c+的一些语法更加明白,这对我以后的编程有很大的帮忙；（3）下一步的改进本程序代码设计时运用了递归的调用方式,式得以提高；效率仍可以通过将其转换为栈模拟的方第 12 页名师归纳总结 - - - - - - -第 12 页,共 23 页精选学习资料 - - - - - - - - - 源代码：由 3 部分组成 /main.cpp #include using namespace std; #includeSort.h #include #include static int Sort:
22、*pFunction7long int =&Sort:InsertSort,&Sort:ShellSort,&Sort:BubbleSort,&Sort:QuickSort,&Sor t:SelectSort,&Sort:HeapSort,&Sort:MergeSort; char *funcName7=1、插入排序 :,2、希尔排序 :,3、冒泡排序 :,4、快速排序 :,5、挑选排序 :,6、堆 排 序:,7、归并排序 :; /*统计时间函数 */ void StatisticsSort &obj,int i,int j obj.startTime=obj.GetNowTime; obj.
23、*pFunctioniobj.pRandom1; obj.endTime=obj.GetNowTime; obj.runtimeij=obj.endTime-obj.startTime; /* int main Sort obj; obj.CreateData; 主调函数 */ memcpyobj.pRandom1,obj.pRandom2,Max+1*sizeoflong int; int i0,j0; /* obj.SetTimesZero; fori=0;i7;i+ 乱序序列 */ Statisticsobj,i,0; coutfuncNamein; / 输出各排序结果 obj.Prin
24、tArrayobj.pRandom1; ifi.=6 memcpyobj.pRandom1,obj.pRandom2,Max+1*sizeoflong int; obj.RecordTimes0; /* obj.SetTimesZero; for i=0;i7;i+ 次序序列 */ Statisticsobj,i,1; 第 13 页名师归纳总结 - - - - - - -第 13 页,共 23 页精选学习资料 - - - - - - - - - obj.RecordTimes2; /* obj.SetTimesZero; fori=1;i=Max;i+ 逆序序列 */ obj.pRandom2
25、i=obj.pRandom1Max+1-i; memcpyobj.pRandom1,obj.pRandom2,Max+1*sizeoflong int; fori=0;i7;i+ Statisticsobj,i,2; memcpyobj.pRandom1,obj.pRandom2,Max+1*sizeoflong int; obj.RecordTimes4; /*统计排序数据 */ obj.PrintStatisticsfuncName; return 0; /Sort.h const int Max =50; class Sort public: Sort; Sort; void Creat
26、eDatavoid; int InsertSortlong int ; int ShellSortlong int ; int BubbleSortlong int ; int QuickSortlong int ; int QuickSortRecursionlong int , int ,int; int QuickSortPatitionlong int , int , int ; int SelectSortlong int ; int HeapSortlong int ;/ 堆排序 void HeapSortSiftlong int , int , int ;/ 挑选 int Mer
27、geSortlong int ; void Mergelong int ,long int , int , int , int ;/ 归并排序 void MergePasslong int ,long int , int ; long double GetNowTimevoid; void PrintArraylong int*; void SetTimesZerovoid; void RecordTimesint; 第 14 页名师归纳总结 - - - - - - -第 14 页,共 23 页精选学习资料 - - - - - - - - - friend void StatisticsSor
28、t &,int ,int; void PrintStatisticschar *; friend int mainvoid; private: long int *pRandom1; long int *pRandom2; long double runtime73; int comparetimes7; int movetimes7; int timestable76; long double startTime,endTime; ; /Function.cpp #includeSort.h #include #include #include #include #include #incl
29、ude #include #include using namespace std; /*构造函数*/ Sort:Sort memsettimestable,0,sizeofint*7*6; /*构造数组*/ void Sort:CreateData pRandom1=new long intMax+1; pRandom2=new long intMax+1; srandunsignedtimeNULL; forint i = 1; i = Max;i+ pRandom2i=rand; cout 随机乱序数组如下：n; / 输出原始数组PrintArraypRandom2; /*简单插入排序第
30、 15 页名师归纳总结 - - - - - - -第 15 页,共 23 页精选学习资料 - - - - - - - - - */ int Sort:InsertSortlong int parray int j=0; forint i =2; i = Max;i+ parray0=parrayi; comparetimes0+;/ 比较次数统计 forj=i-1;parray0=1;d/=2 forint i=d+1;i0 & parray0parrayj;j-=d parrayj+d=parrayj; movetimes1+; parrayj+d=parray0; movetimes1+=
31、2; return 0; /*冒泡排序*/ int Sort:BubbleSortlong int parray 第 16 页名师归纳总结 - - - - - - -第 16 页,共 23 页精选学习资料 - - - - - - - - - int exchange=Max; int bound,j; whileexchange bound=exchange; exchange=0; forj=1;jparrayj+1 parray0=parrayj; parrayj=parrayj+1; parrayj+1=parray0; exchange=j; movetimes2+=3; return
32、 0; /*快速排序*/ int Sort:QuickSortlong int parray QuickSortRecursionparray,1, Max; return 0; int Sort:QuickSortRecursionlong int parray, int first=1, int end=Max if firstend int pivot=QuickSortPatitionparray, first, end; QuickSortRecursionparray, first, pivot-1;/ 左侧子序列排序 QuickSortRecursionparray, pivot+1, end; / 右侧子序列排序 return 0; int Sort:QuickSortPatitionlong int r, int first,