数据结构实验3——排序

《数据结构实验3——排序》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

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

2、的执行吋间，精确到微秒（选作）4、对2和3的结果进行分析，验证上述各种算法的吋间复杂度编写测试main（）a数测试排序算法的正确性。2.1存储结构顺序存储结构——数组aOala2a3a4a5a62.2关键算法分析1.插入排辰依次将待排序的序列111的每一个记录插入到先前排序好的序列屮，直到全部记录排序完毕voidInsertsort(intr[_,intn){for(inti=2;i<=n;i++){if(r[i]

3、]=r[jl；r[j+1]=r[0];}}2.希尔排序：先将整个序列分割成若干个了列，分别在各个了列屮运用宜接插入排序，待整个序列基本有序时，再对全体记录进行一次直接插入排序voidShellInsert(intr[],intn){intj;for(intd=n/2;d>=1;d=d/2){for(inti二d+1;in;i卄)if(r[i]0&&r[0]

4、则交换，直到没有反序记录为止voidBubbleSort(intr[],intn)intpos=n;while(pos!=0)intbound=pos;pos=0;for(inti=1;ir[i+1]){r[0]=r[i];r[i]=r[i+1];r[i+1]=r[0]:pos=i;}})3.快速排序：首先选择一个基准，将记录分割为两部分，左支小于或等于基准，右支则大于基准，然后对两部分重复上述过程，直至整个序列排序完成intPartion(intr[],intfirst,intend){inti=f

5、irst;intj二end;intpivot二r[i];while(i=pivot))J—；r[i]=r[j];while((i

6、并将它与序列中的第一个记录交换位置；然后从不包括第一个位置上的记录序列屮选择关键码最小(或最人)的记录并将它与序列中的笫二个记录交换位置；如此重复，直到序列中只剩下一个记录为止voidSelectSort(intr[],intn){for(inti=1;i

7、算法的时间复杂度和空间复杂度，如下表所示:排序方法平均情况最好情况最坏情况辅助空间直接插入排序O(n)oQ）O(n)0（l）希尔排序O（nlog2n）^O（/）oG2）0（1）起泡排序O（J）0（”）oG2）o仃)快速排序O（nlog2n）O（wlog2n）O（n）o（log2?i）〜oG）简单选择排序O（n2）O（J12）O（.n）0（1）3.程序运行结果3.1主函数流程图开始3.2程序运行框图#includeusingnamespacestd;voidprint(intr[J,intn){for(inti=1;i<

8、=n;i++)cout«r[i]«"”;cout«endl;}/*插入排序*/voidInsertsort(intr[],intn){for(inti=2;i<=n;i++){if(r[i]<