《2022年北邮数据结构实验第三次实验排序总结》由会员分享，可在线阅读，更多相关《2022年北邮数据结构实验第三次实验排序总结（23页珍藏版）》请在金锄头文库上搜索。
1、第 1 页数据结构实验报告1实验要求(1) 实验目的通过选择下面两个题目之一，学习、实现、对比各种排序算法，掌握各种排序算法的优劣，以及各种算法使用的情况。(2) 实验内容使用简单数组实现下面各种排序算法，并进行比较。排序算法：1、插入排序2、希尔排序3、冒泡排序4、快速排序5、简单选择排序6、堆排序（选作）7、归并排序（选作）8、基数排序（选作）9、其他要求：1、测试数据分成三类：正序、逆序、随机数据2、对于这三类数据，比较上述排序算法中关键字的比较次数和移动次数（其中关键字交换计为3 次移动）。3、对于这三类数据，比较上述排序算法中不同算法的执行时间，精确到微秒（选作）4、对 2 和 3的
2、结果进行分析，验证上述各种算法的时间复杂度编写测试 main() 函数测试排序算法的正确性。2. 程序分析2.1 存储结构顺序表 : 示意图：2.2 关键算法分析（1）测试数据的产生：正序、逆序、随机数据用两个数组实现乱序、顺序以及逆序数据的排序。基本思想为：随机序列产生一个指定长度的乱序序列，然后通过memcpy()函数拷贝到第a0 a1 a2 a3 a4 a5 a6 a7 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 1 页，共 23 页第 2 页二个数组里， 第二个数组作为乱序序列的保存数组，每次对第一个数组进行排序，之后拷贝第二个数组中的
3、乱序序列到第一个数组，实现各次乱序排列。只要算法正确 （第一步可以检验），之后顺序排列只需反复对第一个数组进行操作即可，再后用第二个数组保存逆序数组， 然后同样在每次排序之后复制第二数组存储的乱序序列到第一组，对第一组反复排序即可。 pRandom1=new long intMax+1;pRandom2=new long intMax+1; srand(unsigned)time(NULL); for(int i = 1; i = Max;i+ ) pRandom2i=rand(); memcpy(obj.pRandom1,obj.pRandom2,(Max+1)*sizeof(long in
4、t); （2）排序算法：插入排序： 依次将待排序的序列中的每一个记录插入到先前排序好的序列中，直到全部记录排序完毕。/1/int j=0; /2/ for(int 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:ShellSort(long int
5、 parray) int j=0; for(int d=Max/2;d=1;d/=2) for(int i=d+1;i0 & parray0parrayj;j-=d) parrayj+d=parrayj; movetimes1+; parrayj+d=parray0; movetimes1+=2; return 0; 冒泡排序：两两比较相邻记录的关键码，如果反序则交换，直到没有反序记录为止。int Sort:BubbleSort(long int parray) 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 2 页，共 23 页第 3 页 int
6、 exchange=Max; int bound,j; while(exchange) bound=exchange; exchange=0; for(j=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 Sort:Quic
7、kSort(long int parray) QuickSortRecursion(parray,1, Max);return 0; int Sort:QuickSortRecursion(long int parray, int first=1, int end=Max) if (firstend) int pivot=QuickSortPatition(parray, first, end); QuickSortRecursion(parray, first, pivot-1);/左侧子序列排序 QuickSortRecursion(parray, pivot+1, end); /右侧子序
8、列排序 return 0; int Sort:QuickSortPatition(long 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 页，共 23 页第 4 页 while (i
9、j & ri= rj) i+; comparetimes3+; / 左侧扫描 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:SelectSor
10、t(long int parray) int i,j,index,temp; 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; 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - -
11、 -第 4 页，共 23 页第 5 页示意图：r1,r2,r3,ri- 1,ri,ri+1,rn反序则交换有序区堆排序： 通过建立大根堆或者小根堆，取出根节点， 反复调整堆使之保持大根堆或者小根堆，直至最后序列有序。int Sort:HeapSort(long int parray) int i; for (i=Max/2; i=1; i-) HeapSortSift(parray, i, Max) ; for (i=1; iMax; i+) parray0=parrayMax-i+1; parrayMax-i+1=parray1; parray1=parray0; movetimes5+=3
12、; HeapSortSift(parray, 1, Max-i); return 0; void Sort:HeapSortSift(long 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 页，共 23 页第 6 页
13、parray0=parrayi; parrayi=parrayj; parrayj=parray0; movetimes5+=3; i=j; j=2*i; /被筛结点位于原来结点j 的位置归并排序： 将若干个有序序列两两归并，直至所有待排序的记录都在一个有序序列为止。int Sort:MergeSort(long int parray) long int r1Max+1; int h(1); while (hMax) MergePass(parray, r1, h); /归并 h=2*h; MergePass(r1, parray, h); h=2*h; return 0; void Sort
14、:Merge(long int parray, long int r1, int s, 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 页，共 23 页第 7 页 while (i=m) r1k+=parrayi+; movet
15、imes6+; else while (j=t) r1k+=parrayj+; movetimes6+; void Sort:MergePass(long int parray, long int r1, int h) /一趟归并 int i(1),k; while (i=Max-2*h+1) Merge(parray, r1, i, i+h-1, i+2*h-1); i+=2*h; if (iMax-h+1) Merge(parray, r1, i, i+h-1, Max); else for (k=i; k=Max; k+) r1k=parrayk; movetimes6+; （3）比较上
16、述排序算法中关键字的比较次数和移动次数：使用函数指针数组，分别指向各排序函数的入口地址，然后在Statistics()函数中加以调用，使得排序函数运行在统计时间函数之间，这样使用一个for语句即可实现算法的一次性调用、时间统计、移动次数和比较次数统计。void Statistics(Sort &obj,int i,int j) obj.startTime=obj.GetNowTime(); (obj.*pFunctioni)(obj.pRandom1); obj.endTime=obj.GetNowTime(); obj.runtimeij=obj.endTime-obj.startTime;
17、 建立两个数组分别统计运行次数，再统一使用一个数组记录七种算法在三种不同数据情况下的移动次数和交换次数。在分别运行乱序、顺序和逆序数组排序时取出前两个数组的值写入第三个数组，然后置零继续统计。(4) 算法的执行时间：精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 7 页，共 23 页第 8 页获取当前系统时间，精确到微秒，分别在代码运行前后调用记录前后时间，再相减即可得到代码运行时间。此处调用函数QueryPerformanceCounter()用于得到高精度计时器的值。long double Sort:GetNowT33ime() LARGE_I
18、NTEGER litmp; LONG64 QPart; QueryPerformanceCounter(&litmp); QPart=litmp.QuadPart; return (long double)QPart; （5）各种算法的时间复杂度与空间复杂度：3. 程序运行结果（1）流程图：排序方法平均情况最好情况最坏情况辅助空间直接插入排序O(n2) O(n) O(n2) O(1) 希尔排序O(nlog2n)O(n2) O(n1.3) O(n2) O(1) 起泡排序O(n2) O (n) O(n2) O(1) 快速排序O(nlog2n) O(nlog2n) O(n2) O(log2n) O(
19、n) 简单选择排序O(n2) O(n2) O(n2) O(1) 堆排序O(nlog2n) O(nlog2n) O (nlog2n) O(1) 归并排序O(nlog2n) O(nlog2n) O(nlog2n) O(n) 开始产生随机数组乱序数组七种排序和统计顺序数组七种排序和统计精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 8 页，共 23 页第 9 页（2）测试条件：本实验中随机产生的数据量为50 （3）测试结论运行结果：结 束输出统计结果逆序数组七种排序和统计精选学习资料 - - - - - - - - - 名师归纳总结 - - - - -
20、- -第 9 页，共 23 页第 10 页精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 10 页，共 23 页第 11 页精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 11 页，共 23 页第 12 页分析：多次运行之后统计，从乱序的时间消耗来看，基本符合理论分析由于加入了统计次数的代码，势必增加时间开销，这样统计出来的时间将有一定的误差。假若比较次数和移动次数相差较多，则将产生较大的实验误差。4. 总结（1）调试时出现的问题及解决的方法在调试过程中，我遇到了一些困难。例如：循环的条件控制不正确。通
21、过云阅读书本，我发现，错误的原因是没能正确理解概念。经过反复的尝试，不断对知识的理解，最终我将错误改正。（2）心得体会通过此次实验，我对各这种排序有了更加直观和深刻的认识，对书本上介绍的各种算法有了更熟练的掌握。在编程的过程中，我也遇到了一些困难，多是有关c+语法等方面的困难，通过不断的调试与查询资料，我对c+的一些语法更加了解，这对我以后的编程有很大的帮助。（3）下一步的改进本程序代码设计时运用了递归的调用方式，效率还可以通过将其转换为栈模拟的方式得以提高。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 12 页，共 23 页第 13 页源代码：
22、由3 部分组成/main.cpp #include using namespace std; #includeSort.h #include #include static int (Sort:*pFunction7)(long int )=&Sort:InsertSort,&Sort:ShellSort,&Sort:BubbleSort,&Sort:QuickSort,&Sort:SelectSort,&Sort:HeapSort,&Sort:MergeSort; char *funcName7=1、 插入排序 :,2、 希尔排序 :,3、 冒泡排序 :,4、 快速排序 :,5、选择排序 :
23、,6、堆排 序:,7、归并排序 :; /*统计时间函数 */ void Statistics(Sort &obj,int i,int j) obj.startTime=obj.GetNowTime(); (obj.*pFunctioni)(obj.pRandom1); obj.endTime=obj.GetNowTime(); obj.runtimeij=obj.endTime-obj.startTime; /*主调函数 */ int main() Sort obj; obj.CreateData(); memcpy(obj.pRandom1,obj.pRandom2,(Max+1)*size
24、of(long int); int i(0),j(0); /*乱序序列 */ obj.SetTimesZero(); for(i=0;i7;i+) Statistics(obj,i,0); coutfuncNamein; / 输出各排序结果obj.PrintArray(obj.pRandom1); if(i!=6) memcpy(obj.pRandom1,obj.pRandom2,(Max+1)*sizeof(long int); obj.RecordTimes(0); /*顺序序列 */ obj.SetTimesZero(); for( i=0;i7;i+) Statistics(obj,i
25、,1); 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 13 页，共 23 页第 14 页obj.RecordTimes(2); /*逆序序列 */ obj.SetTimesZero(); for(i=1;i=Max;i+) obj.pRandom2i=obj.pRandom1Max+1-i; memcpy(obj.pRandom1,obj.pRandom2,(Max+1)*sizeof(long int); for(i=0;i7;i+) Statistics(obj,i,2); memcpy(obj.pRandom1,obj.pRandom2,
26、(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 QuickS
27、ortRecursion(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
28、 ); long double GetNowTime(void); void PrintArray(long int*); void SetTimesZero(void); void RecordTimes(int); 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 14 页，共 23 页第 15 页friend void Statistics(Sort &,int ,int); void PrintStatistics(char *); friend int main(void); private: long int *pRandom1; lon
29、g int *pRandom2; long double runtime73; int comparetimes7; int movetimes7; int timestable76; long double startTime,endTime; ; /Function.cpp #includeSort.h #include #include #include #include #include #include #include #include using namespace std; /*构造函数*/ Sort:Sort() memset(timestable,0,sizeof(int)
30、*7*6); /*构造数组*/ void Sort:CreateData() pRandom1=new long intMax+1; pRandom2=new long intMax+1; srand(unsigned)time(NULL); for(int i = 1; i = Max;i+ ) pRandom2i=rand(); cout 随机乱序数组如下：n; / 输出原始数组PrintArray(pRandom2); /*简单插入排序精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 15 页，共 23 页第 16 页*/ int Sort:I
31、nsertSort(long int parray) int j=0; for(int i =2; i = Max;i+) parray0=parrayi; comparetimes0+;/比较次数统计for(j=i-1;parray0=1;d/=2) for(int i=d+1;i0 & parray0parrayj;j-=d) parrayj+d=parrayj; movetimes1+; parrayj+d=parray0; movetimes1+=2; return 0; /*冒泡排序*/ int Sort:BubbleSort(long int parray) 精选学习资料 - -
32、- - - - - - - 名师归纳总结 - - - - - - -第 16 页，共 23 页第 17 页int exchange=Max; int bound,j; while(exchange) bound=exchange; exchange=0; for(j=1;jparrayj+1) parray0=parrayj; parrayj=parrayj+1; parrayj+1=parray0; exchange=j; movetimes2+=3; return 0; /*快速排序*/ int Sort:QuickSort(long int parray) QuickSortRecurs
33、ion(parray,1, Max); return 0; int Sort:QuickSortRecursion(long int parray, int first=1, int end=Max) if (firstend) int pivot=QuickSortPatition(parray, first, end); QuickSortRecursion(parray, first, pivot-1);/左侧子序列排序 QuickSortRecursion(parray, pivot+1, end); /右侧子序列排序 return 0; int Sort:QuickSortPatit
34、ion(long int r, int first, int end ) int i=first; int j=end; int temp; 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 17 页，共 23 页第 18 页 while (ij) while (ij & ri= rj) j-; comparetimes3+; / 右侧扫描 if (ij) temp=ri; /将较小记录交换到前面 ri=rj; rj=temp; i+; movetimes3+=3; while (ij & ri= rj) i+; comparetimes3+; /
35、左侧扫描 if (ij) temp=rj; rj=ri; ri=temp; /将较大记录交换到后面 j-; movetimes3+=3; return i; /i为轴值记录的最终位置 /*选择排序*/ int Sort:SelectSort(long int parray) int i,j,index,temp; for (i=1; iMax; i+) /对 n 个记录进行n-1 趟简单选择排序 index=i; for (j=i+1; j=Max; j+) comparetimes4+; /在无序区中选取最小记录 if (parrayj=1; i-) HeapSortSift(parray,
36、 i, Max) ; for (i=1; iMax; i+) parray0=parrayMax-i+1; parrayMax-i+1=parray1; parray1=parray0; movetimes5+=3; HeapSortSift(parray, 1, Max-i); return 0; void Sort:HeapSortSift(long int parray, int k, int m) int i,j; i=k; j=2*i; /置 i 为要筛的结点，j 为 i 的左孩子 while (j=m) /筛选还没有进行到叶子 if (jm & parrayjparrayj) co
37、mparetimes5+; 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 19 页，共 23 页第 20 页 break; / 根结点已经大于左右孩子中的较大者else parray0=parrayi; parrayi=parrayj; parrayj=parray0; movetimes5+=3; i=j; j=2*i; /被筛结点位于原来结点j 的位置 /*归并排序*/ int Sort:MergeSort(long int parray) long int r1Max+1; int h(1); while (hMax) MergePass(
38、parray, r1, h); /归并 h=2*h; MergePass(r1, parray, h); h=2*h; return 0; void Sort:Merge(long int parray, long int r1, int s, int m, int t) /一次归并 int i=s; int j=m+1; int k=s; while (i=m & j=t) comparetimes6+; movetimes6+; if (parrayi=parrayj) 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 20 页，共 23 页第
39、21 页 r1k+=parrayi+; else r1k+=parrayj+; if (i=m) while (i=m) r1k+=parrayi+; movetimes6+; else while (j=t) r1k+=parrayj+; movetimes6+; void Sort:MergePass(long int parray, long int r1, int h) /一趟归并 int i(1),k; while (i=Max-2*h+1) Merge(parray, r1, i, i+h-1, i+2*h-1); i+=2*h; if (iMax-h+1) Merge(parra
40、y, r1, i, i+h-1, Max); else for (k=i; k=Max; k+) r1k=parrayk; movetimes6+; /*获 取 当 前 时 间*/ long double Sort:GetNowTime() LARGE_INTEGER litmp; LONG64 QPart; QueryPerformanceCounter(&litmp); QPart=litmp.QuadPart; return (long double)QPart; 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 21 页，共 23 页第 22
41、 页 /*打印数组*/ void Sort:PrintArray(long int *pRandom) for(int j=1;j=Max;j+) coutpRandomjt; coutendl; /*数 组 置 零 函 数*/ void Sort:SetTimesZero() memset(comparetimes,0,sizeof(int)*7); memset(movetimes,0,sizeof(int)*7); void Sort:RecordTimes(int j) for(int i=0;i7;i+) timestableij=movetimesi; timestableij+1
42、=comparetimesi; /*输 出 排 序 数 据*/ void Sort:PrintStatistics(char* funcname) int i(0),j(0); cout 排序方法 t乱序耗时 ( s) 顺序耗时 ( s) 逆序耗时 ( s)endl; for(i=0;i7;i+) coutfuncnameitsetw(8)setiosflags(ios:fixed)setprecision(0) setiosflags(ios:left)runtimei0tsetw(8)runtimei1 tsetw(8)runtimei2endl; coutnttt移动次数统计表nn; c
43、out 排 序 方 法 t 乱 序 序 列 t 顺 序 序 列 t 逆 序 序 列tendl; for(i=0;i7;i+) 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 22 页，共 23 页第 23 页coutfuncnamei; for(j=0;j6;j+=2) couttttimestableij; coutendl; coutnttt比较次数统计表nn; cout 排 序 方 法 t 乱 序 序 列 t 顺 序 序 列 t 逆 序 序 列tendl; for(i=0;i7;i+) coutfuncnamei; for(j=1;j6;j+=2) couttttimestableij; coutendl; /*类 的 析 构 函 数*/ Sort:Sort() delete pRandom1; delete pRandom2; 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 23 页，共 23 页
