插入排序在我用 Scala 编写的代码中不起作用

Question

我正在编写一个函数来执行插入排序。在编写代码时，我再次获得与输出相同的列表。

def insertionSort(xs: List[Int]): List[Int] =
{
  if (xs.isEmpty) Nil
  else insert(xs.head, 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)
}

谁能告诉我我哪里出错了。

Answer 1

我猜你在你的函数中遗漏了一个小的递归调用。请参考下面的代码。

def insertionSort(xs: List[Int]): List[Int] =
{
  if (xs.isEmpty) Nil
  else insert(xs.head, insertionSort(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 编写的代码中不起作用

Insertion sort not working in my code written in Scala

scala

insertion-sort