Scala：说说快速排序

简短的几行代码就完成了快速排序：

def qsort: List[Int] => List[Int] = {
  case Nil => Nil
  case pivot :: tail =>
    val (smaller, rest) = tail.partition(_ < pivot)
    qsort(smaller) ::: pivot :: qsort(rest)
}

这几行代码很美，美不胜收。
我喜欢把这种风格里定义的sqort叫做对象，函数对象；
它的类型是List[Int] => List[Int]，这是个函数类型，接受一个List[Int]参数，返回一个List[Int] 结果；
模式匹配的第二个case pivot :: tail用来匹配至少有一个元素的List，如果匹配，pivot(轴)将被赋值为第一个元素；
val (smaller, rest) = tail.partition(_ < pivot)
这行代码很强大，partition为高阶函数，接受一个返回值为布尔值的函数。_ < pivot 为语法糖，是(i:Int)=>i<pivot匿名函数的简写；
这里的partition返回一个二元组(List[Int],List[Int]),smaller包含所有小于pivot的元素，rest包含tail中所有大于等于pivot的元素。
qsort(smaller) ::: pivot :: qsort(rest)，这行代码很直观，虽然执行顺序有点拗；
直观的地方在于书写的顺序，小的在前大的在后，然后用:::和::符号链接起来；
执行的时候是qsort(rest).::(pivot),就是把pivot放在qsort(rest)的结果(是个List)的首位；
用括号表示优先级：(qsort(smaller) ::: (pivot :: qsort(rest)))
完全写法：(qsort(rest).::(pivot)).:::(qsort(smaller)) 这里的::和:::都是方法，还是简写好，形象直观，也是最终结果的表现形式。

qsort(smaller) ::: pivot :: qsort(rest) 这行代码很不容易理解，怎么qsort还没有定义完就能调用了？这是我第一次接触递归的困惑。
假设qsort已经在别的地方定义完，在这里调用，则很容易理解；qsort在自己定义的地方调用自己，则显得很抽象，仿佛一口不见底的井。
我是这样理解，定义一个规则来把一个集合处理为prePart和nextPart两部分，然后把这个规则分别应用在这两部分上。