如何在Scala中实现插入排序

Question

我在Scala中给出了以下代码：

def insertsort (l: List[Int]): List[Int] = {
if (l == Nil) Nil
else insert (l.head, insertsort (l.tail))
}

现在如何实现insert()？

Answer 1

以下是如何进行插入排序：

def insertSort(l: List[Int]): List[Int] = {
l.foldLeft(List.empty[Int]) { (sorted, i) =>
val (less, greater) = sorted.partition(_ < i)
(less :+ i) ++ greater
}
}

如果你不熟悉foldLeft，下面是它的工作原理。当我们说l.foldLeft时，这意味着我们要为l的每个成员做一些事情，即我们想要排序的列表。我们传入一个空列表作为第一个参数，它代表我们已经排序的列表部分(它从空开始，因为我们还没有做任何事情)。对于foldLeft的每次迭代，我们将按排序顺序再添加一个列表元素，并以这种方式构建我们的解决方案。

第二个参数是一个有两个参数的函数。第一个是累积排序列表，第二个是我们试图添加到排序列表中的来自l的当前整数。我们将已排序的列表拆分为两个列表，一个小于当前int，另一个大于/等于。然后我们在中间插入我们的int。此函数的返回值将成为下一次迭代中的第一个参数(我们称之为"排序")。

让我们对l=List(3,1,2)进行排序

第一次通过：排序=无，i=3。小于和大于均为零。该函数返回Nil+3+Nil，即List(3)，它将为下一次传递进行排序。

第二遍：排序=列表(3)，i=1。less=无，更大=列表(3)。函数返回Nil+1+List(3)，即List(1，3)。

第三遍：排序=列表(1，3)，i=2。less=列表(1)，更大=列表(3)。函数返回List(1)+2+List(3)=List(1,2,3)。

在我们对所有l进行迭代后，foldLeft返回最终的累积值(上次迭代的最后一行的值，在我们的例子中：List(1，2，3))。

希望能有所帮助！

Answer 2

看看这个。

/**
* Insertion sort algorithm(https://en.wikipedia.org/wiki/Insertion_sort)
* typically has nested loops with mutable state in imperative style of program
*
* Steps of an insertion sort:
* 3 7 4 9 5 2 6 1
* 3 7 4 9 5 2 6 1
* 3 7 4 9 5 2 6 1
* 3 4 7 9 5 2 6 1
* 3 4 7 9 5 2 6 1
* 3 4 5 7 9 2 6 1
* 2 3 4 5 7 9 6 1
* 2 3 4 5 6 7 9 1
* 1 2 3 4 5 6 7 9
*
* @param input
* @return
*/
def insertionSort(input: List[Int]): List[Int] = {
input.foldLeft(List[Int]())( (acc, element) => {
val (firstHalf, secondHalf) = acc.span(_ < element)
//inserting the element at the right place
firstHalf ::: element :: secondHalf
})
}

这是的源代码