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);
    println("排序前的结果");
    arrays.foreach(println) 
    arrays = sort(arrays);
    println("排序后的结果");
    arrays.foreach(println) 
  }
  
  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方法合并多个数组，返回排序后的结果就行了。<!--endfragment-->

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

<!--endfragment-->

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

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

评论

10 楼 fineqtbull 2009-10-18  

支持博主对Scala的看法。
欢迎到Scala圈子来看看

9 楼 smiletuna 2009-09-16  

vwpolo 写道

不过Scala在国内的应用好象没有活跃起来,

本来scala也没出来多久，怎么期待能很火爆呢。

erlang, python这些历史都不比java短， 但是流行程度和java比又是另外一回事了。

8 楼 vwpolo 2009-09-09  

不过Scala在国内的应用好象没有活跃起来,

7 楼 night_stalker 2009-09-08  

话说那个 qsort 写法应该是来自 haskell

qsort []     = []
qsort (x:xs) = qsort (filter (< x) xs) ++ [x] ++ qsort (filter (>= x) xs)

在 ruby 看起来就是这样

def sort a
  return a if a.size <= 1
  pivot = a[0]
  sort(a.select{|x| x < pivot}) +
       a.select{|x| x == pivot} +
  sort(a.select{|x| x > pivot})
end

6 楼 night_stalker 2009-09-08  

……

implicit def Array2ArrayEx [T <% Ordered[T]] (a: Array [T]) = new {
  def sort = {
    scala.util.Sorting quickSort a
    a
  }
}

println(Array("hello","123","no").sort.toString)
println(Array(123,343,5435,23,3213).sort.toString)

5 楼 leisure 2009-09-08  

scala确实不错

4 楼 fxsjy 2009-09-01  

netbeans的scala插件，应该是目前最好用的。

3 楼 wangxin0072000 2009-09-01  

请问有什么比较好的IDE或者什么编辑器吗？是在不习惯在notepad上写代码。

2 楼 advantech 2009-08-15  

我现在力挺Scala，更力挺Scala和Java的混合编程，各取其精华。

1 楼 icefishc 2009-08-13  

有个小错误

引用

这种方式和传统的快速排序方法在时间复杂度和空间复杂度相似

这么做的空间复杂度要比原先多得多.  嘿嘿

一般的QuickSort的递归实现已经很简单的了
如果一定要说说有什么麻烦的地方那就是它的partition部分 （实际上你简化的也就是那部分） 呵呵

但那个inplace的partition实在很精彩 扔掉不合适