功能Scala中的选择排序

Question

我正在通过"Scala编程"编写并编写了一个快速实现选择排序算法.但是,由于我在函数式编程方面仍然有点绿色,因此我无法转换为更多Scala-ish风格.对于那里的Scala程序员,我怎样才能使用Lists和vals而不是回到我的命令式方式呢？

http://gist.github.com/225870

Answer 1

正如starblue已经说过的那样,你需要一个计算列表最小值的函数,并返回删除了该元素的列表.这是我的尾部递归实现类似的东西(因为我相信foldl在标准库中是尾递归),我试图尽可能地使它尽可能的功能:).它返回一个列表,其中包含原始列表的所有元素(但有些反转 - 参见下面的解释),最小值为head.

def minimum(xs: List[Int]): List[Int] =
  (List(xs.head) /: xs.tail) {
    (ys, x) =>
      if(x < ys.head) (x :: ys)
      else            (ys.head :: x :: ys.tail)
  }

这基本上是一个折叠,从包含第一个元素的列表开始.xs如果第一个元素xs小于该列表的头部,我们将它预先附加到列表中ys.否则,我们将其ys作为第二个元素添加到列表中.等等递归地,我们将列表折叠成一个新的列表,其中包含最小元素作为头部,列表包含所有元素xs(不一定是相同的顺序),其中最小元素被删除,作为尾部.请注意,此功能不会删除重复项.

创建此辅助函数后,现在可以轻松实现选择排序.

def selectionSort(xs: List[Int]): List[Int] =  
  if(xs.isEmpty) List()
  else {
    val ys = minimum(xs)
    if(ys.tail.isEmpty) 
      ys
    else
      ys.head :: selectionSort(ys.tail)
  }

不幸的是,这个实现不是尾递归的,所以它会炸掉大型列表的堆栈.无论如何,你不应该对大型列表使用O(n ^ 2)排序,但仍然......如果实现是尾递归的话会很好.我会试着想一些......我认为它看起来像是折叠的实现.

尾递归!

为了使它具有尾递归性,我在函数式编程中使用了一种非常常见的模式 - 累加器.它有点落后,因为现在我需要一个被调用的函数maximum,它基本上做同样的minimum,但是使用最大元素 - 它的实现是最小的,但使用>而不是<.

def selectionSort(xs: List[Int]) = {
  def selectionSortHelper(xs: List[Int], accumulator: List[Int]): List[Int] =
    if(xs.isEmpty) accumulator
    else {
          val ys = maximum(xs)
          selectionSortHelper(ys.tail, ys.head :: accumulator)
    }

  selectionSortHelper(xs, Nil) 
  }

编辑:更改了答案,将辅助函数作为选择排序函数的子函数.

它基本上将最大值累积到一个列表中,它最终作为基本案例返回.你也可以看到,它是尾递归通过更换accumulator通过throw new NullPointerException-然后检查堆栈跟踪.

这是使用累加器逐步排序.左侧显示列表xs,右侧显示列表accumulator.每一步都由星形表示最大值.

64* 25 12 22 11  ------- Nil
11 22 12 25*     ------- 64
22* 12 11        ------- 25 64
11 12*           ------- 22 25 64
11*              ------- 12 22 25 64
Nil              ------- 11 12 22 25 64

以下显示了逐步折叠以计算最大值:

maximum(25 12 64 22 11)

25 :: Nil         /: 12 64 22 11  -- 25 > 12, so it stays as head
25 :: 12          /: 64 22 11     -- same as above
64 :: 25 12       /: 22 11        -- 25 < 64, so the new head is 64
64 :: 22 25 12    /: 11           -- and stays so
64 :: 11 22 25 12 /: Nil          -- until the end

64 11 22 25 12