20172319 2018.11.19-11.25

实验三《查找与排序》 实验报告

课程名称:《程序设计与数据结构》  学生班级：1723班  学生姓名：唐才铭  学生学号：20172319 实验教师：王志强老师课程助教：张师瑜学姐、张之睿学长实验时间：2018年11月19日——2018年11月25日必修/选修：必修

目录

---

实验内容

1. 实验三-查找与排序-1： 定义一个Searching和Sorting类，并在类中实现linearSearch（教材P162 ）,SelectionSort方法（P169），最后完成测试。
2. 实验三-查找与排序-2： 重构你的代码。
3. 实验三-查找与排序-3： 在Searching中补充查找算法并测试。
4. 实验三-查找与排序-4： 补充实现课上讲过的排序方法：希尔排序，堆排序，二叉树排序等(至少3个)。
5. 实验三-查找与排序-5（选做，加分）： 编写Android程序对各种查找与排序算法进行测试。

---

实验要求

1. 完成蓝墨云上与实验二《树》相关的活动，及时提交代码运行截图和码云Git链接，截图要有学号水印，否则会扣分。
2. 完成实验、撰写实验报告，实验报告以博客方式发表在博客园，注意实验报告重点是运行结果，遇到的问题(工具查找，安装，使用，程序的编辑，调试，运行等)、解决办法（空洞的方法如“查网络”、“问同学”、“看书”等一律得0分）以及分析（从中可以得到什么启示，有什么收获，教训等）。报告可以参考范飞龙老师的。
3. 严禁抄袭，有该行为者实验成绩归零，并附加其他惩罚措施。

---

实验步骤

1. 实验三-查找与排序-1：
   定义一个Searching和Sorting类，并在类中实现linearSearch（教材P162 ）,SelectionSort方法（P169），最后完成测试。
   要求不少于10个测试用例，提交测试用例设计情况（正常，异常，边界，正序，逆序），用例数据中要包含自己学号的后四位
   提交运行结果图。
   （2分）
2. 实验三-查找与排序-2：
   重构你的代码
   把Sorting.java Searching.java放入 cn.edu.besti.cs1723.（姓名首字母+四位学号） 包中（例如：cn.edu.besti.cs1723.G2301）
   把测试代码放test包中
   重新编译，运行代码，提交编译，运行的截图（IDEA，命令行两种）
   （2分）
3. 实验三-查找与排序-3：
   参考http://www.cnblogs.com/maybe2030/p/4715035.html 在Searching中补充查找算法并测试
   提交运行结果截图
   (3分）
4. 实验三-查找与排序-4：
   补充实现课上讲过的排序方法：希尔排序，堆排序，二叉树排序等(至少3个)
   测试实现的算法（正常，异常，边界）
   提交运行结果截图
   （3分，如果编写多个排序算法，即使其中三个排序程序有瑕疵，也可以酌情得满分）
5. 实验三-查找与排序-5（选做，加分）：
   编写Android程序对各种查找与排序算法进行测试
   提交运行结果截图
   推送代码到码云
   （加分3，加到实验中）

前期准备：

1. 预先下载安装好IDEA 。

需求分析：

1. 需要了解各种查找及排序算法的相关知识；
2. 需要理解掌握各种查找及排序算法的相关实现；

---

代码实现及解释

本次实验一共分为五个提交点：

• 实验三-查找与排序-1：
• 要实现的方法有：linearSearch;SelectionSort;
• linearSearch 具体代码如下：

public static Comparable linearSearch(Comparable[] data,Comparable target)    {        int index = 0;        Comparable result = null;        while (result==null && index < data.length)        {            if (data[index].compareTo(target)==0){                result = data[index];            }            else {                index++;            }        }        return result;    }

• SelectionSort 具体代码如下：

public static 
    
     > String selectionSort(int[] data)    {        int min;        T temp;        for (int index = 0; index < data.length-1; index++)        {            min = index;            for (int scan = index+1; scan < data.length; scan++) {                if (data[scan]
    

• 实现结果截图：

  
  

• 实验三-查找与排序-2:

• 实现很简单，只是换个包重构而已。

• 实现结果截图：实验时测试案例代码写错了，打印会造成误解，蓝墨云已给出正确的打印结果，以下只展示部分结果。

  
  

• 实验三-查找与排序-3：

• 补充的查找算法有：二分查找；插值查找；斐波那契查找；树表查找；分块查找；哈希查找。

• 实现结果截图：

  
  

• 实验三-查找与排序-4：

• 补充的排序算法：希尔排序；堆排序；二叉树排序；插入排序；冒泡排序；归并排序；快速排序。

• 运行结果截图：

• 实验三-查找与排序-5：
• 实现结果截图：仅展示部分截图
  

---

测试过程及遇到的问题

• 问题1： 无任何记录。
• 解决：

---

分析总结

---

代码托管

• 
  

---

参考资料