1.最大最小数
同时找到最大最小数最优
算法：
首先让所有的元素参与两两比较，这样总共比较了n/2次，最大数肯定在胜者组中，最小数肯定在败者组中；然后从容量为n/2的胜者组中找到最大的数，最少要比较n/2 - 1次；同理，从容量为n/2的败者组中找到最小的数，最少要比较n/2 - 1次。所以总共需要比较(3n/2)
- 2 次。以上假设n为偶数。奇数同理。2.N个数中第k小的数
按照类似快速排序算 法中的“分类”步骤，任选一个参考数，把整个数组分成左右两部分。左边部分小于参考数，右边部分大于参考数。然后根据左右部分各自包含元素的个数，计算出
要求的元素在哪个数组中。（要求的元素或者是左数组中的第k小数，或者是右数组中第[k-l]小的数。l为左数组的长度）然后递归之。平均情况下时间复杂度是Θ(n)
01
02 int partition(int start, int end)
03 {
04 int i, j, pivot=a[start], temp;
05 i = start;
06 j = end;
07
08 while (i < j)
09 {
10 while (a[i] <= pivot && i < end) i++;
11 while (a[j] >= pivot && j > start) j--;
12 if (i < j)
13 {
14 temp = a[i];
15 a[i] = a[j];
16 a[j] = temp;
17 }
18 }
19 a[start] = a[j];
20 a[j] = pivot;
21 return j;
22 }
23
24
25 int order_statistic(int start, int end, int k)
26 {
27 // 用partition函数把序列分成两半，中间的pivot元素是序列中的第i个
28 int i = partition(start, end);
29 if (k == i)
30 return i; //
返回找到的元素
31 else if (k > i)
32 order_statistic(i+1, end, k); //
从后半部分找出第k-i小的元素并返回
33 else
34 order_statistic(start, i-1, k); //
从前半部分找出第k小的元素并返回
35 }