c++ - 找到随机排列数组的平均比较次数

Question

我必须在 cpp 中编写一个函数，它运行 N 个大小为 M 的随机排列数组，并返回找到最小值和最大值的平均比较次数这些数组的元素。我想我应该使用这样的算法来找到每个数组的最小值和最大值:

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]

但是如何生成一定大小的随机置换数组呢？(我知道如何生成随机数组)

我还想问一下，查找“普通”随机数组的最小值和最大值的平均比较次数与排列随机数组情况下的 ovg 数之间有什么区别。 你想得到不同数量的比较吗？

Answer 1

寻找数组最小元素的算法可能如下所示:

int min = array[0];
for(int i = 1; i < size; i++)
{
    if(array[i] < min) //Note that this is a comparison no matter if min
    {                  //needs to be updated or not
        min = array[i];
    }
}

此代码使用 min存储我们看到的当前最小元素，将除第一个元素之外的每个元素与其进行比较，并更新 min如有必要。

请注意，每次迭代都会进行比较，它总是恰好是 size - 1次。

还不信？编写一个简短的函数来进行比较并增加一个全局计数器，在循环中使用它代替 <运算符(operator):

int counter = 0;
bool isless(int a, int b) { counter++; return a < b; }
int min = array[0];
for(int i = 1; i < size; i++)
{
    if(isless(array[i], min))
    {
        min = array[i];
    }
}