scala - 你如何编写一个惯用的 Scala Quicksort 函数？

Question

我最近回答了 question尝试在 Scala 中编写快速排序函数时，我看到了类似下面写在某处的代码的内容。

def qsort(l: List[Int]): List[Int] = {
  l match {
    case Nil         => Nil
    case pivot::tail => qsort(tail.filter(_ < pivot)) ::: pivot :: qsort(tail.filter(_ >= pivot))
  }
}

我的回答收到了一些 build 性的批评，指出 List 是快速排序集合的糟糕选择，其次以上不是尾递归。

我试图以尾递归的方式重写上述内容，但运气不佳。是否可以编写尾递归快速排序？或者，如果没有，如何以功能风格完成？还可以做些什么来最大限度地提高实现效率？

Answer 1

几年前，我花了一些时间尽可能地优化功能性快速排序。以下是我想出的 Vanilla List[A] :

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)
}

我可以通过自定义 List 做得更好结构体。这种自定义结构基本上跟踪了列表的理想(或接近理想)轴心点。因此，只需访问这个特殊的列表属性，我就可以在恒定时间内获得更好的枢轴点。在实践中，这比选择头部的标准功能方法要好得多。

事实上，上面的内容仍然很活泼。它是“半”尾递归(你不能在不变得非常丑陋的情况下进行尾递归快速排序)。更重要的是，它首先从尾端重建，因此与传统方法相比，中间列表要少得多。

重要的是要注意，这不是在 Scala 中进行快速排序的最优雅或最惯用的方法，它恰好工作得很好。编写归并排序可能会更成功，当用函数式语言实现时，它通常是一个更快的算法(更不用说更干净了)。