北邮数据结构实验报告-排序.doc

北京邮电大学数据结构试验报告实验名称： 实验四 排序学生姓名： 班 级： 班内序号： 学 号： 日 期： 2014年1月4日1 实验目的学习、实现、对比各种排序算法，掌握各种排序算法的优劣，以及各种算法使用的情况。2 实验内容2.1 题目1使用简单数组实现下面各种排序算法，并进行比较。排序算法： 1、插入排序 2、希尔排序3、冒泡排序4、快速排序5、简单选择排序6、堆排序（选作）7、归并排序（选作）8、基数排序（选作）9、其他要求： 1、测试数据分成三类：正序、逆序、随机数据2、对于这三类数据，比较上述排序算法中关键字的比较次数和移动次数（其中关键字交换计为3次移动）。 3、对于这三类数据，比较上述排序算法中不同算法的执行时间，精确到微秒（选作）4、对2和3的结果进行分析，验证上述各种算法的时间复杂度编写测试main()函数测试线性表的正确性。3 程序分析3.1存储结构顺序存储结构数组3.2关键算法分析1. 插入排序：依次将待排序的序列中的每一个记录插入到先前排序好的序列中，直到全部记录排序完毕void Insertsort(int r,int n,int* compare,int* move)/插入排序 *compare=0;*move=0;int i;int j;for(i=1;in;i+)/一共要排序n-1次int x=ri;for(j=i-1;x=0;j-) (*compare)+;(*move)+;rj+1=rj;if(j=0) (*compare)+;rj+1=x;2. 希尔排序：先将整个序列分割成若干个子列，分别在各个子列中运用直接插入排序，待整个序列基本有序时，再对全体记录进行一次直接插入排序void ShellInsert(int r,int n,int* compare,int* move)/希尔排序 *compare=0;*move=0;int j;10 9 12 12 20 20 31for(int d=n/2;d=1;d=d/2)/间距越来越小for(int i=d;i=n-1;i+)/从ad往后逐个元素确定是否需要前移if(ri=0)&(x=0)(*compare)+; rj+d=x;else (*compare)+;3. 冒泡排序：两两比较相邻记录的关键码，如果反序则交换，直到没有反序记录为止void Bubblesort(int r,int n,int* compare,int* move)/交换（冒泡）排序*compare=0;*move=0;int x;for(int j=0;jj;i-) if(riri-1) (*compare)+; (*move)+=3; x=ri; ri=ri-1; ri-1=x; else (*compare)+; 4. 快速排序：首先选择一个基准，将记录分割为两部分，左支小于或等于基准，右支则大于基准，然后对两部分重复上述过程，直至整个序列排序完成int Partion(int r,int first,int end,int* compare,int* move)/快速排序中的轴定位int i=first;int j=end;int zhou=ri;/默认第一个元素为轴while(ij)while(i=zhou) /查看右侧元素与轴的大小关系(*compare)+;j-;if(ij)(*compare)+;(*move)+; ri=rj;/发现轴右侧的某数比轴值小，将其前置while(ij)&(ri=zhou)/查看左侧元素与轴的大小关系(*compare)+; i+;if(ij)(*compare)+; (*move)+; rj=ri;/发现轴左侧的某数比轴值小，将其后置ri=zhou;/最后确定轴的位置return i;void Qsort(int r,int i,int j,int* compare,int* move)/快速排序if(ij)int centre=Partion(r,i,j,compare,move);Qsort(r,i,centre-1,compare,move);Qsort(r,centre+1,j,compare,move);5. 选择排序：从待排序的记录序列中选择关键码最小的记录并将它与序列中的第一个记录交换位置；然后从不包括第一个位置上的记录序列中选择关键码最小（或最大）的记录并将它与序列中的第二个记录交换位置；如此重复，直到序列中只剩下一个记录为止void Selectsort(int r,int n,int* compare,int* move)/选择排序*compare=0;*move=0;for(int i=0;in-1;i+)/排序n-1次 int min=i; for(int j=i+1;jn;j+)/通过此层循环，找到真正的第i个最小值 (*compare)+; if(rjrmin) min=j;/记录下当前找到的最小值的位置 if(min!=i) (*move)+=3; int Min; Min=rmin; rmin=ri; ri=Min; 4 程序运行结果4.1主函数流程图4.2程序运行框图5 实验心得1.调试时出现的问题及解决的方法 在初期构思代码的时候，首先构造了各种算法的基本实现代码，封装成类，已经能够实现七种排序的基本功能，并且测试无误。之后考虑如何能简化代码以实现多达七种排序算法的简单调用、乱序和顺序以及逆序数据的分别排序和性能指标统计（算法移动次数和比较次数的精确统计）。2.心得体会 程序的优化是一个艰辛的过程，如果只是实现一般的功能，将变得容易很多，当加上优化，不论是效率还是结构优化，都需要精心设计。3. 改进本程序代码设计时运用了递归的调用方式，效率还可以通过将其转换为栈模拟的方式得以提高。另外还可以进一步考虑算法时间的精确统计，以便从时间角度比较这几种排序算法的优劣。完整源代码#includeusing namespace std;void Insertsort(int r,int n,int* compare,int* move);void ShellInsert(int r,int n,int* compare,int* move);void Bubblesort(int r,int n,int* compare,int* move);int Partion(int r,int first,int end,int* compare,int* move);void Qsort(int r,int i,int j,int* compare,int* move);void Selectsort(int r,int n,int* compare,int* move);void Insertsort(int r,int n,int* compare,int* move)/插入排序 *compare=0;*move=0;int i;int j;for(i=1;in;i+)/一共要排序n-1次int x=ri;for(j=i-1;x=0;j-) (*compare)+;(*move)+;rj+1=rj;if(j=0) (*compare)+;rj+1=x;void ShellInsert(int r,int n,int* compare,int* move)/希尔排序 *compare=0;*move=0;int j;for(int d=n/2;d=1;d=d/2)/间距越来越小for(int i=d;i=n-1;i+)/从ad往后逐个元素确定是否需要前移if(ri=0)&(x=0)(*compare)+; rj+d=x;else (*compare)+;void Bubblesort(int r,int n,int* compare,int* move)/交换（冒泡）排序*compare=0;*move=0;int x;for(int j=0;jj;i-) if(riri-1) (*compare)+; (*move)+=3; x=ri; ri=ri-1; ri-1=x; else (*compare)+; int Partion(int r,int first,int end,int* compare,int* move)/快速排序中的轴定位int i=first;int j=end;int zhou=ri;/默认第一个元素为轴while(ij)while(i=zhou) /查看右侧元素与轴的大小关系(*compare)+;j-;if(ij)(*compare)+;(*move)+; ri=rj;/发现轴右侧的某数比轴值小，将其前置while(ij)&(ri=zhou)/查看左侧元素与轴的大小关系(*compare)+; i+;if(ij)(*compare)+; (*move)+; rj=ri;/发现轴左侧的某数比轴值小，将其后置ri=zhou;/最后确定轴的位置return i;void Qsort(int r,int i,int j,int* compare,int* move)/快速排序if(ij)int centre=Partion(r,i,j,compare,move);Qsort(r,i,centre-1,compare,move);Qsort(r,centre+1,j,compare,move);void Selectsort(int r,int n,int* compare,int* move)/选择排序*compare=0;*move=0;for(int i=0;in-1;i+)/排序n-1次 int min=i; for(int j=i+1;jn;j+)/通过此层循环，找到真正的第i个最小值 (*compare)+; if(rjrmin) min=j;/记录下当前找到的最小值的位置 if(min!=i) (*move)+=3; int Min; Min=rmin; rmin=ri; ri=Min; void main()int i;int compare=0;int move=0;cout请您先输入一个正序数组哦endl;int n;coutn;int *r=new intn;cout请输入数组中的元素：;for(i=0;iri;int *a=new intn;for(i=0;in;i+) ai=ri;Insertsort(a,n,&compare,&move);coutn插入排序结果为：;for(i=0;in;i+) coutai ;coutn比较次数为compare;coutn移动次数为movenendl;int *b=new intn;for(i=0;in;i+) bi=ri;ShellInsert(b,n,&compare,&move);cout希尔排序结果为：;for(i=0;in;i+) coutbi ;coutn比较次数为compare;coutn移动次数为movenendl;int *c=new intn;for(i=0;in;i+) ci=ri;Bubblesort(c,n,&compare,&move);cout交换排序结果为：;for(i=0;in;i+) coutci ;coutn比较次数为compare;coutn移动次数为movenendl;compare=0;move=0;int *d=new intn;for(i=0;in;i+) di=ri;Qsort(d,0,n-1,&compare,&move);cout快速排序结果为：;for(i=0;in;i+) coutdi ;coutn比较次数为compare;coutn移动次数为movenendl;int *e=new intn;for(i=0;in;i+) ei=ri;Selectsort(e,n,&compare,&move);cout选择排序结果为：;for(i=0;in;i+) coutei ;coutn比较次数为compare;coutn移动次数为movenendl;cout再输入一个逆序数组endl;coutn;cout请输入数组中的元素：;for(i=0;iri;for(i=0;in;i+) ai=ri;Insertsort(a,n,&compare,&move);coutn插入排序结果为：;for(i=0;in;i+) coutai ;coutn比较次数为compare;coutn移动次数为movenendl;for(i=0;in;i+) bi=ri;ShellInsert(b,n,&compare,&move);cout希尔排序结果为：;for(i=0;in;i+) coutbi ;coutn比较次数为compare;coutn移动次数为movenendl;for(i=0;in;i+) ci=ri;Bubblesort(c,n,&compare,&move);cout交换排序结果为：;for(i=0;in;i+) coutci ;coutn比较次数为compare;coutn移动次数为movenendl;compare=0;move=0;for(i=0;in;i+) di=ri;Qsort(d,0,n-1,&compare,&move);cout快速排序结果为：;for(i=0;in;i+) coutdi ;coutn比较次数为compare;coutn移动次数为movenendl;for(i=0;in;i+) ei=ri;Selectsort(e,n,&compare,&move);cout选择排序结果为：;for(i=0;in;i+) coutei ;coutn比较次数为compare;coutn移动次数为movenendl;cout最后输入一个乱序数组endl;coutn;cout请输入数组中的元素：;for(i=0;iri;for(i=0;i