北邮数据结构实验四题目1

《北邮数据结构实验四题目1》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、北邮数据结构实验报告实验名称：实验四排序学生姓名：XXX班级:XXX班内序号：XX学号：XXX口期：2013年12月20口1.实验要求a.实验目的通过实现K述实验内容，学习、实现、对比各种排序算法，掌握各种排序算法的优劣，以及各种算法使用的情况。b.实验内容使用简单数组实现下面各种排序算法，并进行比较。排序算法：1、插入排序2、希尔排序3、冒泡排序4、快速排序5、简单选择排序6、堆排序7、归并排序8、基数排序（选作）9、其他1.程序分析2.1存储结构存储结构：顺序存储结构示意图如下：aOala2a3a4a5a6a7a8a9顺序数组存储结构2.2关键算法分析核心算法思想：1.利用教材讲述的基本

2、算法思想，实现七种排序算法，统计其运行相关数据。2.将数组名当做地址传入函数，实现快速调用和统计。使得程序代码可读性增、结构更加优化。关键算法思想描述和实现：关键算法1:实现七种算法的基本排序功能。1、插入排序：依次将待排序的序列中的每一个记录插入到先前排序好的序列中，直到全部记录排序完毕。2、希尔排序：先将整个序列分割成若干个子列，分别在各个子列屮运用直接插入排序，待整个序列基本有序时，再对全体记录进行一次直接插入排序。3、冒泡排序：两两比较相邻记录的关键码，如果反序则交换，直到没有反序记录为止。4、快速排序：首先选择一个基准，将记录分割为两部分，左支小于或等于基准，右支则大于基准，然后对

3、两部分重复上述过程，直至整个序列排序完成。5、选择排序：从待排序的记录序列中选择关键码最小(或最大)的记录并将它与序列中的第一个记录交换位置;然后从不包括第一个位置上的记录序列中选择关键码最小(或最大)的记录并将它与序列屮的第二个记录交换位置;如此重复,直到序列屮只剩下一个记录为止。6、堆排序：通过建立大根堆或者小根堆，取山根节点，反复调整堆使之保持大根堆或者小根堆，直至最后序列有序。7、归并排序：将若干个有序序列两两归并，直至所有待排序的记录都在一个有序序列为止。C++实现：voidInsert(intr[]，intn)//直接插入排序，升序{intcompare=0,move=0;定义比

4、较和移动的系数并初始化为零，以下相同不再叙述for(inti=2;i

5、//希尔排序intcompare=0，move=0;for(intd=n/2;d〉=l;d=d/2){for(inti=d+l;i0&&rf01

6、后的冒泡排序{intcompare=0,move=0;intpos=n;whi1e(pos!=0)判断循环的结朿条件，下面会有介绍{intbound=pos;pos=0;令pos初始化为0,之后如果没有进入循环修改其值则跳出while循环for(inti=l;i=pivot))右侧扫瞄，大于哨兵的不动r[O]=r[i];r[i]=r[i+l]；r[i+l]=r[O];pos=

7、i+l;move++;compare++;}}cout«n比较次数："〈〈comparecc”移动次数：n«move«endl;}intPartion(intr[],intfirst,intend,inta,intb)//—次快排头尾哨兵头在尾之前，即尚未遍历数组a++;r[i]=r[j];小小于哨兵的进入哨兵b++;while((i