5

所以，我有四个整数，我需要找出这四个中最小的两个。在 C（或任何其他语言）中这样做最有效的方法是什么？

编辑：为了提高效率，我需要一个固定的实现，因为这是一个非常关键的操作，将被执行数千次。

4

7 回答 7

5

这是使用排序网络的有效实现：

inline void Sort2(int *p0, int *p1)
{
    if (*p0 > *p1)
    {
        const int temp = *p0;
        *p0 = *p1;
        *p1 = temp;
    }
}

inline void Sort4(int *p0, int *p1, int *p2, int *p3)
{
    Sort2(p0, p1);
    Sort2(p2, p3);
    Sort2(p0, p2);  
    Sort2(p1, p3);  
    Sort2(p1, p2);  
}

这只需要 5 次比较和最多 5 次交换。您可以忽略 p2、p3 的结果。

请注意，对于性能关键型应用程序Sort2，可以在某些架构上通过一两条指令实现无分支。

于 2012-08-31T11:54:47.010 回答
3

只需编写一个循环并跟踪低 2 值吗？应该是最大 O(2N)，这是我认为可以实现的最佳复杂性。

于 2012-08-31T11:51:58.617 回答
3

最有效的方法？为了避免任何额外的步骤，我得到了这个（在伪代码中）。这将避免您与其他更通用的解决方案（特别是那些不利用比较操作的传递性质的解决方案）进行的任何不必要的比较。

请记住，这只是考虑效率，而不是针对漂亮的代码。

if a<=b:
  if b<=c:
    # c too big, which of b and d is smaller?
    if b<=d:
      return (a,b)
    else:
      return (a,d)
  else if b<=d:
    # a and c both < b, and b < d
    return (a,c)
  else:
    # b is > a, c and d. Down to just those three.
    if a<=c:
      if c<=d:
        # a < c < d
        return (a,c)
      else:
        # a and d both < c
        return (a,d)
    else if d<=a:
      # Both c and d < a
      return (c,d)
    else:
      # c < a < d
      return (a,c)
else:
  # b < a
  if a<=c:
    # c too big, which of a and d is smaller?
    if a<=d:
      return (a,b)
    else:
      return (b,d)
  else if a<=d:
    # b and c both < a, and a < d
    return (b,c)
  else:
    # a is > b, c and d. Down to just those three.
    if b<=c:
      if c<=d:
        # b < c < d
        return (b,c)
      else:
        # b and d both < c
        return (b,d)
    else if d<=b:
      # Both c and d < b
      return (c,d)
    else:
      # c < b < d
      return (b,c)

我认为这有 5 次比较的最坏情况和 3 次比较的最佳情况（显然没有办法在少于 3 次比较中做到这一点）。

于 2012-08-31T12:04:50.667 回答
3

您可以进行 4 次比较和最多 4 次交换。

inline void swap(int* i, int* j) {
  static int buffer;
  buffer = *j;
  *j = *i;
  *i = buffer;
}

inline void sort2(int* a, int* s) {
  if (*s < a[1])
    swap(s,a+1);
  if (*s < a[0]) // it is NOT sufficient to say "else if" here
    swap(s,a);
}

inline void sort4(int* a) {
  sort2(a,a+2);
  sort2(a,a+3);
}

结果将是第一个到单元格，但请注意，这些单元格不一定是排序的！它们只是最小的元素。

于 2012-08-31T12:08:09.723 回答
2

我会用它们制作一个数组，排序并取前两个值。

于 2012-08-31T11:51:09.863 回答
2

您最多可以通过 4 次比较来完成它：

  • 比较第一对数字，让小bea1和大bea2
  • 比较第二对数字，让较小的bea3和较大的bea4
  • 如果 a1 >= a4 返回 (a3, a4)
  • （现在我们知道 a1 < a4）
  • 如果 a3 >= a2 返回 (a1, a2)
  • （现在我们也知道 a3 < a2）
  • 返回 (a1, a3)

要确定这是真的，您可以检查所有可能返回的组合：

(a1, a2) (a1, a3) (a1, a4)

(a2, a3) (a2, a4)

(a3, a4)

于 2012-08-31T13:32:01.880 回答
0

我认为您可以对数组进行排序并选择前两个元素。

于 2012-08-31T11:51:17.867 回答