Scala插入排序insert函数调用逻辑咨询：基于示例代码解析

嘿，我来一步步拆解这个Scala插入排序里insert函数的执行过程，咱们就从你提到的List(4,1,3)的排序流程入手——先纠正个小笔误：你写的insert(2,Nil)应该是insert(3,Nil)哦，咱们从正确的递归调用链开始讲。

首先先把给定的代码贴出来，方便对照：

def isort(xs: List[Int]) : List[Int] = if(xs.isEmpty) Nil else insert(xs.head, isort(xs.tail))
def insert(x: Int, xs: List[Int]) : List[Int] = if(xs.isEmpty || x <= xs.head) x:: xs else xs.head :: insert(x, xs.tail)

Scala的这个插入排序是递归从最底层开始执行的，所以咱们得从最内层的调用往外层推：

第一步：最内层的insert(3, Nil) #

当执行isort(List(3))时，因为List(3)不是空的，所以调用insert(3, isort(Nil))。而isort(Nil)直接返回Nil，所以实际执行的是insert(3, Nil)。

看insert函数的逻辑：

• 条件xs.isEmpty || x <= xs.head中，xs.isEmpty是true，所以直接触发x :: xs，也就是3 :: Nil，得到结果List(3)。这就是isort(List(3))的返回值。

第二步：insert(1, List(3)) #

接下来执行isort(List(1,3))，它会调用insert(1, isort(List(3)))，而我们已经知道isort(List(3))返回List(3)，所以现在是insert(1, List(3))。

看insert的条件：

• xs.isEmpty是false，但1 <= 3是true，所以直接返回1 :: List(3)，得到结果List(1,3)。这就是isort(List(1,3))的返回值。

第三步：最外层的insert(4, List(1,3)) #

现在到了最开始的isort(List(4,1,3))，它调用insert(4, isort(List(1,3)))，也就是insert(4, List(1,3))。

这里的条件判断：

• xs.isEmpty是false，且4 <= 1是false，所以执行xs.head :: insert(x, xs.tail)——也就是1 :: insert(4, List(3))。

现在进入insert(4, List(3))的调用：

• xs.isEmpty是false，4 <= 3也是false，所以继续执行3 :: insert(4, Nil)。

最后执行insert(4, Nil)：

• xs.isEmpty是true，返回4 :: Nil，也就是List(4)。

现在把这些递归的结果往回拼接：

1. 3 :: List(4) → List(3,4)
2. 1 :: List(3,4) → List(1,3,4)

这就是List(4,1,3)排序后的最终结果。

总结insert函数的核心逻辑 #

insert的作用是把单个元素x插入到已经排好序的列表xs的正确位置：

• 如果xs是空的，直接把x作为新列表的第一个元素
• 如果x比xs的第一个元素小或相等，直接插在xs的最前面
• 否则，先保留xs的第一个元素，递归地把x插入到xs剩下的尾部，直到找到合适的位置

内容的提问来源于stack exchange，提问作者Abhi