scala - Scala：如何在指定的索引范围内对数组进行排序？

Question

我在代码中已经有一个比较函数“compr”来比较两个值。

我想要这样的东西：

Sorting.stableSort(arr[i,j] , compr)

其中 arr[i,j] 是数组中元素的范围。

Answer 1

将切片作为视图，排序并复制回来（或将切片作为工作缓冲区）。

scala> val vs = Array(3,2,8,5,4,9,1,10,6,7)
vs: Array[Int] = Array(3, 2, 8, 5, 4, 9, 1, 10, 6, 7)

scala> vs.view(2,5).toSeq.sorted.copyToArray(vs,2)

scala> vs
res31: Array[Int] = Array(3, 2, 4, 5, 8, 9, 1, 10, 6, 7)

在 REPL 之外，.toSeq不需要额外的：

vs.view(2,5).sorted.copyToArray(vs,2)

Answer 2

在不重新实现排序的情况下，这应该尽可能好。仅创建一个具有要排序的切片大小的额外数组。

def stableSort[K:reflect.ClassTag](xs:Array[K], from:Int, to:Int, comp:(K,K) => Boolean) : Unit = {
  val tmp = xs.slice(from,to)
  scala.util.Sorting.stableSort(tmp, comp)
  tmp.copyToArray(xs, from)
}

Answer 3

将数组拆分为三部分，对中间部分进行排序然后将它们连接起来，不是最有效的方法，但这是关心性能的FP =)

val sorted = 
  for {
    first       <- l.take(FROM)
    sortingPart <- l.slice(FROM, UNTIL)
    lastPart    <- l.takeRight(UNTIL)
  } yield (first ++ Sorter.sort(sortingPart) ++ lastPart)

Answer 4

像这样的东西：

def stableSort[T](x: Seq[T], i: Int, j: Int, comp: (T,T) => Boolean ):Seq[T] = {
    x.take(i) ++ x.slice(i,j).sortWith(comp) ++ x.drop(i+j-1)
}                                         

def comp: (Int,Int) => Boolean = { case (x1,x2) => x1 < x2 } 
val x = Array(1,9,5,6,3)                           
stableSort(x,1,4, comp)
// > res0: Seq[Int] = ArrayBuffer(1, 5, 6, 9, 3)

如果你的类实现了 Ordering ，它会不那么麻烦。