Scala 算法:快速排序

这篇是 scala 实现各种算法的第一篇,快速排序
用 case match 语法非常简单

/**
* QuickSort
* 快速排序
*
* @author zhaihao
* @version 1.0 3/24/16 23:02
*/
object QuickSort {
def main(args: Array[String]) {
println(quickSort(List(3, 4, 2, 15, 23, 5, 4, 2, 1, 3, 5)))
}

def quickSort[T <% Ordered[T]](list: List[T]): List[T] = {
list match {
case Nil => Nil
case x :: xs =>
val (before, after) = xs.partition(_ < x)
quickSort(before) ++ (x :: quickSort(after))
}
}
}

快速排序使用分治法(Divide and conquer)策略来把一个序列(list)分为两个子序列(sub-lists)。
步骤为:

  1. 从数列中挑出一个元素,称为”基准”(pivot),
  2. 重新排序数列,所有元素比基准值小的摆放在基准前面,所有元素比基准值大的摆在基准的后面(相同的数可以到任一边)。在这个分区结束之后,该基准就处于数列的中间位置。这个称为分区(partition)操作。
  3. 递归地(recursive)把小于基准值元素的子数列和大于基准值元素的子数列排序。

递归的最底部情形,是数列的大小是零或一,也就是永远都已经被排序好了。虽然一直递归下去,但是这个算法总会结束,因为在每次的迭代(iteration)中,它至少会把一个元素摆到它最后的位置去。


- - - - - - - - End Thank For Your Reading - - - - - - - -