数据结构实验报告实验六排序算法.doc

昆明理工大学信息工程与自动化学院学生实验报告（ 201 201 学年 第 一 学期 ）课程名称：数据结构 开课实验室： 年 月 日年级、专业、班 学号 姓名 成绩实验项目名称排序算法指导教师 教师评语 教师签名： 年 月 日一.实验内容：排序算法，包括直接插入排序，希尔排序，冒泡排序，快速排序，直接选择排序，堆排序等等。二.实验目的：1.掌握各种查找算法理解和实现；2.增强上机编程调试能力三.主要程序代码分析：void InsertSort(DataType a,int n) /直接插入排序int i,j;DataType temp; /temp是监视哨for(i=0;i-1 & temp.keyaj.key) /查找ai的插入位置aj+1=aj; /将关键字大于ai.key的记录后移j-;aj+1=temp; /插入aivoid SelectSort(DataType a,int n) /选择排序int i,j,small;DataType temp;for(i=0;in-1;i+) /做n-1次选择排序small=i;for(j=i+1;jn;j+) /在当前无序区选关键字最小的记录asmallif(aj.keyasmall.key)small=j;if(small!=i)temp=ai;ai=asmall; /交换ai和 asmallasmall=temp;void BubbleSort(DataType a,int n) /冒泡排序int i,j,flag=1;DataType temp;for(i=1;in & flag=1;i+) /做n-1次排序flag=0;for(j=0;jaj+i.key) /交换记录flag=1;temp=aj;aj=aj+1;aj+1=temp;四.程序运行结果：五.实验总结：排序是数据处理中经常使用的一种重要运算。我们在以前程序设计的时候就接触过，但是经过这次上机实验，我对排序有了更深的认识。以下就是我对排序一些新的认识：冒泡排序属于稳定排序，是一种借助“交换”进行排序的方法。首先要将第一个记录的关键字和第二个记录的关键字进行比较，若为逆序，则将两个记录交换之，然后比较第二个记录与第三个记录的关键字，以此类推，直至第n-1个记录与第n个记录的关键字进行比较为止。 直接插入排序属于稳定的排序，每次从无序表中取出第一个元素，把它插入到有序表的合适位置，使有序表仍然有序。第一趟将待比较的数值与它的前一个数值进行比较，当前一数值比待比较数值大的情况下继续循环比较，依次进行下去，进行了(n-1)趟扫描以后就完成了整个排序过程，结束该次循环。选择排序属于不稳定排序，基本思想是每一趟在n-i+1（i=1，2，n-1）个记录中选取关键字最小的记录作为有序序列中第i个记录。第i趟简单选择排序是指通过n-i次关键字的比较，从n-i+1个记录中选出关键字最小的记录，并和第i个记录进行交换。共需进行n-1趟比较，直到所有记录排序完成为止。希尔排序属于不稳定排序，也是一种属插入排序类，它的基本思想是：先将整个待排记录序列分割称为若干个子序列分别进行直接插入排序，待整个序列中记录“基本有序”时，