lec29 Basic Sorts
排序的性质
需要满足两点：
- 三段论：如果
a<b, a=b，那么b<a。 - 传递性：如果
a<b, b<c，那么a<c。
从另一个观点来看，排序就是让数组中的逆序的数量变为 0。
排序
选择排序
简单的算法。每次从数组中选择最小的元素放到前面，那么前面就是从小到大的。重复这个步骤。时间复杂度为 $\Theta(n^2)$。
初始的堆排序
将所有的元素插入 max 堆中，然后重复 N 次：
- 从堆中删除最大的元素
- 将最大的元素放在输出数组未使用的后方
插入总共耗费 $O(n\log(n))$，选择最大元素耗费 $\Theta(1)$，移除最大元素 n 次，每次消耗 $O(\log(n))$。所以总的时间复杂度为 $O(n\log(n))$。
这个方法除了初始数组，还需要新建两个数组：一个为了代表 max 堆，另一个为了储存输出元素。显然，这样对空间的消耗较大。
就地的堆排序
考虑不使用其他数组，而是在输入的基础上使用堆排序。首先，看成是没有排序的堆。因此，需要不断让靠后的元素向上，保证堆的性质。
接着，每次删除最大元素，也就是移除第一个元素，然后将最后一个元素放到第一个元素，下沉。最后消耗 $O(n\log(n))$ 的时间。因为不新建数组，所以空间复杂度为 $\Theta(1)$。
归并排序
将数组分成两部分。分别递归让左右排序好，然后新建数组，分别去除两个有序数组的最小项。时间复杂度为 $\Theta(n\log(n))$，空间复杂度为 $\Theta(n)$。
插入排序
每次对于未排序的第一个元素，在排序的元素中比较，向前交换，直到顺序正确。时间复杂度最低为 $\Omega(n)$，最高为 $O(n^2)$。
如果有一个几乎排序好的数组，那么插入排序很快。
总结
lec30 Quick Sort
插入排序
如果有一个排序好的数组。随机选择一个数字，改变该数字。这时候，最好的算法是什么？答案是插入排序。插入排序的时间消耗正比于逆序的数量。
同时，对于较小的数组，例如数量小于 15，插入排序也很快。
快速排序
背景
假设有一个字典，对应英文和俄文。需要将英文句子里的每个单词翻译成对应的俄文。字典中英文是排序好的，这时候利用二分查找需要 $O(\log(n))$ 的时间。然而，在 60 年代只有磁带来储存，并没有 RAM 的随机读取性能，所以没有二分查找的性能。
所以，可以先排序句子，然后扫描一次磁带。然而，这又涉及到排序句子的问题。
Partitioning
找到数组中某个元素 x，然后移动到位置 j，保证左侧的元素都小于等于 x，右侧的元素都大于等于 x。
可以三次扫描数组，第一次将小于 x 的元素放到新的数组中，第二次找到 x，第三次将大于 x 的元素放入新数组。也可以用双向队列实现。
实现
当选择一个元素，进行 partitioning 后，这个元素已经到了正确的位置。接下来，可以利用递归处理剩下的左右两个部分。
性能
快速排序的性能主要取决于 partition 的操作。在理想的情况下，表现为 $\Theta(n\log(n))$；如果本来就是顺序的，那么此时表现很差，为 $\Theta(n^2)$。
快速排序和 BST 的思想很像。可以利用概率论证明，绝大多数情况下，快速排序的性能是 $\Theta(n\log(n))$。
lec31 Software Engineering II
复杂的代码
复杂的代码有两大特征：
- 依赖性：一块代码不能独自地阅读、理解和修改
- 迷惑性：重要的信息不显然
模块化设计
使用模块化设计可以有效减少复杂性，例如使用帮助函数和帮助类。模块一词可以指代很多东西，例如类、包、一段代码等等。模块之间不可能完全独立，但是需要处理好如何在模块之间传递信息。理想情况下，目标就是尽可能减少模块之间的依赖性。
最好的模块同时具有简单的接口和复杂的实现方式。通过简单的接口，可以简化调用，并且也方便修改。这就实现了隐藏内部的复杂性。例如，利用红黑树实现 Map，就做到了这一点，外界完全不用知道红黑树是怎么实现的。
信息隐藏的反面就是信息暴露。如果在较高的抽象层直接从很低的抽象层操纵事务，就会导致复杂性很高。软件工程师的必要技能之一就是敏锐地察觉到信息暴露的情况。
推荐的做法：
- 创造类和接口，实现封装复杂性。
- 创造 ‘deep’ 的模块，拥有简单的接口和复杂的实现方式。
- 不要过度依赖“暂时分解模块”。
- 战略性，而不是战术性。
- 为你自己隐藏信息。
团队协作
有些团队在各种工作中都做得很好，有的相反。这就引出了团队智力。但是，团队智力并不是个体智力的平均值或最高值。
团队智力与社会关系的敏感度有关，以及成员之间是否充分参与。团队协作和人际关系高度相关。
接受反馈有时候会感觉糟糕。不过，要认识到建设性的反馈肯定是有益的。同时，也要学会正确地提供反馈。