在看《算法导论》的过程中，对排序，选择等算法有了进一步的了解。
最大值，最小值 问题
首先，我们思考一个问题：在长度为n的数组A中找出最小值（最大值），至少需要多少次比较呢？
当然，我们很容易想出一个简单的方法：设置一个变量min，初始值设为A[0], 遍历整个数组进行比较，若当前值比min小，则更新min的值为当前值。
1 | MINIMUM(A) |
用这种方法，我们可以用n-1次比较找出最小值。当然，我们也可以找到最大值，只需把循环中的符号改变一下即可。
那么，这是不是达到最优了呢？是否还能有更少的比较次数？接下来我们来证明n-1次比较已经是下界了，也就是说不可能还有更少的比较次数方案。
证明过程
在寻找最小值的过程中，我们维护一个集合，其中包含所有可能为最小值的元素。初始状态下，集合中包含了所有元素。只有当集合中只剩一个元素时，我们才能将最小值确定下来。每一次比较有一个胜利者（较小值）和一个失败者（较大值），失败者不可能成为最小值，于是遭到淘汰，从集合中去除。每一次比较淘汰一个元素。要想淘汰n-1个元素，至少要进行n-1次比较，故n-1已经是下界（lower bound)了。
同时寻找最大值和最小值 问题
在某些时候，我们需要找出数组中的最大值和最小值。
首先，我们很容易想出一个baseline method：分别用（n-1)次比较找出最大值和最小值。这种方法，我们需要2n-2次比较。
那么这是不是最优方案呢？从直觉上我们可以发现，应该还有更优的方案。因为在这种方法里，寻找最大值与寻找最小值完全分开来，互相没有利用对方的比较，所以很可能会有重复的比较。
这里介绍一个更优的方法：
- 将数组中的元素两两配对，进行比较，标注较小和较大。
- 在较小的
n/2个元素中寻找最小值。 - 在较大的
n/2个元素中寻找最大值。
平均比较次数为：n/2 + (n/2-1) + (n/2-1) = 3n/2-2次比较。
问题：如何证明 同时寻找最大值和最小值 最坏情况下的比较次数至少为3n/2 - 2
与上面的证明过程类似，我们维护两个集合，分别存储可能为最小值的集合MIN和可能为最大值的集合MAX。只有当两个集合中均只剩一个元素时，我们才能成功找出最大值和最小值。
初始状态下，两个集合中均包含数组中所有元素。
首先，我们可以对数组进行两两配对，每一对进行比较。这时，由于参与比较的元素没有重复，每一次比较均可以在两个集合中去除一个元素。于是在n/2次比较后，两个集合中均剩余n/2个元素。
这时，MIN和MAX集合中分别包含n/2个元素，并且没有重复。接下来，有三种比较方式：
- MIN中元素与MAX中元素进行比较。
- MIN中两个元素比较。
- MAX中两个元素比较。
在第一种比较方式中，MIN中元素与MAX中元素进行比较时，有两种结果：如果MIN中元素较小，我们无法去除元素；如果MIN中元素偏大，我们可以在两个集合中分别去除一个元素。由于我们考虑的是最坏情况，所以自然选择第一种结果：无法去除任何一个元素。所以这种比较显然是无意义的。
在第二种方式以及第三种方式中，在一次比较中，无论何种情况，都可以在相应的集合中去除一个元素。
综上分析，我们选择方式二以及方式三进行比较，直至MIN和MAX中均只剩下一个元素时，比较结束。
综上，在最坏情况下，最少需要的比较次数为3n/2 - 2。
注：以上至只考虑了n为偶数情况。n为基数时，原理相同。
寻找第二小的元素问题
如何在n + lgn - 2的比较次数下寻找第二小的元素（以及最小元素）呢？
首先，我们还是用n-1次比较找出最小元素，当然，不再是像一开始一样，以此遍历去比较了。相反的，我们利用分治法的原则，将元素两两配对进行比较，比较完毕后，在较小的n/2个元素中，递归进行两两配对比较，直至最终只剩一个元素…
我们可以用一颗完全二叉树表示以上过程，树的叶子为n个初始元素，比较过程中层层向上，较小的元素一直向上，直至根部只剩一个元素，即最小元素。
接下来，我们分析第二小的元素的特征：由于它只比最小的元素大，比其他的元素都要小，所以在比较的过程中，它一定会在某一层与最小的元素相遇，并被它淘汰。所以我们得出结论：第二小的元素出现在与最小元素比较过的元素中。而每一层一次比较，与最小值比较过的元素一共有lgn个，在其中找出最小元素，需要lgn - 1次比较。
综上，一共需要：n - 1 + lgn - 1 = n + lgn - 2次比较。