20182304 《数据结构与面向对象程序设计》第八周学习总结
教材学习内容总结
- 查找：在某个项目组中寻找某一指定元素目标或确定某一指定元素目标不在项目组中
- 线性查找
- 从头开始依次比较每一个值直至结尾，若找到指定元素返回索引值，否则返回false
- 线性查找的平均时间复杂度为O(n)
- 二分查找
- 在一个已排序的组中，从列表的中间开始查找，如果中间元素不是要找的指定元素，则削减一半查找范围，从剩余一半的查找范围中继续以与之前相同的方式进行查找，多次循环直至找到目标元素或确定目标元素不在查找范围中
- 特点：二分查找要求所查找的组必须是有序的。每次比较都会减少一半的查找元素，在元素较多时，查找效率相对较高
- 二分查找的平均时间复杂度为O(log2n)
- 我们课上另外学了三种查找方法，哈希线性查找、哈希链表查找、二叉树查找，这几个查找方法效率相对更高，但是算法实现比较复杂
- 二叉树查找就是利用链表形成一个二叉树，比父节点大的在右边，比父节点小的在左边，查找时顺着二叉树向下查找
- 哈希线性查找：线性探测再散列，若关键字对应地址非空，向后移位直到找到空地址存入，查找步骤与之相同
- 哈希链表查找：将存储空间定义为链表数组，每一个存储空间都代表一个链表的表头，若出现冲突，直接延长链表的长度，查找顺序与存入顺序相同
- 排序：排序是按某种标准将一列数据项按确定的次序重排的过程
- 算法稳定性：相同元素排序后先后次序是否发生变化
- ASL（平均查找性能分析）：查找所有元素需要进行的比较次数之和/元素总个数
- 选择排序
- 原理：通过反复将某一特定值放到它在列表中的最终已排序位置来实现排序
- 冒泡排序：
- 原理：通过反复比较相邻元素的大小并在必要时进行互换，最终实现排序
- 插入排序:
- 原理：重复地将一个具体的值插入到表中已有序的子序列中
- 选择排序、插入排序、冒泡排序都有着相近的效率，时间复杂度皆为O(n^2)
- 快速排序：
- 王老师讲解的时候将快速排序比喻为确立一个中轴线(一个元素），进行分区，将其他元素按照与这个元素比较的结果放在不同的两个分区，当指针相遇时，一轮排序结束，把这个元素放回去，进行下一轮排序
- 快速排序每次要将列表分成两个分区，因此平均要进行log2n次分区，而每次分区后要进行n次比较操作，因此平均时间复杂度为O(nlogn)
- 快速排序是一种不稳定的算法，但是一般来讲，快速排序的效率最高。例如数列3 3 4 9，标记第一个3为3，如果采用某种排序后3的位置排在了3后，则称这个算法是不稳定的。快速排序时就需要考虑这样的问题，即遇到相同元素时是否需要进行交换，交换就可能导致不稳定，因为次序改变了，所以快速排序并不是一个稳定的算法。
- 归并排序：
- 通过将列表进行递归式分区直至最后每个列表中都只剩余一个元素后，将所有列表重新按顺序重组完成排序。
- 归并排序的平均时间复杂度为O(nlogn)
教材学习中的问题和解决过程
- 问题1：静态方法：使用时不需要实例化该类的一个对象，可以直接通过类名来激活的方法。可以通过在方法声明中使用static修饰符将方法声明为静态的。
- 问题1解决方案：泛型是一种可以存储、操作和管理在实例化之前没有指定类型的对象的一个类，通常用作为标识符。泛型不能被实例化，它只是一个占位符，允许我们去定义管理特定类型的对象的类。
泛型和Object类比较起来有很大不同，Object是一个可以实例化的变量，要进行强制转换才能赋给别的数据类型变量。而泛型T从一开始就被限定了。在之前的安卓作业中，我设置的泛型在比较时不能强制转化，最后只能改变成固定类型int
- 问题2：
- 问题2解决方案：选择排序、插入排序、冒泡排序都有着相近的效率，时间复杂度皆为O(n^2)，但是插入排序的最优情形依赖于初始数据的情况，可以为O(n)。通过对比可以发现，快速排序比大部分排序算法都要快。尽管我们可以在某些特殊的情况下写出比快速排序快的算法，但是就通常情况而言，没有比它更快的了。但是快速排序的稳定性较差，如果需要一个稳定性较好且排序较快的排序算法的话，可以选择使用归并排序，但是归并排序同样存在缺点，因为它需要一个额外的数组，因此对内存空间有一定的要求。
代码调试中的问题和解决过程
问题1：
- 问题1解决方案：
- 问题2：
问题2解决方案：
（
）
上周考试错题总结
- 无
结对及互评
点评模板：
- 博客中值得学习的或问题：
- 代码中值得学习的或问题：
基于评分标准，我给本博客打分：14分。
参考示例
点评过的同学博客和代码
- 本周结对学习情况
- 20182302
- 结对学习内容
- 栈的pop,push,isEmpty，expandCapacity，peek
- 利用安卓实现相关代码
- 队与栈的区别和联系
- 上周博客互评情况
其他（感悟、思考等，可选）
- 链表和数组使用时都需要特殊注意，否则很容易就会发生地址越界
学习进度条
| 目标 |
5000行 |
30篇 |
400小时 |
|
| 第五周 |
1600/2900 |
2/11 |
20/110 |
|
| 第六周 |
981 /3881 |
2/12 |
25/135 |
|
| 第八周 |
1700/5518 |
3/15 |
45/180 |
|
| 第四周 |
300/1300 |
2/9 |
30/90 |
|
尝试一下记录「计划学习时间」和「实际学习时间」，到期末看看能不能改进自己的计划能力。这个工作学习中很重要，也很有用。
耗时估计的公式：Y=X+X/N ，Y=X-X/N，训练次数多了，X、Y就接近了。
参考：软件工程软件的估计为什么这么难，软件工程 估计方法
计划学习时间:30小时
实际学习时间:25小时
改进情况：
(有空多看看现代软件工程 课件
软件工程师能力自我评价表)
参考资料
# 20182304 《数据结构与面向对象程序设计》第八周学习总结
原文：https://www.cnblogs.com/acgacg/p/11790385.html
