分类目录：《算法设计与分析》总目录
相关文章：
· 顺序统计量：最大值与最小值
· 顺序统计量：期望为线性时间的选择算法
· 顺序统计量：最坏情况为线性时间的选择算法
在一个有 n n n个元素的集合中，我们可以很容易地给出 n − 1 n-1 n−1次比较这个上界来确定其最小元素：依次遍历集合中的每个元素，并记录下当前最小元素。当然，最大值也可以通过 n − 1 n-1 n−1次比较找出来。
这的确就是我们能得到的最好结果吗。对于确定最小值问题，我们可以得到其下界就是 O ( n ) O(n) O(n)次比较。对于任意一个确定最小值的算法，可以把它看成是在各元素之间进行的一场锦标赛。每次比较都是锦标赛中的一场比赛，两个元素中较小的获胜。需要注意的是，除了最终获胜者以外，每个元素都至少要输掉一场比赛。因此，我们得到结论：为了确定最小值，必须要做 O ( n ) O(n) O(n)次比较。因此，从所执行的比较次数来看，上述算法就是最优的。
同时找到最小值和最大值在某些应用中，我们必须要找出一个包含 n n n个元素的集合中的最小值和最大值。例如，一个图形程序可能需要转换一组 ( x , y ) (x, y) (x,y)数据，使之能适合一个矩形显示器或其他图形输出装置。为了做到这一点，程序必须首先确定每个坐标中的最小值和最大值。
就这一点来说，用渐近最优的 Θ ( n ) Theta(n) Θ(n)次比较，在 n n n个元素中同时找到最小值和最大值的方法是显然的：只要分别独立地找出最小值和最大值，这各需要 n − 1 n-1 n−1次比较，共需 2 n − 2 2n-2 2n−2次比较。
事实上，我们只需要最多 3 ⌊ n 2 ⌋ 3lfloorfrac{n}{2}rfloor 3⌊2n⌋次比较就可以同时找到最小值和最大值。具体的方法是记录已知的最小值和最大值，但我们并不是将每一个输入元素与当前的最小值和最大值进行比较。这样做的代价是每个元素需要2次比较，而是对输入元素成对地进行处理。首先，我们将对输入元素相互进行比较，然后把较小的与当前最小值比较，把较大的与当前最大值进行比较。这样，对每两个元素共需3次比较。
如何设定已知的最小值和最大值的初始值依赖于 n n n是奇数还是偶数。如果 n n n是奇数，我们就将最小值和最大值的初值都设为第一个元素的值，然后成对地处理余下的元素。如果 n n n是偶数，就对前两个元素做一次比较，以决定最小值和最大值的初值，然后与 n n n是奇数的情形一样，成对地处理余下的元素。
下面来分析一下总的比较次数。如果 n n n是奇数，那么总共进行 3 ⌊ n 2 ⌋ 3lfloorfrac{n}{2}rfloor 3⌊2n⌋次比较。如果 n n n是偶数，则是先进行一次初始比较，然后进行 3 ∗ n − 2 2 3*frac{n-2}{2} 3∗2n−2次比较，共 3 n 2 − 2 frac{3n}{2}-2 23n−2次比较。因此，不管是哪一种情况，总的比较次数至多是 3 ⌊ n 2 ⌋ 3lfloorfrac{n}{2}rfloor 3⌊2n⌋。