C中的合并算法:这是如何工作的？

Question

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

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

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

Answer 1

代码

代码使用所谓的后增量运算符和三元/条件运算符(有关详细信息,请参阅附录).

更冗长的版本可能看起来像这样:

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](另一种情况是近镜像情景).然后,下一个最小元素from 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

也可以看看

• 维基百科/合并算法
• 维基百科/归并
• 维基百科/队列

Appendex A:三元/条件运算符

基本上,这样的表达式:

condition ? trueExpr : falseExpr

首先评估condition,如果是true,则评估trueExpr其值是否为整个表达式的值.如果condition是false,则运算符改为计算falseExpr,其值变为整个表达式的值.

相关问题

• 三元运算符如何工作？
• 要三元还是不三元？
• 您使用哪种编码方式用于三元运算符？

附录B:增量后算子

表达式如i++使用所谓的后增量运算符.运算符递增i,但此表达式的值是递增i 之前的值.相反,预增量表达式(例如++i)的值是增量i 之后的值.

还有预减量(例如--i)和后减量(例如i--).

相关问题

• 循环中i ++和++ i之间的区别？
• C++中的增量 - 何时使用x ++或++ x？

关于陷阱i = i++;(大多数是Java,但也适用于其他语言):

• post increment operator java
• 关于增量后算子的问题

Answer 2

你已经有一个很好的答案解释语法,但到目前为止没有人告诉你代码实际上做了什么.

如果你有两个输入数组,in1和in2,并且每个输入数组都有一个索引,那么这行代码会找到两个当前项中最小的项并将它放入输出数组中.然后它将该输入数组的索引以及索引推进到输出数组中.

如果两个输入是排序数组,并且如果该行在循环中运行,则它在O(n)时间内执行两个输入的合并.执行合并排序时,将重复使用此操作.