以有序的方式合并scala中的两个序列

Question

我试图合并两个序列,使它们保持排序.以下是我编写的代码:

  val seq1 = Seq(1,3,5,7,9)
  val seq2 = Seq(2,4,6,8)
  var arr = Seq[Int]()
  for(b <- seq2)
  {
    for(a <- seq1)
    {
      if(a < b)
        arr = arr :+ a
      else
      {
        arr = arr :+ b;break; 
      }
    }
  }
  println(arr)

我需要的输出需要:

Seq(1,2,3,4,5,6,7,8,9)    

但似乎break在Sc​​ala中不起作用.我对这门语言比较陌生.执行此操作的最佳方法是什么？

Answer 1

最简单的方法可能就是:

(seq1 ++ seq2).sorted

如果seq1并seq2包含其他类型,则必须提供Ordering该类型; 或者,使用该sortBy方法,将每个元素映射到Ordering可以隐式找到的另一种类型的元素:

(seq1 ++ seq2).sortBy(_.toDate)

Answer 2

以下也适用于非交错序列:

def mergeSorted[E: Ordering](x: Seq[E], y: Seq[E]): Seq[E] = {
  val ordering = implicitly[Ordering[E]]
  @tailrec
  def rec(x: Seq[E], y: Seq[E], acc: Seq[E]): Seq[E] = {
    (x, y) match {
      case (Nil, Nil) => acc
      case (_, Nil)   => acc ++ x
      case (Nil, _)   => acc ++ y
      case (xh :: xt, yh :: yt) =>
        if (ordering.lteq(xh, yh))
          rec(xt, y, acc :+ xh)
        else
          rec(x, yt, acc :+ yh)
    }
  }
  rec(x, y, Seq())
}

请注意,出于性能原因,您可能会使用Builders(vs.:+,+ :, reverse).

Answer 3

我很高兴找到@CaringDev的解决方案并将其改编为使用Builder：

def mergeSortedBuilder[E: Ordering](x: Seq[E], y: Seq[E])(implicit ordering: Ordering[E]): Seq[E] = {
  @tailrec
  def rec(x: Seq[E], y: Seq[E], acc: Builder[E, Seq[E]]): Builder[E, Seq[E]] = {
  (x, y) match {
    case (Nil, Nil) => acc
    case (_, Nil)   => acc ++= x
    case (Nil, _)   => acc ++= y
    case (xh :: xt, yh :: yt) =>
      if (ordering.lteq(xh, yh))
        rec(xt, y, acc += xh)
      else
        rec(x, yt, acc += yh)
  }
}
rec(x, y, Seq.newBuilder).result
}