数据结构实验五-查找与排序的实现

1、实 验 报 告课程名称 数据结构 实验名称 查找与排序的实现 系别 专业班级 指导教师11 学号 姓名 实验日期 实验成绩 一、实验目的(1) 掌握交换排序算法（冒泡排序）的基本思想；(2) 掌握交换排序算法（冒泡排序）的实现方法；(3) 掌握折半查找算法的基本思想；(4) 掌握折半查找算法的实现方法；二、实验内容1. 对同一组数据分别进行冒泡排序，输出排序结果。要求：1) 设计三种输入数据序列：正序、反序、无序2) 修改程序：a) 将序列采用手工输入的方式输入b) 增加记录比较次数、移动次数的变量并输出其值，分析三种序列状态的算法时间复杂性2. 对给定的有序查找集合，通过折半查找与给定值k相

2、等的元素。3. 在冒泡算法中若设置一个变量lastExchangeIndex来标记每趟排序时经过交换的最后位置，算法如何改进？三、设计与编码1.本实验用到的理论知识2.算法设计3.编码package sort_search;import java.util.Scanner;public class Sort_Search /冒泡排序算法public void BubbleSort(int r) int temp;int count=0,move=0;boolean flag=true;for(int i=1;ir.length&flag;i+)flag=false;count+;for(int

3、 j=0;jrj+1)temp=rj;rj=rj+1;rj+1=temp;move+;flag=true;System.out.println(排序后的数组为：);for(int i=0;ir.length;i+)System.out.print(ri+ );System.out.println();System.out.println(比较次数为：+count);System.out.println(移动次数为：+move);public static int BinarySearch(int r,int key) /折半查找算法int low=0,high=r.length-1;while

4、(lowkey)high=mid-1;elselow=mid+1;return -1; /测试public static void main(String args) Sort_Search ss=new Sort_Search();int t=new int13;System.out.println(依次输入13个整数为：);Scanner sc=new Scanner(System.in);for(int i=0;it.length;i+)ti=sc.nextInt();System.out.println(排序前的数组为： );for(int i=0;i0)System.out.prin

5、tln(k+ 在数组中的位置是第： + BinarySearch(t,k);elseSystem.out.println(k+ 在数组中查找不到！); 四、运行与调试1. 在调试程序的过程中遇到什么问题，是如何解决的？问题：在计算比较次数和移动次数时，计算数据明显出错。原因：在进行移动和比较的过程中，没有更新标志，导致计数出错。解决办法：在比较和移动的过程中，有进行比较和移动的操作时，更新标志。然后按标志计数。2. 设计了哪些测试数据？预计结果是什么？说明： 测试了int类型数据： 241 17 23 45 37 4 31 43 11 89 33 101 177 预计排序后结果为：4 11 17 23 31 33 37 43 45 89 101 177 241 比较次数： 无序：8次 正序：1次 反序：12次 移动次数： 无序：30次 正序：0次 反序：78次 查找数33的位置为：5 查找数101的位置为：10 查找数100的结果为：查找不到3. 程序运行的结果如何 I.无序输入：II.正序输入：III.反序输入： 五、总结与心得六、思考题已知奇偶转换排序如下：第一趟对所有奇数的i，将ai和ai+1进行比较，第二趟对所有偶数的i,将ai和ai+1进行比较,每次比较时若