这一讲介绍选最大与最小问题，
首先我们看看什么是选择问题。给定一个集合，它里边含有n个不等的实数， 它的输出就是这里边的第
i 小的元素， 当i=1的时候，就是最小的元素，
当i=n的时候，就是最大的元素。
当位置处在中间的时候，叫做中位元素。
那么什么叫做位置中间呢？当n是奇数的时候， 中位数是唯一的，比如说7个数
之中的第4个数就是中位数。这个时候 i 的大小相当，相当于(n+1)/2。
当n是偶数的时候，可以指定i是(n+1)/2这个位置的数。
这样我们从里边选出第i小的元素呢，就是从这n个数里头找到从小
到大排列，位置处在第i个位置的元素。下边我们看一下选最大的问题。
这个算法呢是顺序比较的算法，这个是输出，
初始呢先把这个值取做第一个数1，
然后它的位置是1，把它顺序地和后边的数进行比较，
那么当这个初值定好以后，max它和8来比较，比较的时候，8比它大，
这样就用更大的数来替换这个值。所以替换以后，这个最大数就是8了，
它是位置第2个数。然后它再和后边的4进行比较， 8比4大，那么这个值不替换，
接着它和后边的17进行比较，比较以后， 17比8大，那么接着把这个
8被替换成17，这就是第4个数，然后 它再和3比，比3大不要改变，
再和12比，比12大也不要改变，那么 最后的这个输出呢就是17，它是原来的
第4个数，这是选最大的算法顺序比较。
那么这个算法在最坏情况的时间呢是n-1， 就是说它要进行n-1次的比较，
这个是它的伪码。在这个伪码里面呢，这个for是一个循环，
那么从这个循环里边，表示是和第2个数，一直到第n个数的，一定要进行n-1次的
比较，都在这个循环来完成。那么这里边的伪码呢表示的是它的比较的
操作，max仍然保持那个最大的数，它和第二个数比较，
如果第i个数要是比max大的时候，就进行替换，把位置记下来。
这就是刚才那个算法的伪码。下面我们看一下
问题，有一个改变的问题，就是选最大和最小同时找，
通常的算法呢可以这样做，我先从里边找出最大的数，用刚才的选最大算法，
做好了以后呢，再把这个最大的数从里边
删掉，然后我就可以在剩下的n-1个数里边 来选最小，选最小的做法和最大一样，只不过我
保留的时候，保留比较中较小的那个数就可以了。所以，这个是
两个过程，先选一次最大，删掉，然后在剩下的数里头选最小，
那么这个算法的工作量呢可以估计一下，n个数里头选最大，最多
要做n-1次的比较，那么在剩下的n-1个数里头我来 选最小，要做n-2次的比较，所以整个的比较次数
是2n-3，这是一个通常的算法。
有没有更好的算法呢？下边来看一下。
这个算法是个分组的算法，我们看到假定这是原来的n个数，
有可能是个，n是个奇数，那么分组的时候，我们先把这些个数两个一组两个一组，
一共分成n/2下取整个组，那这就是 第1组，第2组，一直到最后这个组，
当然有可能会轮空，这是分组。分组以后呢， 下边每个组内的元素来做操作，就是做比较，
每组里头比较出一个大点的和一个小点的数，那么假定上面这一列都是
那些个大的数，下边这一列都是这些比较小的数，每一组的比较小的数，
这是每一组的比较大的数。当这样做完了以后呢，我们就在
这些个比较大的数，每个组里边较大的数和这个轮空的数里边
找它里边的最大的数，那就是整个n个数里边的最大数。当这个做了以后呢，我们再在
剩下的这个每个组的较小的数和这个轮空的数里边来找最小， 这样的话得到的就是整个n个数里头最小，这是
分组的算法。把这个算法写成伪码的时候，是下边这个伪码，第一步就是分组，
然后第二步就是每个组里的两个数比较， 得到n/2个下取整个较小和n/2下取整个较大，然后
我们在所有每个组里的较大，可能再加上一个轮空的元素，加起来 是n/2上取整个元素里边找最大，
那么对应的在n/2上取整个较小元素里边来找最小，
这就是伪码。我们看一下这个算法的时间复杂度。
在组内的比较，每个组要比一次，一共有 n/2下取整个组，要比n/2下取整次，
然后我们要在所有那些较大的数里边找最大，
那么较大的数有多少个呢？是n/2上取整这么多个数，在这么多个数
里头找最大，需要做的比较次数是n/2上取整减1。
同样地，在比较小的数里找最小，它做的工作量
和找最大的工作量是一样的。因此这个地方两倍，这也两倍，就得到了
这样多个操作，比较操作。那把这两部分合到一起，这个操作是
组内的比较，是n/2下取整，那么找最大和最小的比较是这个数，
把它和这一项加起来就是这个
公式，在这个公式中，这个下取整和上取整个符号可以合成一个n，
所以剩下的就是n加上n/2上取整，减2，这个
n可以拿到这个取整号的里面来，最后化简成n/2，3n
3倍n的上取整，减掉2。这就是最坏情况的复杂度。这是一个
算法，分组算法。下边我们再看看能不能用分治的算法来做。
分治的算法可以这么做。把这个数组从中间划分成两个子数组L1和L2，
然后我们递归地在L1中求它的最大 和最小，把这个L1中的最大计作max1，
然后这个是min1，然后递归地在L2中做同样的工作，找出它这个的最大和它
这里边的最小。那么整个数组的最大在哪里边 产生呢？就在这两个max1和max2里面，
它们两个谁大，谁是整个组里边的最大。同样地，这两个小
来比较，比较以后谁更小，就是整个组里边的最小，这就是第四步
和第五步的操作。那么通过这样的操作以后呢，整个数组
里的最大和最小就找到了，这是一个递归的分治的算法。
下面我们看一下这个算法的工作量。假定n是2的幂，
这样情况下呢，它会产生2个子问题，就是n/2规模的两个子问题。
那么在，就是因为它是L1和L2，两个数组。
另外这个2是什么呢？2是当两个子问题的解都产生了以后， 我们要找出整个数组的最大，要比一次，另外
找出整个数组的最小，也要比一次，正好需要两次的比较。
那如果原始的数组规模是2的时候，只要比一次就可以找到它的
最大和最小了。这是递推方程，这个方程的解呢可以通过迭代的办法来做到。
我们看到这就是迭代过程，把这个n等于2的k次幂，代进去，
先把它换元，换元以后我们可以把W(2^k-1)用下边的
这一项来替换，刚好这个是方程的的左部，这一项正好是方程的右部，把它替换
下来，替换了以后呢接着又可以做下去， 最后得到这个结果，也是3n/2的
减掉2，这样一个值。这和刚才分组的算法这个复杂度是一样的。
下面我们看一下选择算法的小结。选最大，
如果要是顺序比较的话，它是n-1次的操作
比较次数；如果选最大和最小，同时选这两个数
可以有两种不同的方法，一种是蛮力的算法，这是2n-3，已经算过了。
那么比较好的算法，改进的算法呢，也可以分成两种，一种是分组比较，
这个是3n/2-2，还有一种是分治，也是3n/2-2，这是第二类更好的算法。
那么从这个结果来看，蛮力算法 这个本身也是最好的算法，
就是顺序比较，这个n-1将来可以证明 所有的选最大的算法都要至少做这么多次的比较，
那么选最大和最小问题呢，它的蛮力算法不好，但是 这两个算法已经是最好的算法了，可以证明
它是所有的选最大最小算法中复杂度最低的算法。