北邮数据结构实验报告实验四排序含源码.doc

《北邮数据结构实验报告实验四排序含源码.doc》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、数据结构实验报告实验名称：实验4——排序学生姓名：申宇飞班级：2012211103班内序号：03学号：2012210064日期：2013年12月18日1．实验要求使用简单数组实现下面各种排序算法，并进行比较。排序算法：1、插入排序2、希尔排序3、冒泡排序4、快速排序5、简单选择排序6、堆排序（选作）7、归并排序（选作）8、基数排序（选作）9、其他要求：1、测试数据分成三类：正序、逆序、随机数据2、对于这三类数据，比较上述排序算法中关键字的比较次数和移动次数（其中关键字交换计为3次移动）。3、对于这三类数据，比较上述排序算法中不同算法的执行时间，

2、精确到微秒（选作）4、对2和3的结果进行分析，验证上述各种算法的时间复杂度编写测试main()函数测试线性表的正确性。2.程序分析（1）、设计一个菜单，格式如下：1、直接插入排序2、希尔排序3、冒泡排序4、快速排序5、选择排序6、堆排序7、退出（2）、选择不同的菜单但进行相应的排序，并给出排序的关键字序列。2.1存储结构2.2关键算法分析本程序包含了9个函数，它们分别是：（1）、直接插入排序的算法函数InsertSort（）。voidInsertSort(SqList&L){inti,j;for(i=2;i<=L.length;i++){if(

3、L.r[i].key0){dk/=3;//减小增量for(i=dk;i<=L.leng

4、th;i++){L.r[0].key=L.r[i].key;j=i;while((j>=dk)&&(L.r[j-dk].key>L.r[0].key)){L.r[j].key=L.r[j-dk].key;j-=dk;}L.r[j].key=L.r[0].key;}}}（3）、冒泡排序算法函数BubbleSort（）。voidBubbleSort(SqList&L){inti,j;for(i=0;iL.r[j+1

5、].key){flag=0;inttemp;temp=L.r[j].key;L.r[j].key=L.r[j+1].key;L.r[j+1].key=temp;}//若无交换说明已经有序if(flag==1)break;}}（4）、快速排序的算法函数Partition（）。voidBubbleSort(SqList&L){inti,j;for(i=0;iL.r[j+1].key){flag=0;inttemp;

6、temp=L.r[j].key;L.r[j].key=L.r[j+1].key;L.r[j+1].key=temp;}//若无交换说明已经有序if(flag==1)break;}}（5）、选择排序算法函数SelectSort（）。voidSelectSort(SqList&L){intmin;intj;for(inti=0;i

7、n){min=L.r[k].key;j=k;}}if(i!=j){//与第i个记录交换inttemp=L.r[i].key;L.r[i].key=L.r[j].key;L.r[j].key=temp;}}}（6）、堆排序算法函数HeapAdjust（）。voidHeapAdjust(HeapType&H,ints,intm)第6/10页//堆调整，将记录调整为小顶堆intj;RedTyperc=H.r[s];//暂时存储根结点for(j=2*s;j<=m;j*=2){//沿着结点记录较小的向下筛选if(j

8、+1].key)++j;if(rc.key>=H.r[j].key)break;H.r[s]=H.r[j];s=j;}H.r[s]=rc;}voidH