scala - 函数式 Scala 中的选择排序

Question

我正在学习“Scala 编程”，并编写了选择排序算法的快速实现。然而，由于我对函数式编程还不太了解，所以在转换为更 Scala 风格时遇到了困难。对于 Scala 程序员来说，如何使用 Lists 和 val 来做到这一点，而不是回到我的命令式方式？

http://gist.github.com/225870

Answer 1

如starblue already said ，您需要一个函数来计算列表的最小值并返回删除该元素的列表。这是我类似的尾递归实现(因为我相信 foldl 在标准库中是尾递归)，并且我试图使其尽可能实用:)。它返回一个列表，其中包含原始列表的所有元素(但有点相反 - 请参阅下面的解释)，并以最小值作为头。

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