20162329 2017-2018-1 《程序设计与数据结构》第三周学习总结

教材学习内容总结

1.查找

---

• 线性查找：

  （对任意数组）顺序的对数组内的元素一个一个的进行比较，直到找到所查找元素。

• 二分查找：

  （对有序数组）先比较整个数组中间的元素如果不是带查找元素，就与待查找元素比较，然后按照大小比较结果对以整个数组中间的元素为界再在分出的两个小数组中的其中一个实行同样的方法，以此类推直到查找到待查找元素为止。

---

2.排序

---

• 选择排序：

  第一趟扫描整个表找出最小的一个元素然后将其与第一位的元素换位，第二趟从数组第二个位置开始扫描整个数组找出最小的元素与第二位元素换位，第三趟从数组第三个位置开始......以此类推，直到数组结束。

• 插入排序：

  最初认为第一个元素是有序的，然后将除有序的元素外其他元素一个一个的插入到有序元素中正确的位置，直到将所有的无序元素都插入到有序序列为止。

• 冒泡排序：

  每次循环将一个位置的元素与它后面位置的元素进行比较，如果有必要就换位置，然后下次循环用后面位置的元素与更后一位的元素进行比较换位，以此类推，每次一轮将会把某一个元素放置到相应位置，直到所有元素都到相应位置为止。

• 快速排序：

  每一趟都用每个数组的第一位元素将数组分为两个（大于或小于该元素）数组，然后在每一个分数组依次的运用此方法，直到排序完成。

• 归并排序：

  递归的将一个数组尽量平分为两部分，然后将分好的两部分再次均分，直到分为单个元素后再开始有序的将这些单个元素进行合并，每次两个一组的合并，直到还原为原本大小的数组为止。

---

教材学习中的问题和解决过程

问题1：

之前一直不理解为什么在查找排序时都要实现Comparable这个接口

解决方法：

查找API文档：

此接口强行对实现它的每个类的对象进行整体排序。这种排序被称为类的自然排序，类的 compareTo 方法被称为它的自然比较方法。

实现此接口的对象列表（和数组）可以通过 Collections.sort（和 Arrays.sort）进行自动排序。实现此接口的对象可以用作有序映射中的键或有序集合中的元素，无需指定比较器。

上周考试错题总结

错题代码：

void fun3(int n){     int i=0,s=0;    while (s<=n){         i++;         s=s+i;    }}

计算以上代码的算法复杂度：

我的答案：O(n) 正确答案：O(n^1/2)

计算步骤：

1. n = 1 + 2 + 3 + ... + T(n)
2. n = T(n)*(T(n) + 1) / 2
3. n = [ T(n)^2 + T(n) ] / 2
4. 复杂度为O(n^1/2)

结对及互评

这周我们学习的主要为排序和查找，因为课上老师说要考试，我和我的搭档还一起去图书馆一起讨论了双方对代码的理解，取长补短，各有进步，希望以后能增加这样讨论的次数，对我们彼此都有很好的帮助。

点评模板：

• 博客中值得学习的或问题：
  • 界面很好看
  • 问题分析可以更详细

• 其他

  希望我们结对在这学期能相互促进，技术更上一层楼。

  本周结对学习情况

  • 结对学习内容
    • 一起讨论学习。

其他

通过这周的学习发现，一个假期缺少练习，对一些很基础的代码结构都已经不太熟悉了，导致在代码实现的时候总是出现一些很低级的错误，希望接下来的自己加快脚步尽快进入学习状态，提高自己的水平。

学习进度条

	代码行数（新增/累积）	博客量（新增/累积）	学习时间（新增/累积）	重要成长
目标	5000行	30篇	400小时
第一周	0/200	1/2	10/20	了解数据结构及算法
第二周	664/500	2/3	10/20	系统的学习了查找和排序

参考资料

• ...