好好生活,努力工作,天天向上！
BlogJava 首页 新随笔 联系 聚合 管理
  46 Posts :: 1 Stories :: 178 Comments :: 0 Trackbacks
Scala 的快速排序

   真的是越来越喜欢Scala了，简洁的语法，清新的风格是我对Scala的印象，感觉使用Scala进行编程真的非常的方便，从Scala的设计思想也能得到不少的启发，就比如下面的一个对数字数组快速排序的sort(Array[Int])方法，你以前想到过通过这样的方式实现吗？

/**
 * 快速排序的例子2
 * @author VWPOLO
 * <p>2009-8-12</p>
 */
object TestQuickSort2 {
  def main(args : Array[String]) : Unit = {
    var arrays = Array(123,343,5435,23,3213);
    Console.println("排序前的结果");
    arrays.foreach((array: Int ) => println(array))
    arrays = sort(arrays);
    Console.println("排序后的结果");
    arrays.foreach((array: Int ) => println(array))
  }
  
  def sort(xs: Array[Int]):Array[Int] = {
    if(xs.length <= 1)
      xs;
    else {
      val pivot = xs(xs.length /2);
      Array.concat(
          sort(xs filter (pivot >)),
               xs filter (pivot ==),
          sort(xs filter (pivot <))
      )
    }
  }
}

    sort(Array[Int])方法通过简明的方式完成了传统的快速排序功能：

      1、判断参数数组是否为空？如果为空说明排序完成，直接方法参数。

      2、如果给定的参数数字不为空，取得数组的中间数。

      3、根据中间数对参数数组进行拆分，通过调用Array的filter(p: A => Boolean)方法对数组进行分区并生成一个新的数组，"xs filter (pivot >)" 生成一个新的数组只包含小于pivot的数字，"xs filter (pivot ==)"里面的数组只包含等于pivot的数组，"xs filter (pivot <)"则包含大于pivot的数字，通过sort方法的迭代，完成了排序过程。

      4、通过Array.concat方法合并多个数组，返回排序后的结果就行了。


    sort方法指定了返回值但是方法块中没有"return" 语言，其实加不加都无所谓，Scala编译器可以自动进行判断。

    这种方式和传统的快速排序方法在时间复杂度和空间复杂度相似，但是代码却大大的简化了，不信你用Java写一个对数字数组快速的排序方法(要自己写，使用Collections.sort(List<T>)方法可不算啊)。

    Scala引起了大家的大量关注，一些人拿Scala的缺点和Java的优点进行比较进行批评Scala，"另一些人拿Java缺点和Scala优点进行比较来拥护Scala，然后两队人在论坛上打起了口水仗，Scala又不是钞票，当然不能够取悦所有人。


    参考资料：Scala By Example
 

posted on 2009-08-13 09:02 VWPOLO 阅读(1586) 评论(6)  编辑  收藏 所属分类: Java 技术

Feedback

# re: Scala 的快速排序 2009-08-13 10:19 Johnny Jian
Console.println("排序前的结果");
arrays.foreach((array: Int ) => println(array))

=>

println("排序前的结果")
arrays.foreach(println)  回复  更多评论
  

# re: Scala 的快速排序 2009-08-13 10:23 VWPOLO
@Johnny Jian
不错，这样更简洁！  回复  更多评论
  

# re: Scala 的快速排序[未登录] 2009-08-13 11:20 dennis
这里并不是scala的优雅，而是递归的优雅。scala的语法谈不上优美，反而是晦涩。  回复  更多评论
  

# re: Scala 的快速排序 2009-08-14 00:40 Net4J
不还觉得Groovy的顺眼.  回复  更多评论
  

# re: Scala 的快速排序 2009-08-14 22:44 Johnny Jian
@Net4J
赞成
同样的程序用Groovy写：
def sort(xs) {
if (xs.size() <= 1)
xs
else {
def pivot = xs[xs.size() / 2 as int]
sort(xs.findAll { it < pivot }) +
xs.findAll { it == pivot } +
sort(xs.findAll { it > pivot })
}
}
def array = [123, 343, 5435, 23, 3213]
println array
array = sort(array)
println array

或者用groupBy方法：
def sort(xs) {
if (!xs)
[]
else {
def pivot = xs[xs.size() / 2 as int]
def m = xs.groupBy { it <=> pivot }
sort(m[-1]) + m[0] + sort(m[1])
}
}
def array = [123, 343, 5435, 23, 3213]
println array
array = sort(array)
println array  回复  更多评论
  

# re: Scala 的快速排序 2009-08-15 09:53 VWPOLO
@Johnny Jian
只能说萝卜白菜，各有所爱了  回复  更多评论
  


只有注册用户登录后才能发表评论。
网站导航: