今天是第11周课程的第一课。

有同学对排序算法表现出了极大的兴趣，还有的表示面向对象编程的原则太干巴巴了，不好理解。今天的课程我就换一个主题，讲点有趣的东西吧。

这是我们小密圈《进击的Java新人》课程第一次涉及算法设计之类的知识。算法设计是一个比较有趣的话题，我们后面要讲的很多与查找，排序有关的知识和数据结构，如果能先学会算法设计，就会有更加深刻的认识。

Algorithm，算法，这个东西，就是解决问题的方法而已。没什么高深的。比如说，大家都熟悉的一个高斯的故事，就是高斯上小学的时候，老师让计算从1加到100的和是多少，其他同学都是手动去算了，只有高斯利用等差数列求和公式迅速得到答案。解决问题的两种思路，这就是两种算法。我们以前介绍过时间复杂度的问题，很明显，计算99次加法，得到结果，这个算法的时间复杂度是O(n)，而直接使用公式一次乘法求得结果的时间复杂度是O(1)。这是算法的一个例子。

再来一个段子，一个小姑娘在图书馆借了一大摞书，抱着出门，警报响了，小姑娘正准备一本本地去试看是哪一本还没有消磁，管理员大妈惊呼：“这得试到什么时候了." 然后大妈就把书分了两半，去试一下没有响，再把剩下的那一半书再分两半。大妈的这种解法就叫分治。这也是算法设计的一个例子。小姑娘的解法的时间复杂度是O(n)，大妈解法的时间复杂度是O(log n)。当然，段子下面早就有人回复：如果不止一本书没有消磁，大妈解法就挂了。可见，设计一个正确的算法并不是一件很容易的事情。

我们今天介绍的主题是贪心算法。这是相对比较容易的一种算法。我这里不敢给出严格定义，因为我当年领悟贪心和动态规划的无后效性用了三年时间。从我第一次听说无后效性到终有一天恍然大悟，总共用去了一千天。所以，我这里就不讲定义，咱们直接看例子。

贪心算法，如果不用手动证明一个问题的数学性质的话，其实是比较简单的。看这样一个例子：假设有一个背包，其最大容量是50KG，现在有各种不同价值的液体，比方说，有水，其价值是10 每千克，共100KG；酒精，其价值是20 每千克，共30KG；有油，价值25每千克，共30KG。问什么样的方案才能使得背包里装的液体的总价值最大？显然，这是一道小学生都会的题目，拣贵的装呗。这谁不会。那就是把30KG油先装了，因为油最贵嘛，剩下20KG的容量装酒精，因为酒精比水贵。

好，那么，这个思维过程就是贪心：每一阶段做决策都找出当前条件下的最优解。当然这个问题，这种解法的正确性显而易见，贪心类的问题最难的地方在于正确性无法证明。这个我们先不管。毕竟我们不是在做算法研究，我们只要能用贪心去解决具体的编程问题就行了。

再看一个简单的例子。在商店找零，比如说，售货员要找给你37块钱，那什么样的方案才是找钱的张数最少的方案呢？肯定是找回的零钱面值越大，最后的张数越少。所以我们可以使用贪心的方法来解决这个问题。先找一张20的，如果再找一张20的，那就超过37了，这不行，所以就再找一张10块的，然后是5块的和两张一块的。最终的方案就得到了，这也是一次典型的贪心计算方案。

在贪心的思想的指导下，也设计了一种排序算法，这种算法被称为选择排序。排序的思想很简单。既然我的目标是把一堆数字从小到大排，那么我按阶段解决这个问题不就好了么？第一步找到最小的那个数把它放到第一位，第二步在剩下的所有数里再找最小的，把它放到第二位，依次类推。