文章来自网络加课本：

   本次学习的内容讨论的问题是在一个由n个不同数值构成的集合中选择第i个顺序统计量问题。主要讲的内容是如何在线性时间内O(n)时间内在集合S中选择第i小的元素，最基本的是选择集合的最大值和最小值。一般情况下选择的元素是随机的，最大值和最小值是特殊情况，书中重点介绍了如何采用分治算法来实现选择第i小的元素，并借助中位数进行优化处理，保证最坏保证运行时间是线性的O(n)。

1、基本概念

　　顺序统计量：在一个由n个元素组成的集合中，第i个顺序统计量是值该集合中第i小的元素。例如最小值是第1个顺序统计量，最大值是第n个顺序统计量。

      中位数：一般来说，中位数是指它所在集合的“中间元素”，当n为奇数时，中位数是唯一的，出现位置为n/2；当n为偶数时候，存在两个中位数，位置分别为n/2（上中位数）和n/2+1（下中位数）。

2、选择问题描述

　　输入：一个包含n个（不同的）数的集合A和一个数i，1≤i≤n。

     输出：元素x∈A，它恰大于A中其他的i-1个元素。

最直接的办法就是采用一种排序算法先对集合A进行排序，然后输出第i个元素即可。可以采用前面讲到的归并排序、堆排序和快速排序，运行时间为O(nlgn)。接下来书中由浅入深的讲如何在线性时间内解决这个问题。

3、最大值和最小值

　　要在集合中选择最大值和最小值，可以通过两两元素比较，并记录最大值和最小值，n元素的集合需要比较n-1次，这样运行时间为O(n)。举个例子来说明，现在要求和集合A={32,12,23,67,45,78}的最大值，开始假设第一个元素最大，即max=1，然后从第二个元素开始向后比较，记录最大值的位置。执行过程如下图所示：

书中给出的求最小值的伪代码如下：

1 MINMUN(A)
2    min = A[1]
3    for i=1 to length(A)
4       do if min > A[i]
5                then  min >= A[i]
6   return min

问题：
（1）同时找出集合的最大值和最小值

方法1：按照上面讲到的方法，分别独立的找出集合的最大值和最小值，各用n-1次比较，共有2n-2次比较。

方法2：可否将最大值和最小值结合在一起寻找呢？答案是可以的，在两两比较过程中同时记录最大值和最小值，这样最大需要3n/2次比较。现在的做法不是将每一个　　　　　　输入元素与当前的最大值和最小值进行比较，而是成对的处理元素，先将一对输入元素进行比较，然后把较大者与当前最大值比较，较小者与当前最小者比较，因此每两个元素需要3次比较。初始设置最大值和最小值方法：如何n为奇数，就将最大值和最小值都设置为第一个元素的值，然后成对的处理后续的元素。如果n为偶数，那么先比较前面两个元素的值，较大的设置为最大值，较小的设置为最小值，然后成对处理后续的元素。这样做的目的保证能够成对的处理后续的元素。举个例子说明这个过程，假设现在要找出集合A={32,23,12,67,45,78,10,39,9,58}最大值和最小值，执行过程如下：

#include<iostream>
using namespace std;


void get_max_min(int a[],int len, int *max, int *min)
{
	int tmp_max, tmp_min;

	if (len % 2 == 0)
	{
		if (a[0] > a[1])
		{
			*max = a[0];
			*min = a[1];
		}
		else{
			*max = a[1];
			*min= a[0];
		}

		for (int i = 2; i < len; i = i + 2)
		{
			if (a[i]>a[i + 1])
			{
				tmp_max = a[i];
				tmp_min = a[i + 1];
			}
			else
			{
				tmp_max = a[i + 1];
				tmp_min = a[i];
			}

			if (*max < tmp_max)
				*max = tmp_max;
			if (*min>tmp_min)
				*min = tmp_min;
		}
	}
	else
	{
		*max = a[0];
		*min = a[0];

		for (int i = 1; i < len; i = i + 2)
		{
			if (a[i]>a[i + 1])
			{
				tmp_max = a[i];
				tmp_min = a[i + 1];
			}
			else
			{
				tmp_max = a[i + 1];
				tmp_min = a[i];
			}

			if (*max < tmp_max)
				*max = tmp_max;

			if (*min>tmp_min)
				*min = tmp_min;
		}
	}
}

int main()
{

	int a[] = { 23, 12, 34, 26, 78, 45, 87, 15, 60, 19, 11 };
	int len = sizeof(a) / sizeof(int);

	cout << len << endl;

	int max_value, min_value;
	get_max_min(a, len, &max_value, &min_value);

	cout << max_value << endl;
	cout << min_value << endl;

	return 0;
}

算法导论-------------中位数和顺序统计学