直接插入排序、冒泡排序、快速排序—于—实验七

宁德师范学院计算机系实验报告（2014—2015学年第一学期）课程名称数据结构实验名称实验七数据的排序与检索专业计算机科学与技术年级2013级学号B2013102141姓名于指导教师毛雁明实验日期2014-12-2实验目的与要求：1、掌握数据结构中的几种常用排序方法：插入排序、快速排序、选择排序等。2、遇到实际问题能够选择适当的排序方法解决。实验设备（环境）：微机、C语言编程环境（VC++）实验内容：给定的数组list[N]={213,111,222,77,400,300,987,1024,632,555}，试分别用直接插入排序、冒泡排序、快速排序对上述数据进行排序。要求：每种排序算法编写为独立的自定义函数且要求输出每趟排序后的数据排列序列情况。实验步骤、实验结果及分析：(1)函数代码#includestdio.h#definen10typedefstruct{intkey;}RecType;typedefRecTypeSeqList[n+1];voidinsertSort(SeqListr){inti,j;for(i=2;i=n;i++){r[0]=r[i];j=i-1;while(r[0].keyr[j].key){r[j+1]=r[j];j--;}r[j+1]=r[0];}}voidbubblesort(SeqListr){inti,j,exchange;for(i=1;in;i++){exchange=0;for(j=n-1;j=i;j--)if(r[j+1].keyr[j].key){r[0]=r[j+1];r[j+1]=r[j];r[j]=r[0];exchange=1;}if(!exchange)break;}}intpartition(SeqListr,inti,intj){RecTypepivot=r[i];while(ij){while(ij&&r[j].key=pivot.key)j--;if(ij)r[i++]=r[j];while(ij&&r[i].key=pivot.key)i++;if(ij)r[j--]=r[i];}r[i]=pivot;returni;}voidquicksort(SeqListr,intlow,inthigh){intpivotpos;if(lowhigh){pivotpos=partition(r,low,high);quicksort(r,low,pivotpos-1);quicksort(r,pivotpos+1,high);}}main(void){intlow=1,high=10;SeqListr={0,213,111,222,77,400,300,987,1024,632,555};inti;insertSort(r);printf(直接插入排序算法：\n);for(i=1;i=n;i++)printf(%-6d,r[i]);printf(\n);bubblesort(r);printf(冒泡排序算法：\n);for(i=1;i=n;i++)printf(%-6d,r[i]);printf(\n);quicksort(r,low,high);printf(快速排序算法：\n);for(i=1;i=n;i++)printf(%-6d,r[i]);printf(\n);}(2)主函数流程图(3)运行结果(4)实验总结本实验主要考查直接插入排序、冒泡排序、快速排序三项函数调用，难度还是有的，需要我们首先理解这三种排序方式，排序实质，然后我们就需要写程序代码，主函数还是很好写的，快速排序算法代码是个难点，还要嵌套一个调用函数需要我们在草稿纸上事先演算下，进行多次调试，达到要求。直接插入排序的方法是首先在当前有序区r[i..i-1]中查找人r[i]的正常插入位置k；然后将r[k..i-1]中的记录均后移一个位置，腾出k位置上的空间插入r[i]。其他方法与这有点不同，画主函数流程图要求我们对代码整体有个框架认识，首先动态分配空间，建立顺序表，然后输入整数进行判断，不符合时继续输入整数，符合时进行选择，然后执行功能，选择退出时，整个程序都退出。虽然经过上学期对C语言半年的学习可以说掌握的基本可以，但是几天不练就会手生，甚至不知如何下手，这时我们要查阅课本，通过这次实验的练习，我在学习数据结构的同时也对C语言进行了一次复习回顾，可谓收获颇丰。指导教师评语：成绩评定教师签字毛雁明2014年12月7日备注：注：1、报告内的项目或设置，可根据实际情况加以补充和调整2、教师批改学生实验报告应在学生提交实验报告10日内