1. 查找最小值
逻辑比较简单，用第一个元素来初始化最小值min，
然后与数组中其余元素比较，找出最小值。
时间复杂度是O(n)，已经最优化了。
int minimum(int A[], int len)
{
int min = A[0];
int i;
for (i = 2; i < len; i++)
if (A[i] < min)
min = A[i];
return min;
}2. 同时找最大和最小值
如果依然采用前面的方法，用第一个元素初始化min和max。
然后将min和max与数组的其他n - 1个元素比较，每次循环比较两次。
那么一共需要2n - 2次比较。
int min_max(int A[], int len, int *min, int *max)
{
// 若是偶数，则根据前两个元素比较结果来初始化min和max。
// 若是奇数，则用第一个元素初始化min和max，现在剩余元素也为偶数个了。
if (len % 2 == 0) {
if (A[0] < A[1]) {
*min = A[0];
*max = A[1];
} else {
*min = A[1];
*max = A[0];
}
} else {
*min = *max = A[0];
}
// 若为偶数就从第三个元素开始处理，奇数就从第二个元素。
// 循环每次处理一对元素。
int i;
for (i = (len % 2 == 0 ? 2 : 1); i < len - 1; i += 2) {
// 用这一对元素中的大者与max比较，小者与min比较
// 偶数时：需要(n - 2) / 2 * 3 + 1 次比较
// 奇数时：需要(n - 1) / 2 * 3 次比较
if (A[i] < A[i + 1]) {
if (A[i] < *min)
*min = A[i];
if (A[i + 1] > *max)
*max = A[i + 1];
} else {
if (A[i + 1] < *min)
*min = A[i + 1];
if (A[i] > *max)
*max = A[i];
}
}
}
int main(void)
{
int A[] = { 12, 5, 9, 10, 7, 3, 15, 20 };
int min = minimum(A, 8);
printf("%d\n", min);
int max;
min_max(A, 8, &min, &max);
printf("%d, %d\n", min, max);
int B[] = { 12, 5, 9, 10, 7, 3, 15, 20, 1 };
min_max(B, 9, &min, &max);
printf("%d, %d\n", min, max);
return 1;
}
3. 找到次小值（习题9.1-1）
“在算法导论中习题9-1提出，在最坏情况下利用 n
+ logn - 2 次比较，找出n个元素中第二小的元素。
其方法叫做 tournament method, 算法实现如下:
对数组a[1…n] 中元素成对的做比较，每次比较后讲较小的数拿出，形成的数组再继续这样处理，直到剩下最后的一个，就是数组中最小的那个。将这个过程以一个树的形式表现出来,如下图：
在这个过程中，非树叶节点就是比较的次数，一共进行了n-1 次比较，树根即为最小的元素。而第二小的元素一定是在这个过程中与根节点进行过比较的元素。即上图中5，3和2。这样的节点最多有logn个，在这些节点中找到最小的元素需要进行logn-1次比较。因此总共所需的比较次数为 n-1
+ logn-1 = n+logn-2次”。
其方法叫做 tournament method, 算法实现如下:
对数组a[1…n] 中元素成对的做比较，每次比较后讲较小的数拿出，形成的数组再继续这样处理，直到剩下最后的一个，就是数组中最小的那个。将这个过程以一个树的形式表现出来,如下图：
解决问题的关键是：用树形结构来表示整个比较过程。