任何人都可以解释以下 Scala 代码吗？

Question

我必须在 Scala 中描述 BubbleSort，我用这段代码测试了它。但是我不太清楚每个函数的作用。

object BubbleSort {
  def sort(list: List[Int]): List[Int] = list match {
    case List() => List()
    case head :: tail => compute(head, sort(tail))
  }

  def compute(data: Int, dataSet: List[Int]): List[Int] = dataSet match {
    case List() => List(data)
    case head :: tail => if (data <= head) data :: dataSet else head :: compute(data, tail)
  }

  def main(args: Array[String]) {
    val list = List(3, 12, 43, 23, 7, 1, 2, 0)
    println(sort(list))
  }
}

谁能给我解释一下？

Answer 1

从最后一个元素开始查看您的函数如何工作

sort(List()) // List()
compute(0, List()) // List(0)
sort(List(0))      // List(0)
compute(2, List(0)) // List(0, 2)
sort(List(2, 0))    // List(0, 2)
compute(1, List(0, 2)) // List(0, 1, 2)
sort(List(1, 0, 2))    // List(0, 1, 2)
compute(7, List(0, 1, 2)) // List(0, 1, 2, 7)
sort(List(7, 0, 1, 2))    // List(0, 1, 2, 7)
compute(23, List(0, 1, 2, 7)) // List(0, 1, 2, 7, 23)
sort(List(23, 0, 1, 2, 7))    // List(0, 1, 2, 7, 23)
compute(43, List(0, 1, 2, 7, 23)) // List(0, 1, 2, 7, 23, 43)
sort(List(43, 0, 1, 2, 7, 23))    // List(0, 1, 2, 7, 23, 43)
compute(12, List(0, 1, 2, 7, 23, 43)) // List(0, 1, 2, 7, 12, 23, 43)
sort(List(12, 0, 1, 2, 7, 23, 43))    // List(0, 1, 2, 7, 12, 23, 43)
compute(3, List(0, 1, 2, 7, 12, 23, 43)) // List(0, 1, 2, 3, 7, 12, 23, 43)
sort(List(3, 0, 1, 2, 7, 12, 23, 43))    // List(0, 1, 2, 3, 7, 12, 23, 43)

compute 将元素 ("bubble") 推到适当的位置。

Answer 2

首先，冒泡排序的 classic definition 涉及在相邻元素乱序时交换它们。这里没有交换，所以它看起来不像真正的冒泡排序。

compute() 方法可能更恰当地称为 insert()，因为它就是这样做的。它将 data 元素插入到已排序的 dataSet 中。简单的情况是当 data 元素属于 dataSet 的头部（或仅属于其中的元素）。如果不是这种情况，那么它将当前 dataSet 的头部放在一边（在调用堆栈上）并递归直到 data can 被放在头部，然后展开调用堆栈，使用最新的 data 元素重建 dataSet。

sort()方法简单一些。它只是从当前 list 中取出头部并将其放置在调用堆栈中，直到 list 为空，然后进行排序。然后展开，将每个元素连同上次调用返回的排序结果一起传递给 compute()。

任何人都可以解释以下 Scala 代码吗？

Can anyone explain the following Scala code?

scala

intellij-idea

bubble-sort