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

《北邮数据结构实验报告-排序》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、北京邮电大学数据结构试验报告实验名称：实验四排序学生姓名：班级：班内序号：学号：日期：2014年1月4日1实验目的学习、实现、对比各种排序算法，掌握各种排序算法的优劣，以及各种算法使用的情况。2实验内容2.1题目1使用简单数组实现下面各种排序算法，并进行比较。排序算法：1、插入排序2、希尔排序3、冒泡排序4、快速排序5、简单选择排序6、堆排序（选作）7、归并排序（选作）8、基数排序（选作）9、其他要求：1、测试数据分成三类：正序、逆序、随机数据2、对于这三类数据，比较上述排序算法中关键字的比较次数和移动次数（其中关键字交换计为3次移动）。3、对于这三类

2、数据，比较上述排序算法中不同算法的执行时间，精确到微秒（选作）4、对2和3的结果进行分析，验证上述各种算法的时间复杂度编写测试main()函数测试线性表的正确性。3程序分析3.1 存储结构顺序存储结构——数组3.2 关键算法分析1.插入排序：依次将待排序的序列中的每一个记录插入到先前排序好的序列中，直到全部记录排序完毕voidInsertsort(intr[],intn,int*compare,int*move)//插入排序{*compare=0;*move=0;inti;intj;for(i=1;i

3、i];for(j=i-1;x=0;j--){(*compare)++;(*move)++;r[j+1]=r[j];}if(j>=0)(*compare)++;r[j+1]=x;}}2.希尔排序：先将整个序列分割成若干个子列，分别在各个子列中运用直接插入排序，待整个序列基本有序时，再对全体记录进行一次直接插入排序voidShellInsert(intr[],intn,int*compare,int*move)//希尔排序{*compare=0;*move=0;intj;1091212202031for(intd=n/2;d>=1;d=d

4、/2)//间距越来越小{for(inti=d;i<=n-1;i++)//从a[d]往后逐个元素确定是否需要前移{if(r[i]=0)&&(x=0)(*compare)++;r[j+d]=x;}else(*compare)++;}}}1.冒泡排序：两两比较相邻记录的关键码，如果反序则交换，直到没有反序记录为止voidBub

5、blesort(intr[],intn,int*compare,int*move)//交换（冒泡）排序{*compare=0;*move=0;intx;for(intj=0;jj;i--){if(r[i]

6、个序列排序完成intPartion(intr[],intfirst,intend,int*compare,int*move)//快速排序中的轴定位{inti=first;intj=end;intzhou=r[i];//默认第一个元素为轴while(i=zhou))//查看右侧元素与轴的大小关系{(*compare)++;j--;}if(i

7、看左侧元素与轴的大小关系{(*compare)++;i++;}if(i

8、are,move);}}1.选择排序：从待排序的记录序列中选择关键码最小的记录并将它与序列中的