谁能解释一下下面的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 将元件（"气泡"）推到适当的位置。

Answer 2

首先 经典定义 如果相邻的元素不符合顺序，则需要进行交换。这里没有进行交换，所以它看起来并不像一个真正的气泡排序。

在这里，没有进行交换，所以看起来不像是真正的泡泡排序。compute() 方法，更正确的做法是调用 insert() 因为这就是它的作用。它插入了一个 data 元素中加入已排序的 dataSet. 琐碎的情况是，当 data 元素属于头部的 dataSet. 如果不是这样的话，那么它就会把当前的头放在 dataSet 搁置（在调用堆栈上）并循环使用，直到 data 可以 在头部放置，然后拆开调用栈，重建 dataSet 与最新 data 元素就位。

该 sort() 的方法更简单一些。它只是将当前的 list 并将其放在呼叫堆栈上，直到 list 是空的，因此，排序。然后它展开，将每个元素传递给 compute() 以及上一次调用返回的排序结果。