第十章 Scala 容器基础(二十八):集合排序

原创
2016/04/19 16:25
阅读数 4K

Problem

    你想要对一个集合元素进行排序。或者你想定义一个自定义类来实现Ordered trait,来让你可以使用sorted方法,或者使用比较操符<,<=,>,>=来对类的实例进行比较。

Solution

    你可以使用sorted或者sortWith方法来对集合进行排序。

    Sorted方法可以对集合元素类型为Double,Float,Int和其他可以隐试转化scala.math.Ordering的进行排序。

scala> val l = List(10, 5, 8, 1, 7).sorted
l: List[Int] = List(1, 5, 7, 8, 10)

scala> val b = List("banana", "pear", "apple", "orange").sorted
b: List[String] = List(apple, banana, orange, pear)

    Rich版本的numeric类(比如RichInt)和StringOps类都实现了Ordered trait,所以他们可以使用sorted方法实现排序。

    SortWith方法让你可以使用自己的排序逻辑来实现排序规则。下面的例子展示了如何对集合元素类型为Int和String使用sortWith排序:

scala> List(10, 5, 8, 1, 7).sortWith(_ < _)
res14: List[Int] = List(1, 5, 7, 8, 10)

scala> List(10, 5, 8, 1, 7).sortWith(_ > _)
res15: List[Int] = List(10, 8, 7, 5, 1)

scala> List("banana", "pear", "apple", "orange").sortWith(_ < _)
res16: List[String] = List(apple, banana, orange, pear)

scala>  List("banana", "pear", "apple", "orange").sortWith(_ > _)
res17: List[String] = List(pear, orange, banana, apple)

    你的排序方法的复杂度取决于你的排序需求。举个例子,你可以通过sort访问元素的方法,比如下面这个例子,按长度对一个字符串集合进行排序:

scala> List("banana", "pear", "apple", "orange").sortWith(_.length < _.length)
res18: List[String] = List(pear, apple, banana, orange)

scala> List("banana", "pear", "apple", "orange").sortWith(_.length > _.length)
res19: List[String] = List(banana, orange, apple, pear)

    如果你的排序方法非常复杂或者会被重复使用,那么你可以先定义这个方法后,再调用此方法:

scala> def sortByLength(s1: String, s2: String) = {
     |   println("compare %s and %s".format(s1, s2))
     |   s1.length > s2.length
     | }
sortByLength: (s1: String, s2: String)Boolean

scala> List("banana", "pear", "apple").sortWith(sortByLength)
compare pear and banana
compare banana and pear
compare apple and pear
compare apple and pear
compare apple and banana
compare banana and apple
res20: List[String] = List(banana, apple, pear)

Discussion

    如果你定义的类,没有定义对Ordering的隐式转换,那么你就没有办法通过调用sorted方法来对集合元素进行排序。

scala> class Person(var name: String) {
     |   override def toString = name
     | }
defined class Person

    创建一个Person集合:

scala> val ty = new Person("Tyler")
ty: Person = Tyler

scala> val al = new Person("Al")
al: Person = Al

scala> val paul = new Person("Paul")
paul: Person = Paul

scala> val dudes = List(ty, al, paul)
dudes: List[Person] = List(Tyler, Al, Paul)

    如果你调用sorted方法对dudes进行排序,那么你会看到下面的错误提示:

scala> dudes.sorted
<console>:13: error: No implicit Ordering defined for Person.
              dudes.sorted
                    ^

    但是你可以使用sortWith对dudes进行排序:

scala> dudes.sortWith(_.name < _.name)
res1: List[Person] = List(Al, Paul, Tyler)

scala> dudes.sortWith(_.name > _.name)
res2: List[Person] = List(Tyler, Paul, Al)
Mix in the Ordered trait

    混入Ordered特质能够让你的程序使用sorted方法来对Person集合进行排序,但是你必须实现compare方法。

class Person(var name: String) extends Ordered[Person]{
  override def toString = name

  override def compare(that: Person): Int = {
    if (this.name == that.name) return 0
    else if (this.name > that.name) return 1
    else return -1
  }
}

    这个新的Person类就可以使用sorted方法来进行排序了。

    Compare方法提供了排序功能,compare方法会这样进行工作:

  • 如果两个对象相等,返回0

  • 如果this<that那么返回一个负数

  • 如果shit>that那么返回一个正数

    类的两个实例谁大谁小完全取决于你的compare算法,因为目前这个算法仅仅比较两个字符串的值,所以也可以写成这样:

def compare (that: Person) = this.name.compare(that.name)

    使用Ordered特质的另外一个好处是它可以让你在代码中直接比较对象实例。

if (al > ty) println("Al") else println("Tyler")

    上面代码之所以可以工作是因为Ordered特质实现了<=, <, >, >=方法,并调用你定义的compare方法来使之生效。

See Also

For more information, the Ordered and Ordering Scaladoc is excellent, with good examples of this approach, and other approaches.

• The Ordering trait

• The Ordered trait











展开阅读全文
打赏
1
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
1
分享
OSCHINA
登录后可查看更多优质内容
返回顶部
顶部