c - C : how does this work?中的合并算法

This question is unlikely to help any future visitors; it is only relevant to a small geographic area, a specific moment in time, or an extraordinarily narrow situation that is not generally applicable to the worldwide audience of the internet. For help making this question more broadly applicable, visit the help center。

已关闭10年。

此C代码段是合并算法实现的一部分:

out[i++] = (in1[i1] < in2[i2]) ? in1[i1++] : in2[i2++];

有人可以解释一下它是如何工作的吗？

最佳答案

编码

该代码使用所谓的后递增运算符和三元/条件运算符(有关更多详细信息，请参见附录)。

更详细的版本可能看起来像这样:

if (in1[i1] < in2[i2]) {
    out[i] = in1[i1];
    i++;
    i1++;
} else {
    out[i] = in2[i2];
    i++;
    i2++;
}

算法

如果in1和in2中的元素按排序顺序排列，则该片段将作为合并算法的主要部分，以将两个排序后的输入缓冲区合并为一个排序后的输出缓冲区。

在比较i1和i2之前，必须注意确保in1和in2分别是in1[i1]和in2[i2]的入站。然后in1[i1]是in1中的下一个可用最小元素，同样in2[i2]是in2中的下一个可用最小元素。

在不失一般性的前提下，我们假设使用in1[i1] < in2[i2](另一种情况是近乎镜像的情况)。然后in1中的下一个最小元素小于in2中的下一个最小元素，并在赋值的右侧添加in1[i1++]，我们从in1中获取下一个最小值，并将其指针前进到下一个可用值(如果有) 。在分配的左侧使用out[i++]，我们将获取的值分配给输出缓冲区中的一个插槽，并将其指针前进到下一个可用的插槽(如果有)。

使用类似于Queue的抽象数据结构而不是具有相应指针索引的数组(为清楚起见)，总体合并算法的更高级别的伪代码可能类似于以下内容:

procedure MERGE(Queue in1, in2) : Queue
// given sorted queues in1, in2, return a merged sorted queue

   INIT out IS Empty-Queue

   WHILE in1.notEmpty() AND in2.notEmpty()
      IF in1.peek() < in2.peek()
         out.enqueue(in1.dequeue())
      ELSE
         out.enqueue(in2.dequeue())

   // at this point, at least one of the queue is empty

   // dump in1 to out in case it's not empty
   WHILE in1.notEmpty()
      out.enqueue(in1.dequeue())

   // dump in2 to out in case it's not empty
   WHILE in2.notEmpty()
      out.enqueue(in2.dequeue())

   RETURN out

也可以看看

Wikipedia/Merge algorithm

Wikipedia/Mergesort

Wikipedia/Queue

附录A:三元/条件运算符

本质上，这样的表达式:

condition ? trueExpr : falseExpr

首先评估condition，如果它是true，它将评估trueExpr，其值成为整个表达式的值。相反，如果condition是false，则运算符将求值falseExpr，其值成为整个表达式的值。

相关问题

How does the ternary operator work?

To ternary or not to ternary?

Which coding style you use for ternary operator?

附录B:后增量运算符

诸如i++之类的表达式使用了所谓的后递增运算符。运算符将i递增，但是此表达式的值是递增之前i的值。相反，预增量表达式的值(例如++i)是增量后的i的值。

还有递减(例如--i)和递减(例如i--)。

相关问题

Difference between i++ and ++i in a loop?

Incrementing in C++ - When to use x++ or ++x?

像i = i++;这样的陷阱(大多数都是Java，但也适用于其他语言):

post increment operator java

Question about post-increment operator

关于c - C : how does this work?中的合并算法，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/3275602/