线性时间排序

计数排序

计数排序假设 n 个输入元素中的每一个都是在 0 到 max 区间内的一个整数。（max 是数组里最大的数字）

基本思想：对每个输入元素 x，确定小于 x 的元素个数。利用这一信息，就可以直接把 x 放到它的输出数组中的位置了。例如如果有 17 个元素小于 x，则 x 就应该在第 18 个输出位置上。当有几个元素相同时，这一方案就要稍作修改，因为不能把它们放在同一输出位置。

假设输入数组是 A[0 … n]，那么我们还需要两个数组：B[0 … n] 输出数组，C[0 … max] 临时数组。

代理模式（Proxy）

为另一个对象提供一个替身或占位符以控制对这个对象的访问。

栗子

还记得上一个笔记中的糖果机吧，现在产品经理想要一份写着糖果机位置、库存和当前的状态报告。

是不是挺简单的？赶紧写代码。

状态模式（State）

允许对象在内部状态改变时改变它的行为，对象看起来好像修改了它的类。

栗子

现在有一台糖果机，它的状态（挺复杂的）：

• 没有 25 分钱 -> 投入 25 分钱 -> 有 25 分钱
• 有 25 分钱 -> 转动曲柄 -> 售出糖果（数量不为0） | 糖果售罄（数量为0）
• 有 25 分钱 -> 退钱按钮 -> 退出 25 分钱
• 售出糖果 -> 没有 25 分钱

从上面的状态实现代码的步骤：

1. 找出所有状态 -> 共四种：没有 25 分钱、有 25 分钱、售出糖果、糖果售罄。
2. 创建一个持有当前状态的实例变量 state。
3. 写出所有可能发生的动作判断。

适配器模式（Adapter）

将一个类的接口，转换成客户期望的另一个接口。适配器让原本接口不兼容的类可以合作无间。

栗子

欧洲的插座大多是三脚的，而美国的插头大多是两脚的，那么如何让两脚插头插进三脚插座里呢？这就需要一个转换头，作为一个中介，二脚插头先插入转换头，然后转换头再插入三脚插座。

还记得笔记1里的鸭子吧？

模版方法模式（Template）

在一个方法中定义一个算法的骨架，而将一些步骤延迟到子类。模版方法使得子类可以在不改变算法结构的情况下，重新定义算法中的某些步骤。

好莱坞原则：别调用（打电话给）我们，我们会调用（打电话给）你。
（由高层组件决定低层组件的行为，而不是反过来）

栗子

现在你有两种冲泡饮料，分别是咖啡和茶。

咖啡的冲泡过程：

1. 把水煮沸
2. 用沸水冲泡咖啡
3. 把咖啡倒进杯子
4. 加糖和牛奶

茶的冲泡过程：

1. 把水煮沸
2. 用沸水浸泡茶叶
3. 把茶倒进杯子
4. 加柠檬

单例模式（Singleton）

确保一个类只有一个实例，并提供一个全局访问点。

应用场景：线程池、注册表、任务管理器、日志对象、充当打印机、显卡等设备的驱动程序等的对象。

命令模式（Command）

将“请求”封装成对象，以便使用不同的请求，队列或日志来参数化其他对象。命令模式也支持可撤销的操作。

栗子

现在有个万能遥控器，它有五个插槽和五对开关按钮。每个插槽可以插一张存储卡，存储卡里面存的是可以控制的某个电器代码，对应的开关按钮可以控制某个电器开关。（听起来这个遥控器有点奇怪是不是？你把它想像成小霸王游戏机就可以了）

你的任务就是给遥控器上的这些开关按钮编程，让它们可以使用存储卡存的电器命令进而控制电器。

工厂模式（Factory）

定义了一个创建对象的接口，但由子类决定要实例化的类是哪一个。工厂方法让类把实例化推迟到子类。

new

按照之前的原则，使用接口，并 new 一个具体实现：

1

Duck duck = new MallardDuck();

但如果出现一堆相关的具体类时，可能会写出这样的代码：

1
2
3
4
5
6
7
8
9

Duck duck;

if (picnic) { // 在野外，是绿头鸭
	duck = new MallardDuck();
} else if (hunting) { // 在打猎，是诱导鸭
	duck = new DecoyDuck();
} else if (inBathTub) { // 在浴缸，是橡皮鸭
	duck = new RubberDuck();
}

一旦有变化或扩展，就要重新打开这段代码进行检查和修改。通常这样修改过的代码将造成部分系统更难维护和更新，而且也更容易犯错。