scala 快速排序

QuickSort.scala

package flower.april.sort

import flower.april.util.ArrayUtils

/**
 * Date: 2010-7-26
 * Time: 12:34:40
 * Description: 
 */

object QuickSort {
  def sort[T <% Ordered[T]](arr: Array[T], start: Int = 0, end: Int) {

    def partition(from: Int = 0, to: Int): Int = {
      val x = arr(to)
      var i = from - 1
      for (j <- from until to) {
        if (arr(j) <= x) {
          i = i + 1
          ArrayUtils.swap(arr, i, j)
        }
      }
      ArrayUtils.swap(arr, i + 1, to)
      return i + 1
    }

    if (start < end) {
      val m = partition(start, end)
      sort(arr, start, m - 1)
      sort(arr, m + 1, end)
    }

  }

  def main(arg: Array[String]): Unit = {
    Console println "QuickSort"

    val arr = Array(87,2, 4, 5, 89, 6, 7, 8)

    sort(arr, end = arr.length - 1)

    arr.foreach(println)

  }

}

too much java style！ it‘s not scala style

def msort[T](less:%28T,T%29 => Boolean)(xs:List[T]):List[T] = {
def merge(xs:List[T],ys:List[T]):List[T] = (xs,ys) match{
case (Nil,) => ys
case (,Nil) => xs
case (x::xs1,y::ys1) =>
if (less(x,y))x::merge (xs1,ys)
else y::merge (xs,ys1)
}
val n = xs.length / 2
if (n==0) xs
else{
val (ys,zs) = xs splitAt n
merge(msort(less)(ys),msort(less)(zs))
}
}

your reply is merge sort. mine is quick sort. and too scala style make the algorithsm unefficient.

…

------------------ ԭʼʼ ------------------ : "h63542"; ʱ: 2011731() 4:49 ռ: "songpp22"; : Re: gist gist: 899322 def msort[T](less:%28T,T%29 => Boolean)(xs:List[T]):List[T] = { def merge(xs:List[T],ys:List[T]):List[T] = (xs,ys) match{ case (Nil,_) => ys case (_,Nil) => xs case (x::xs1,y::ys1) => if (less(x,y))x::merge (xs1,ys) else y::merge (xs,ys1) } val n = xs.length / 2 if (n==0) xs else{ val (ys,zs) = xs splitAt n merge(msort(less)(ys),msort(less)(zs)) } } ## Reply to this email directly or view it on GitHub: https://gist.github.com/899322

oh, typo . ineffective

…

------------------ ԭʼʼ ------------------ : "h63542"; ʱ: 2011731() 4:49 ռ: "songpp22"; : Re: gist gist: 899322 def msort[T](less:%28T,T%29 => Boolean)(xs:List[T]):List[T] = { def merge(xs:List[T],ys:List[T]):List[T] = (xs,ys) match{ case (Nil,_) => ys case (_,Nil) => xs case (x::xs1,y::ys1) => if (less(x,y))x::merge (xs1,ys) else y::merge (xs,ys1) } val n = xs.length / 2 if (n==0) xs else{ val (ys,zs) = xs splitAt n merge(msort(less)(ys),msort(less)(zs)) } } ## Reply to this email directly or view it on GitHub: https://gist.github.com/899322

def quicksort[T](less:%28T,T%29 => Boolean)(xs:List[T]):List[T] = {
list match {
case Nil => Nil
case x::xs =>
val (before,after) = xs partition(less(_ ,x))
qsort(before) ++ (x :: qsort(after))
}
}

def quicksort[T](less:%28T,T%29 => Boolean)(xs:List[T]):List[T] = {
xs match {
case Nil => Nil
case x::xs =>
val (before,after) = xs partition(less(_ ,x))
quicksort(less)(before) ++ (x :: quicksort(less)(after))
}
}

better than prev. but still inefficency. i think inplace sort is better. 2011/8/5 h63542 < [email protected]>

…

def quicksort[T](less:%28T,T%29 => Boolean)(xs:List[T]):List[T] = { xs match { case Nil => Nil case x::xs => val (before,after) = xs partition(less(_ ,x)) quicksort(less)(before) ++ (x :: quicksort(less)(after)) } } ## Reply to this email directly or view it on GitHub: https://gist.github.com/899322