中位数和顺序统计量

在一个由 n 个元素组成的集合中，第 i 个顺序统计量(order statistic)是该集合中第 i 小的元素。一个中位数(median)是它所属集合的“中点元素”。当n为奇数时，中位数是唯一的，位于 i = (n + 1) / 2。当n为偶数时，存在两个中位数，分别位于 i = n / 2， i = n / 2 + 1 处。一般，中位数都是指下中位数。

中位数

打擂台

同时找到最小值和最大值

在 n 个元素中，同时找到最小值和最大值的方法是显然的：只要分别独立地找出最小值和最大值，这各需要 n-1 次比较，共需 2n - 2 次比较。

事实上，我们只需要最多次比较就可以同时找到最小值和最大值。首先，我们将一对输入元素相互进行比较，然后把较小的与当前最小值比较，把较大的与当前最大值进行比较。这样，每对元素共需3次比较。

如何设定已知的最小值和最大值的初始值依赖于 n 是奇数还是偶数。如果 n 是奇数，我们就将最小值和最大值的初值都设为第一个元素的值，然后成对地处理余下的元素。如果 n 是偶数，就对前两个元素做一次比较，以决定最小值和最大值的初值，然后与 n 是技术的情形式样，成对地处理余下的元素。

下面来分析一下总的比较次数。如果 n 是奇数，那么总共进行 次比较。如果 n 是偶数，则是先进行一次初始比较，然后进行 次比较，总共 次比较。因此，不管是哪一种情况，总的比较次数至多是

例题：NOIP2018普及组初赛第9题

《算法导论》练习9. 1-2 提示：考虑有多少个数成为最大值或最小值的潜在可能，然后分析一下每一次比较会如何影响这些计数。