Scala如何实现尾递归的数组排序检测高阶函数isSorted

问题原因排查 #

你编写的代码核心问题是漏掉了数组最后一对相邻元素的比较逻辑：你在递归中仅当b + 1 < as.size时才执行比较操作，当b走到数组倒数第二个索引时，b+1等于数组长度，会直接跳过比较返回true，导致最后两个元素没有经过comparison规则校验。比如输入isSorted[Int](Array(1,3,2), (x,y) => x <= y)，你的代码会错误返回true，原因就是3和2这对最后相邻元素没有被比较。

修正后的实现代码 #

import scala.annotation.tailrec

def isSorted[A](as: Array[A], comparison: (A, A) => Boolean): Boolean = {
  // 边界情况提前处理，避免递归中重复判断
  if (as.length <= 1) return true

  @tailrec
  def loop(currentIdx: Int): Boolean = {
    // 已经遍历完所有相邻对，全部符合规则
    if (currentIdx >= as.length - 1) true
    // 当前相邻对不符合规则，直接返回false
    else if (!comparison(as(currentIdx), as(currentIdx + 1))) false
    // 符合规则，继续判断下一对
    else loop(currentIdx + 1)
  }

  loop(0)
}

逻辑说明 #

1. 入口函数先处理边界场景：空数组、长度为1的数组天然符合任意排序规则，直接返回true
2. 尾递归函数从索引0开始，逐对比较相邻的as[currentIdx]和as[currentIdx+1]
3. 只要有一对不符合比较规则就直接返回false，全部遍历完成后返回true
4. 递归逻辑每一步只做增量判断，没有额外运算，符合尾递归要求，@tailrec注解可以正常编译通过

测试用例验证 #

运行你给出的三个测试用例，结果完全符合预期：

• 示例1：isSorted[Int](Array(1, 2, 3), (x, y) => x <= y) → 返回true
• 示例2：isSorted[Int](Array(2, 2, 2), (x, y) => x == y) → 返回true
• 示例3：isSorted[Int](Array(2, 2, 2), (x, y) => x < y) → 返回false

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