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

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 存储结构 顺序表: 示意图：a0a1a2a3a4a5a6a7 2.2 关键算法分析（1） 测试数据的产生：正序、逆序、随机数据用两个数组实现乱序、顺序以及逆序数据的排序。基本思想为：随机序列产生一个指定长度的乱序序列，然后通过memcpy()函数拷贝到第二个数组里，第二个数组作为乱序序列的保存数组，每次对第一个数组进行排序，之后拷贝第二个数组中的乱序序列到第一个数组，实现各次乱序排列。只要算法正确（第一步可以检验），之后顺序排列只需反复对第一个数组进行操作即可，再后用第二个数组保存逆序数组，然后同样在每

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 int);（2） 排序算法：插入排序：依次将待排序的序列中的每一个记录插入到先前排序好的序列中，直到全部记录排序完毕。/1/int j=0;/2/ for(int i

4、=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 parray)int j=0;for(int d=Max/2;d=1;d/=2)for(int i=d+1;i0 & parray0parrayj;j-=d) parr

5、ayj+d=parrayj;movetimes1+;parrayj+d=parray0;movetimes1+=2;return 0;冒泡排序：两两比较相邻记录的关键码，如果反序则交换，直到没有反序记录为止。int Sort:BubbleSort(long int parray) 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;movet

6、imes2+=3;return 0;示意图：r1,r2,r3,ri-1,ri,ri+1,rn 反序则交换 有序区快速排序：首先选择一个基准，将记录分割为两部分，左支小于或等于基准，右支则大于基准，然后对两部分重复上述过程，直至整个序列排序完成。int Sort:QuickSort(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=QuickS

7、ortPatition(parray, first, end); QuickSortRecursion(parray, first, pivot-1);/左侧子序列排序 QuickSortRecursion(parray, pivot+1, end); /右侧子序列排序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) t

8、emp=ri; /将较小记录交换到前面 ri=rj; rj=temp; i+; movetimes3+=3; while (ij & 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选择排序：从待排序的记录序列中选择关键码最小（或最大）的记录并将它与序列中的第一个记录交换位置；然后从不包括第一个位置上的记录序列中选择关键码最小（或最大）的记录

9、并将它与序列中的第二个记录交换位置；如此重复，直到序列中只剩下一个记录为止。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 (parrayjparrayindex) index=j; if (index!=i) temp=parrayi; parrayi=parrayindex; parrayindex=temp; movetim

10、es4+=3; 示意图：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; HeapSortSift(

11、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 parray0=parrayi; parrayi=parrayj; parrayj=parray0; movetimes5+=3; i=j; j=2*i; /被筛结点位于原来结

12、点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:Merge(long int parray, long int r1, int s, int m, int t) /一次归并int i=s;int j=m+1;int k=s; whi

13、le (i=m & j=t) comparetimes6+; movetimes6+; if (parrayi=parrayj) 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

14、, 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）比较上述排序算法中关键字的比较次数和移动次数：使用函数指针数组，分别指向各排序函数的入口地址，然后在Statistics()函数中加以调用，使得排序函数运行在统计时间函数之间，这样使用一个for语句即可实现算法的一次性调用、时间统计、移动次数和比较次数统计。void Statistics(Sort &obj,int i,int

15、j)obj.startTime=obj.GetNowTime();(obj.*pFunctioni)(obj.pRandom1);obj.endTime=obj.GetNowTime();obj.runtimeij=obj.endTime-obj.startTime;建立两个数组分别统计运行次数，再统一使用一个数组记录七种算法在三种不同数据情况下的移动次数和交换次数。在分别运行乱序、顺序和逆序数组排序时取出前两个数组的值写入第三个数组，然后置零继续统计。(4)算法的执行时间：获取当前系统时间，精确到微秒，分别在代码运行前后调用记录前后时间，再相减即可得到代码运行时间。此处调用函数QueryPe

16、rformanceCounter()用于得到高精度计时器的值。long double Sort:GetNowT33ime()LARGE_INTEGER litmp; LONG64 QPart; QueryPerformanceCounter(&litmp);QPart=litmp.QuadPart;return (long double)QPart;（5）各种算法的时间复杂度与空间复杂度：排序方法平均情况最好情况最坏情况辅助空间直接插入排序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)快速排

17、序O(nlog2n)O(nlog2n)O(n2)O(log2n) O(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)3. 程序运行结果（1）流程图：开始产生随机数组乱序数组七种排序和统计顺序数组七种排序和统计逆序数组七种排序和统计输出统计结果结 束（2）测试条件：本实验中随机产生的数据量为50（3）测试结论运行结果：分析：多次运行之后统计，从乱序的时间消耗来看，基本符合理论分析由于加入了统计次数的代码，势必增加时间开销，这样统计出来的时间将有一定的

18、误差。假若比较次数和移动次数相差较多，则将产生较大的实验误差。4. 总结（1） 调试时出现的问题及解决的方法在调试过程中，我遇到了一些困难。例如：循环的条件控制不正确。通过云阅读书本，我发现，错误的原因是没能正确理解概念。经过反复的尝试，不断对知识的理解，最终我将错误改正。（2） 心得体会通过此次实验，我对各这种排序有了更加直观和深刻的认识，对书本上介绍的各种算法有了更熟练的掌握。在编程的过程中，我也遇到了一些困难，多是有关c+语法等方面的困难，通过不断的调试与查询资料，我对c+的一些语法更加了解，这对我以后的编程有很大的帮助。（3） 下一步的改进本程序代码设计时运用了递归的调用方式，效率还可

19、以通过将其转换为栈模拟的方式得以提高。源代码：由3部分组成/main.cpp#includeusing namespace std;#includeSort.h#include#includestatic 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

20、、选择排序:,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)*sizeof(long

21、 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,1);obj.RecordTimes(2);

22、/*逆序序列*/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,(Max+1)*sizeof(long int);obj.RecordTimes(4);/*统计排序数据*/obj.PrintStatistics(funcName);return 0;/Sor

23、t.hconst int Max =50;class Sortpublic: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 HeapS

24、ort(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 S

25、tatistics(Sort &,int ,int);void PrintStatistics(char *);friend int main(void);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#inc

26、lude#include#includeusing namespace std;/*构造函数*/Sort:Sort()memset(timestable,0,sizeof(int)*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);/*简单插入

27、排序*/int Sort:InsertSort(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)int exchan

28、ge=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)QuickSortRecursion(parray,1, Max);return 0;int Sort:QuickSortRecursion(long int parray, int

29、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:QuickSortPatition(long int r, int first, int end )int i=first;int j=end;int temp; while (ij) whi

30、le (ij & ri= rj) j-; comparetimes3+; /右侧扫描 if (ij) temp=ri; /将较小记录交换到前面 ri=rj; rj=temp; i+; movetimes3+=3; while (ij & ri= rj) i+; comparetimes3+; /左侧扫描 if (ij) temp=rj; rj=ri; ri=temp; /将较大记录交换到后面 j-; movetimes3+=3; return i; /i为轴值记录的最终位置/*选择排序*/int Sort:SelectSort(long int parray)int i,j,index,tem

31、p; for (i=1; iMax; i+) /对n个记录进行n-1趟简单选择排序 index=i; for (j=i+1; j=Max; j+) comparetimes4+;/在无序区中选取最小记录 if (parrayj=1; i-)HeapSortSift(parray, 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:

32、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 parray0=parrayi; parrayi=parrayj; parrayj=parray0; movetimes5+=3; i=j; j=2*i; /被筛结点位于原来结点j的位置 /*归并排序*/int Sort:MergeSort(long

33、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: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) 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