c# - 使用锦标赛括号查找最小数字

Question

我正在编写一个程序，该程序必须在锦标赛分组中找到最小的数字。例如有一个数组

int[] a = new int[4] {4, 2, 1, 3}

通过比较相邻的数字，我必须选择最小的一个。 ( min(4, 2) -> 2 ， min(1, 3) -> 1 ，然后我比较 1 和 2，1 是最小的，所以它是赢家，但是不可能比较 2 和 1。只有 a[0] 和 1 ，a [2] 和 a[3] 等等。一般来说，a[2*i] 和 a[(2*i)+1] for(int i=0; i<a.Length/2; i++) <- 像这样

第一题:如果有n个数，整棵树由2n-1个括号组成。我应该创建一个包含 4 个或 7 个元素的数组吗？ 4 似乎是一个更好的选择。

第二个问题:如果我正在比较 4 和 2，而 2 更小，我应该让 a[0] = 2，然后在比较 1 和 3 时，a 1 = 1？最后将 a[0] 与 1 进行比较并将最小的数字放入 a[0]？可能需要临时 int。

最后一个问题:你建议用最简单的方式来做什么？我几乎找不到关于这个算法的任何信息。我希望你将我的思想引导到工作算法中。

不多，但我正在发布我的代码:

int[] a = new int[4] { 4, 2, 1, 3 };
int tmp = 0;
for (int i = 0; i < (a.Length)/2; i++)
{
    if (a[tmp] > a[tmp + 1])
    {
        a[i] = a[i + 1];
    }
    else if(a[tmp] < a[tmp +1])
    {
        a[i] = a[i + 1];
    }
    tmp = tmp + 2;
}

你能指出我做的还好吗，还有哪些地方需要改进？

Answer 1

如果锦标赛风格是必须的，递归方法似乎是最合适的:

int Minimum  (int [] values, int start, int end)
{
   if (start == end)
      return values [start];
   if (end - start == 1)
      if ( values [start] < values [end])
         return values [start];
      else
         return values [end];
   else
   {
      int middle = start + (end - start) / 2;
      int min1 = Minimum  (values, start, middle);
      int min2 = Minimum  (values, middle + 1, end);
      if (min1 < min2)
         return min1;
      else
         return min2;
   }
}

编辑:代码未经测试，可能会出现错误，因为它是在 Android 应用程序上输入的。

编辑:忘了说你是如何调用这个方法的。像这样:

int min = Minimum  (myArray, 0, myArray.Length -1);

编辑:或创建另一个重载:

int Minimum  (int [] values)
{
   return Minimum  (values, 0, values.Length -1);
}

调用只需:

int min = Minimum  (myArray);

编辑:这是非递归方法(请记住，此方法实际上修改了数组):

int Minimum(int[] values)
{
    int step = 1;
    do
    {
        for (int i = 0; i < values.Length - step; i += step)        
            if(values[i] > values[i + step])
                values[i] = values[i + step];
        step *= 2;
    }
    while(step < values.Length);

    return values[0];
}