如何写一段符合scala语言习惯的快速排序

在stackoverflow上看到的一个例子

def qsort[A : Ordering](ls: List[A]) = {
    import Ordered._

    def sort(ls: List[A])(parent: List[A]): List[A] = {
        if (ls.size <= 1) ls ::: parent else {
            val pivot = ls.head

            val (less, equal, greater) = ls.foldLeft((List[A](), List[A](), List[A]())) {
                case ((less, equal, greater), e) => {
                if (e < pivot)
                  (e :: less, equal, greater)
                else if (e == pivot)
                  (less, e :: equal, greater)
                else
                  (less, equal, e :: greater)
                }
            }
            sort(less)(equal ::: sort(greater)(parent))
        }
    }
    sort(ls)(Nil)
}

吐槽一下,如果不考虑效率,我下面的实现,比他的要优美的多;-)

object  Con { 
    def unapply (l:List[Int]) = {
        val p=l(l.size/2); 
        Some((l.filter(_<p),p,l.filter(_>p)))
    } 
}

def qsort(xs:List[Int]):List[Int] = xs match {
    case Nil => xs
    case Con(left, pivot, right) => (qsort(left) :+ pivot) ::: qsort(right)
}

在repl下的测试

如何写一段符合scala语言习惯的快速排序》上有13条评论

  1. Danny

    你好, 一个很好的例子, 但 List (sameElement, sameElement) 转换为 List(sameElement)

    Some((l.filter(_p))) 错误的
    应该是 Some((l.filter(_p)))

    回复
  2. danny

    Some((l.filter(_p))) 这行 应该改成 Some((l.filter(_p))) 这样折半查找才能对相同的元素同样进行处理

    例如 List(3, 3) 这个排序的代码只能返回 List(3). 我也是用scala-check发现这个问题的。

    回复
  3. danny

    写的代码不知道为什么被过滤掉了 如果你用List(3,3) 里面有相同的元素 就发现问题了~

    回复
    1. hongjiang 文章作者

      确实有这个问题,谢谢指正,你是怎么通过 scala-check 发现的?我也去试了一下scala-check,但没有给出提示。我是这样:scalac -cp ./scalacheck_2.11.0-RC1-1.11.3.jar QuickSort.scala 编译时并未给出任何提示。能否告诉我一下你用的scala-check的版本和方式

      回复
  4. danny

    scala check 是一个自动生成数据的测试框架。
    这是测试代码:
    property(“binary search should order list”) = forAll { (anyList : List[Int]) =>
    QuickSortSpec.sort(anyList) == anyList.sorted
    }

    给实现写在QuickSortSpec.sort里就能看出来了

    回复
  5. Cando

    选第一个元素做pivot
    def q(xs: List[Int]): List[Int] = xs match{
    case Nil => xs
    case x::xs => {
    val left = xs filter (_=x)
    q(left):::List(x):::q(right)
    }
    }

    回复
  6. Cando

    为什么right不见了
    def q(xs: List[Int]): List[Int] = xs match{
    case Nil => xs
    case x::xs => {
    val left = xs filter (_=x)
    q(left):::List(x):::q(right)
    }
    }

    回复
  7. JangWee

    博主的这个写的更漂亮,赞!学习了~
    不过这样改一下是不是更好~ 解决相同元素出现的问题~:-)

    object Con {
    def unapply(l: List[Int]) = {
    val p = l(l.size/2)
    Some((l.filter(_p)))
    }
    }

    def qsort(xs:List[Int]):List[Int] = xs match {
    case Nil => xs
    case Con(left,pivot,right) => qsort(left) ::: pivot ::: qsort(right)
    }

    回复
  8. hongjiang 文章作者

    谢谢指出。可能是 wordpress的评论会自动过滤一些html标签,代码里的某些字符被当成html标签过滤掉了。代码上的建议用 gist 好了:https://gist.github.com/

    回复

发表评论

电子邮件地址不会被公开。 必填项已用*标注