如何检查给定List [Int]是否在scala中排序？

Question

我想知道isSorted()scala中是否存在任何函数.

问题:检查是否List[Int]已排序,如果没有删除最小数字并再次List[Int]进行排序？

我只想要1或2行程序.

Answer 1

您可以在输入序列中比较包含多个项目的列表中的每一对:

def isSorted[T](s: Seq[T])(implicit ord: Ordering[T]): Boolean = s match {
    case Seq() => true
    case Seq(_) => true
    case _ => s.sliding(2).forall { case Seq(x, y) => ord.lteq(x, y) }
}

Answer 2

这不是最好的解决方案,但您可以使用sorted列表上的方法,然后将其与原始方法进行比较;

def sorted(l: List[Int]): Boolean = l == l.sorted

Answer 3

执行排序只是为了检查列表是否已经排序有点过分了。这里的最佳解决方案似乎是最明显的，它只是用人类语言描述问题并将其转换为代码：

def isSorted[T](list: List[T])(implicit ord: Ordering[T]): Boolean = list match {
    case Nil => true // an empty list is sorted
    case x :: Nil => true // a single-element list is sorted
    case x :: xs => ord.lteq(x, xs.head) && isSorted(xs) // if the first two elements are ordered and the rest are sorted, the full list is sorted too
}

如果你想要它更短，你可以用第二种情况来换取一点可读性：

def isSorted[T](list: List[T])(implicit ord: Ordering[T]): Boolean = list match {
    case Nil => true
    case x :: xs => xs.headOption.fold(true)(ord.lteq(x, _)) && isSorted(xs)
}

如果你想要一行字，那根本不可读：

def isSorted[T](list: List[T])(implicit ord: Ordering[T]): Boolean = list.headOption.fold(true)(a => list.tail.headOption.fold(true)(ord.lteq(a, _) && isSorted(list.tail.tail)))

Answer 4

有些懒惰:

def isSorted(l:List[Int]):Boolean = {
   val list = l.view
   !list.zip(list.tail).exists {case (x,y) => x>y}
}