1、用c语言编写实验程序，随机产生 10个1~20的正数，设计一个高效算法找其中的最大元素和最小元素，并统计元素之间的比较次数。调用该算法执行10次并求元素的平均比较次数。 要求：至少两种算法解决该问题，要根据测试次数及时间复 杂度分析这两种算法的效率并用测试数据加以验证

在C语言中，寻找一组随机产生的10个1到20之间的正数的最大值、最小值以及统计比较次数，可以使用两种不同的策略：

**算法一：线性查找法**

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

// 定义结构体存储数值和比较计数
typedef struct {
    int value;
    int comparisons;
} Number;

int find_min_max(int arr[], int n, int *min, int *max) {
    int comparisons = 0;
    *min = arr[0];
    *max = arr[0];

    for (int i = 1; i < n; ++i) {
        comparisons++;
        if (arr[i] < *min) {
            *min = arr[i];
        } else if (arr[i] > *max) {
            *max = arr[i];
        }
    }

    return comparisons;
}

int main() {
    srand(time(0)); // 初始化随机种子
    int numbers[10];
    for (int i = 0; i < 10; ++i) {
        numbers[i] = rand() % 20 + 1;
    }

    int min_count, max_count;
    int comparisons_avg = 0;

    for (int i = 0; i < 10; ++i) {
        int comparisons = find_min_max(numbers, 10, &min_count, &max_count);
        comparisons_avg += comparisons;
    }

    comparisons_avg /= 10;
    printf("平均比较次数: %d\n", comparisons_avg);

    return 0;
}

**算法二：分治法 - 分而治之（例如快速选择算法）**

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

// 快速选择辅助函数
int partition(int arr[], int low, int high, int pivot_index) {
    int pivot = arr[pivot_index];
    int i = low - 1;
    for (int j = low; j <= high; ++j) {
        comparisons++; // 比较次数自增
        if (arr[j] < pivot) {
            i++;
            std::swap(arr[i], arr[j]);
        }
    }
    std::swap(arr[i + 1], arr[pivot_index]);
    return i + 1;
}

int quick_select(int arr[], int low, int high, int k) {
    int comparisons = 0;
    if (low == high) {
        return arr[low];
    }
    int pivot_index = partition(arr, low, high, rand() % (high - low + 1) + low);
    if (k == pivot_index) {
        return arr[k];
    } else if (k < pivot_index) {
        return quick_select(arr, low, pivot_index - 1, k);
    } else {
        return quick_select(arr, pivot_index + 1, high, k);
    }
}

int main() {
    // ... 同样生成10个随机数 ...

    int min_count, max_count;
    int comparisons_avg = 0;

    for (int i = 0; i < 10; ++i) {
        int min = quick_select(numbers, 0, 9, 0);
        int max = quick_select(numbers, 0, 9, 9);
        comparisons_avg += find_min_max(numbers, 10, &min_count, &max_count);
    }

    comparisons_avg /= 10;
    printf("平均比较次数: %d\n", comparisons_avg);

    return 0;
}

**分析与验证：**
- **线性查找法**: 时间复杂度为O(n)，对于每个查找都需要遍历所有元素，所以比较次数随着数组大小线性增加。
- **快速选择法**: 最好情况下的时间复杂度接近O(n)，最坏情况下为O(n^2)，但平均来说性能优于线性查找。由于每次分割都接近平均，实际运行中可能会更快。

为了验证这两个算法的效率，你可以测量它们在不同数据集（如不同长度的数组或更大范围的随机数）上的运行时间和比较次数，并对比结果。通过多次实验，你会看到快速选择法通常会有更少的平均比较次数，特别是在处理大数组时。