1

下面是一个用 Scala 编写的选择排序的实现。

ss.sort(arr) 行导致此错误：类型不匹配；找到：需要数组 [字符串]：数组 [Ordered[Any]]

由于 Ordered 类型是由 StringOps 继承的，不应该推断出这种类型吗？如何将字符串数组添加到 sort() 方法？

这是完整的代码：

object SelectionSortTest {

  def main(args: Array[String]){

    val arr = Array("Hello","World")

    val ss = new SelectionSort()
    ss.sort(arr)
  }

}

class SelectionSort {

  def sort(a : Array[Ordered[Any]]) = {
    var N = a.length

    for (i <- 0 until N) {
        var min = i

        for(j <- i + 1 until N){
            if( less(a(j) , a(min))){
              min = j
            }
        exchange(a , i , min)
        }
    }

  }

  def less(v : Ordered[Any] , w : Ordered[Any]) = {
    v.compareTo(w) < 0
  }

  def exchange(a : Array[Ordered[Any]] , i : Integer , j : Integer) = {
    var swap : Ordered[Any] = a(i)
    a(i) = a(j)
    a(j) = swap
  }
}
4

3 回答 3

3

数组是不变的。即使是 的子类型，您也不能将其Array[A]用作。看看这里为什么：为什么数组是不变的，但列表是协变的？Array[B]AB

也不是Ordered，因此您的 less 实现也将不起作用。

您应该通过以下方式使您的实现通用：

object SelectionSortTest {

  def main(args: Array[String]){

    val arr = Array("Hello","World")

    val ss = new SelectionSort()
    ss.sort(arr)
  }

}

class SelectionSort {

  def sort[T <% Ordered[T]](a : Array[T]) = {
    var N = a.length

    for (i <- 0 until N) {
        var min = i

        for(j <- i + 1 until N){
            if(a(j) < a(min)){ // call less directly on Ordered[T]
              min = j
            }
        exchange(a , i , min)
        }
    }

  }

  def exchange[T](a : Array[T] , i : Integer , j : Integer) = {
    var swap = a(i)
    a(i) = a(j)
    a(j) = swap
  }
}

有点奇怪的说法T <% Ordered[T]意味着“任何T可以隐式转换为Ordered[T]”的类型。这确保您仍然可以使用小于运算符。

有关详细信息，请参阅： 什么是 Scala 上下文和视图边界？

于 2013-04-24T21:57:16.233 回答
1

@gzm0 的答案（带有一些非常好的链接）建议Ordered。我将补充一个答案覆盖Ordering，它提供了等效的功能，而不会对你的类施加太多影响。

Ordering让我们调整 sort 方法以接受定义了隐式实例的“T”类型数组。

def sort[T : Ordering](a: Array[T]) = {
  val ord = implicitly[Ordering[T]]
  import ord._ // now comparison operations such as '<' are available for 'T'
  // ...
  if (a(j) < a(min))
  // ...
}

[T : Ordering]andimplicitly[Ordering[T]]组合等价于 type 的隐式参数Ordering[T]：

def sort[T](a: Array[T])(implicit ord: Ordering[T]) = {
  import ord._
  // ...
}

为什么这很有用？case class Account(balance: Int)想象一下，某个第三方为您提供了一个。您现在可以Ordering像这样为它添加一个：

// somewhere in scope
implicit val accountOrdering = new Ordering[Account] {
  def compare(x: Account, y: Account) = x.balance - y.balance
}

// or, more simply
implicit val accountOrdering: Ordering[Account] = Ordering by (_.balance)

只要该实例在范围内，您就应该能够使用sort(accounts).
如果你想使用一些不同的排序，你也可以明确地提供它，像这样：sort(accounts)(otherOrdering).

请注意，这与提供隐式转换没有太大区别Ordering（至少不在这个问题的上下文中）。

于 2013-04-25T23:14:34.247 回答
0

尽管在编写 Scala 时，我习惯于更喜欢函数式编程风格（通过组合器或递归）而不是命令式编程风格（通过变量和迭代），这一次，对于这个特定问题，老式的命令式嵌套循环导致更简单和高效代码。

对于某些类型的问题，我不认为回到命令式风格是错误的，例如排序算法通常会转换输入缓冲区（更像是一个过程），而不是产生一个新的排序集合。

这是我的解决方案：

package bitspoke.algo

import scala.math.Ordered
import scala.collection.mutable.Buffer

abstract class Sorter[T <% Ordered[T]] {

  // algorithm provided by subclasses
  def sort(buffer : Buffer[T]) : Unit

  // check if the buffer is sorted
  def sorted(buffer : Buffer[T]) = buffer.isEmpty || buffer.view.zip(buffer.tail).forall { t => t._2 > t._1 }

  // swap elements in buffer
  def swap(buffer : Buffer[T], i:Int, j:Int) {
    val temp = buffer(i)
    buffer(i) = buffer(j)
    buffer(j) = temp
  }
}


class SelectionSorter[T <% Ordered[T]] extends Sorter[T] {
  def sort(buffer : Buffer[T]) : Unit = {
    for (i <- 0 until buffer.length) {
      var min = i
      for (j <- i until buffer.length) {
        if (buffer(j) < buffer(min))
          min = j
       }
       swap(buffer, i, min)
     }
  }
}

如您所见，为了实现参数多态，java.lang.Comparable我更喜欢使用scala.math.OrderedScala View Bounds 而不是 Upper Bounds。由于原始类型到 Rich Wrappers 的 Scala 隐式转换，这肯定是有效的。

您可以编写一个客户端程序，如下所示：

import bitspoke.algo._
import scala.collection.mutable._

val sorter = new SelectionSorter[Int]
val buffer = ArrayBuffer(3, 0, 4, 2, 1)
sorter.sort(buffer)

assert(sorter.sorted(buffer))
于 2014-04-27T21:52:57.320 回答