C++实现随机排列数组最值查找平均比较次数计算及排列生成

嘿，我来帮你搞定这个问题！咱们一步步来，先解决你卡壳的随机排列生成问题，再把整个流程串起来实现需求。

一、生成随机排列数组：Fisher-Yates洗牌算法 #

生成大小为M的随机排列，最靠谱且无偏的方法是Fisher-Yates洗牌算法，它能在O(M)时间内生成均匀随机的排列。核心逻辑是：先创建有序数组，再从后往前依次将当前元素与随机选中的未交换元素互换，确保每个排列出现的概率均等。

结合C++标准库的高质量随机数生成器（比老式rand()更可靠），代码实现如下：

#include <vector>
#include <random>
#include <algorithm>

// 生成大小为M的随机排列数组（元素为1~M，可按需修改）
std::vector<int> generateRandomPermutation(int M) {
    // 初始化有序数组
    std::vector<int> arr(M);
    for (int i = 0; i < M; ++i) {
        arr[i] = i + 1;
    }

    // 配置随机数生成器
    static std::random_device rd;
    static std::mt19937 gen(rd());

    // Fisher-Yates洗牌核心逻辑
    for (int i = M - 1; i > 0; --i) {
        // 生成0到i之间的随机索引
        std::uniform_int_distribution<int> dist(0, i);
        int random_idx = dist(gen);
        // 交换当前元素与随机选中的元素
        std::swap(arr[i], arr[random_idx]);
    }

    return arr;
}

二、实现MaxMin算法并统计比较次数 #

严格按照你给出的伪代码实现，同时准确统计每一次比较操作：

MaxMin(A)
Max=Min=A[1]
for i <-1 to Length(A)
if A[i] < Min
Min <-A[i]
else if A[i] > Max
Max <-A[i]

注意：C++数组下标从0开始，需调整循环范围；每次条件判断都算一次比较（包括else if的判断），代码里会准确计数：

// 计算单个数组的MaxMin比较次数
int calculateComparisonCount(const std::vector<int>& arr) {
    if (arr.empty()) return 0;

    int max_val = arr[0];
    int min_val = arr[0];
    int comparison_count = 0;

    // 从第二个元素开始遍历（对应伪代码的i=2，因为第一个元素已初始化max/min）
    for (size_t i = 1; i < arr.size(); ++i) {
        comparison_count++; // 第一次比较：A[i] < Min
        if (arr[i] < min_val) {
            min_val = arr[i];
        } else {
            comparison_count++; // 第二次比较：A[i] > Max
            if (arr[i] > max_val) {
                max_val = arr[i];
            }
        }
    }

    return comparison_count;
}

三、整合计算平均比较次数 #

将两个函数结合，生成N个随机排列，统计总比较次数后计算平均值：

// 计算N个大小为M的随机排列的平均比较次数
double calculateAverageComparisons(int N, int M) {
    if (N <= 0 || M <= 0) return 0.0;

    long long total_comparisons = 0;
    for (int i = 0; i < N; ++i) {
        std::vector<int> permutation = generateRandomPermutation(M);
        total_comparisons += calculateComparisonCount(permutation);
    }

    return static_cast<double>(total_comparisons) / N;
}

四、测试示例 #

你可以用以下代码验证功能：

#include <iostream>

int main() {
    int sample_count = 1000;  // 生成1000个随机数组
    int arr_size = 100;       // 每个数组大小为100
    double avg_count = calculateAverageComparisons(sample_count, arr_size);
    std::cout << "MaxMin算法的平均比较次数：" << avg_count << std::endl;
    return 0;
}

小提示 #

• 随机数种子：如果你的平台不支持std::random_device（返回固定值），可以改用std::mt19937 gen(time(nullptr));，但注意time(nullptr)精度为秒级，短时间内多次运行会生成相同种子。
• 元素范围：若需要非1~M的排列，只需修改generateRandomPermutation里的数组初始化逻辑（比如先创建目标集合的有序数组，再洗牌）。

内容的提问来源于stack exchange，提问作者NOA