Scala中的排序函数运行时间长

Sorting function in Scala runs for a long time

我正在尝试在 SCALA 中编写一个递归函数,它接受一个列表并对其进行排序。

不过,代码好像运行很久了。它甚至没有给我错误信息。

def sort(list:List[Int]):List[Int] = list match{

  case Nil => Nil
   case h::t => insert (h, sort(t))
def insert(num:Int, list:List[Int]): List[Int]=list match{
  case Nil => List()
   case head::tail=>
     if(head>=num)
        num::list
     else
       head::insert(num,tail)
   }
 sort(list)
}

您有 2 个问题:

1) 您直接从 sort 函数递归调用 sort - 删除 sort(list) 因为 insert 已经调用了它。这将使它终止。

2) 你 return 在其中一种情况下是一个空列表,而不是用 1 个元素构建列表 - 基本情况是错误的。

此版本有效:

    def sort(list: List[Int]): List[Int] = {
        def insert(num: Int, list: List[Int]): List[Int] = list match {
          case Nil => num :: Nil
          case head::tail =>
            if(head >= num)
              num::list
            else
              head::insert(num, tail)
        }
        list match {
          case Nil => Nil
          case h::t => insert(h, sort(t))
        }
    }