algorithm – 如何定义在Scala中采用Ordered [T]数组的方法？

发布时间：2020-12-16 18:24:45 所属栏目：安全来源：网络整理

导读：我正在 Scala中构建一些基本算法(遵循Cormen的书),以便在主题上刷新我的想法,并且我正在构建插入排序算法.像这样做,它正常工作： class InsertionSort extends Sort {def sort ( items : Array[Int] ) : Unit = { if ( items.length 2 ) { throw new Illegal

我正在 Scala中构建一些基本算法(遵循Cormen的书),以便在主题上刷新我的想法,并且我正在构建插入排序算法.像这样做,它正常工作：

class InsertionSort extends Sort {

def sort ( items : Array[Int] ) : Unit = {

    if ( items.length < 2 ) {
        throw new IllegalArgumentException( "Array must be bigger than 1" )
    }

    1.until( items.length ).foreach( ( currentIndex ) => {

        val key = items(currentIndex)

        var loopIndex = currentIndex - 1

        while ( loopIndex > -1 && items(loopIndex) > key ) {

            items.update( loopIndex + 1,items(loopIndex) )

            loopIndex -= 1
        }

        items.update( loopIndex + 1,key )

    } )

}

}

但这仅适用于Int,我想使用泛型和Ordered [A],所以我可以对任何有序的类型进行排序.当我将签名更改为如下：

def sort( items : Array[Ordered[_]] ) : Unit

以下规范不编译：

"sort correctly with merge sort" in {

  val items = Array[RichInt](5,2,4,6,1,3)

  insertionSort.sort( items )

  items.toList === Array[RichInt]( 1,3,5,6 ).toList

}

并且编译器错误是：

Type mismatch,expected: Array[Ordered[_]],actual Array[RichInt]

但是RichInt是不是有序[RichInt]？我应该如何以接受任何Ordered对象的方式定义此方法签名？

编辑

如果有人感兴趣,最终来源可用here.

解决方法

实际上,RichInt不是Ordered [RichInt],而是Ordered [Int].但是scala.runtime.RichInt&lt ;:Ordered [_],但类Array在类型T中是不变的,因此Array [RichInt]不是数组[Ordered [_]].

scala> def f[T <% Ordered[T]](arr: Array[T]) = { arr(0) < arr(1) }
f: [T](arr: Array[T])(implicit evidence$1: T => Ordered[T])Boolean

scala> f(Array(1,3))
res2: Boolean = true

scala>

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!