Scala 快速排序

来源:转载

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

步骤为:

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

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

以上来自维基百科

快速排序针对数组的网上很多已经实现过了。

这个快速排序是针对List的,而scala的List是递归类型(链表类),在scala中实现递归类的快速排序超级简单如下:

def sort(ls: List[Int]): List[Int] = {

ls match {

case Nil => Nil

case base :: tail => {

val (left, rigth) = tail.partition(_ < base)

sort(left) ::: base :: sort(rigth)

}

}

}

sort(List(4,3,5,2,20,1))

 

就6行代码全都写完了,而且逻辑超清晰,我自己都不敢相信有如此漂亮的代码

我们来一行一行看:

ls match {

对ls进行模式匹配,

 case Nil => Nil

如果列表为空就返回

case base :: tail => {

如果列表可以拆分为头和尾,则就匹配成功(以头尾基准)。

 val (left, rigth) = tail.partition(_ < base)

将尾以按照小于 base 的拆为左,大于base的拆为右。

sort(left) ::: base :: sort(rigth)

递归左边 +中间  +递归右边。

就这几行代码就完成了List类的快速排序。

这种递归风格的语法实在是太漂亮了。


分享给朋友:
您可能感兴趣的文章:
随机阅读: