实验报告6 内部排序

1、实 验 报 告 课程名称 数据结构与算法 实验学期 2015 年 春季 学期所在学院 交通科学与工程学院 所属专业 交通信息与控制工程系 年级 2012 专业班级 学生姓名 学号 指导教师 实验最终成绩 实验报告（六）实验题目内部排序实验时间2015 年06 月 29日实验地点B07-B214实验成绩实验性质应用性设计性综合性教师评阅： 实验目的明确；操作步骤正确；设计文稿（表格、程序、数据库、网页）符合要求； 保存路径正确；实验结果正确；实验分析总结全面；实验报告规范；其他： 评阅教师签名：一、实验目的1 理解各种方法的排序过程及其依据的原则。2 能够根据算法设计的具体要求，正确编写程序实现

2、各类内部排序方法。3 了解各种排序方法的时间复杂度、空间复杂度和稳定性的差异。二、实验内容和要求(说明算法的时间复杂度)1) 给定一个不少于十个关键字的数列，编写直接插入排序算法，将数列调整为非递增有序的序列(以0号单元作为监视哨)。2) 给定一个不少于十个关键字的数列，编写快速排序算法，将数列调整为非递减有序的序列(以最后一个关键字作为枢纽)。三、主要设计思想与算法 （此处不够可加页，或在反面书写）1.插入排序。voidinsert_sort(int*array,unsignedintn)inti,j;inttemp;for(i=1;i0&*(array+j-1)temp;j-)*(arra

3、y+j)=*(array+j-1);*(array+j)=temp;2. 快速排序。void sort(int *a, int left, int right) if(left = right)/如果左边索引大于或者等于右边的索引就代表已经整理完成一个组了/ return ; int i = left; int j = right; int key = aleft; while(i j) /控制在当组内寻找一遍/ while(i j & key = aj) /而寻找结束的条件就是，1，找到一个小于或者大于key的数（大于或小于取决于你想升 序还是降序）2，没有符合条件1的，并且i与j的大小没有

4、反转/ j-;/向前寻找/ ai = aj; /找到一个这样的数后就把它赋给前面的被拿走的i的值（如果第一次循环且key是 aleft，那么就是给key）/ while(i = ai) /这是i在当组内向前寻找，同上，不过注意与key的大小关系停止循环和上面相反， 因为排序思想是把数往两边扔，所以左右两边的数大小与key的关系相反/ i+; aj = ai; ai = key;/当在当组内找完一遍以后就把中间数key回归/ sort(a, left, i - 1);/最后用同样的方式对分出来的左边的小组进行同上的做法/ sort(a, i + 1, right);/用同样的方式对分出来的右边的

5、小组进行同上的做法/ /当然最后可能会出现很多分左右，直到每一组的i = j 为止/ while(i j) /控制在当组内寻找一遍/ while(i j & key = aj) /而寻找结束的条件就是，1，找到一个小于或者大于key的数（大于或小于取决于你想升 序还是降序）2，没有符合条件1的，并且i与j的大小没有反转/ j-;/向前寻找/ ai = aj;/找到一个这样的数后就把它赋给前面的被拿走的i的值（如果第一次循环且key是 aleft，那么就是给key）/ while(i = ai) /这是i在当组内向前寻找，同上，不过注意与key的大小关系停止循环和上面相反，因为排序思想是把数往两

6、边扔，所以左右两边的数大小与key的关系相反/ i+; aj = ai; ai = key;/当在当组内找完一遍以后就把中间数key回归/ sort(a, left, i - 1);/最后用同样的方式对分出来的左边的小组进行同上的做法/ sort(a, i + 1, right);/用同样的方式对分出来的右边的小组进行同上的做法/ /当然最后可能会出现很多分左右，直到每一组的i = j 为止/四、实验结果（可以截图描述实验结果）五、实验分析总结(时间复杂度，以及实验过程中的心得体会)通过这次实验，我练习了书写插入排序和快速排序的算法。插入排序是O（n）级别的算法，而快排是在O（nlogn）级别的算法，但不稳定。快速排序适合在数列有序程度较低的情况下使用，这样可以发挥其最佳功能，如果数列基本有序，则用冒泡算法和插入算法较好。特别是在数据量