我正在尝试 Scala，我想看看如何在 scala 中实现插入排序，并满足以下要求：
如果这不是实现插入排序的 Scala 方式，您仍然可以提供上述代码并解释该方法有什么问题。编辑：这是使用 while 循环的尝试（确实有效），不，这不是家庭作业问题，为什么会有敌意？
def insert_sort(a:Array[Int]):Array[Int]={
for(i <- 0 until a.length)
{
var j=i+1
while(j>1&&a(j)<a(j-1)&&j<a.length)
{
var c=a(j)
a(j)=a(j-1)
a(j-1)=c
j-=1
}
}
return a
}
这就是我想出的，它似乎是功能性的、通用的、尾递归的（foldLeft是尾递归的）......：
def insertionSort[A](la: List[A])(implicit ord: Ordering[A]): List[A] = {
def insert(la: List[A], a: A) = {
val (h, t) = la.span(ord.lt(_, a))
h ::: (a :: t)
}
la.foldLeft(List[A]()) {(acc, a) => insert(acc, a)}
}
迄今为止我见过的最优雅的插入排序算法实现：
val rand = List(5,3,1,2)
def isort(xs: List[Int]): List[Int] =
if (xs.isEmpty) Nil
else insert(xs.head, isort(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)
isort(rand) // Produces List(1,2,3,5)
算法实现取自这本好书：https ://www.artima.com/shop/programming_in_scala_3ed
我的插入排序过程版本如下。它由两个函数组成，isort具有insert以下签名：
isort(xs: List[int]) : List[int]: 接受一个整数列表并输出一个整数列表。insert(x: Int, xs: List[int]) : List[int]接受一个排序的输入列表和一个整数x，并添加x到列表中的正确位置以保持列表排序的不变性。例子：insert(3, [1, 2]) = [1, 2, 3]首先让我们编写insert函数。
否则，有两种可能的情况。列表的头部大于或等于给定的输入整数，在这种情况下，我们只需将输入整数附加到列表的开头并返回它。另一种情况是输入整数大于输入列表的头部。在这种情况下，我们递归地将输入整数插入到列表的尾部。
def insert(x : Int, xs : List[Int]) : List[Int] = {
xs match{
case Nil => List(x)
case y :: xs1 =>
if(y >= x) x :: xs
else y :: insert(x, xs1)
}
}
第二个函数是isort，它接受一个输入列表并对其进行排序。算法如下：
Nil，则返回Nil。否则，递归排序列表的尾部，并将头部添加到（排序的）尾部的正确位置（使用insert过程）
def isort(xs : List[Int]) : List[Int] = {
xs match{
case Nil => Nil
case x :: xs1 => insert(x, isort(xs1))
}
}
我们可以对此进行测试，isort(List(1, 6, 4, -2, 5, 12))并得到正确的预期输出。
嵌套 for 循环可能不是 Scala 中的答案，无论是什么问题。它们在 for 循环代表“重复直到条件，每次迭代都改变它”的语言中是有意义的，这不是Scala 中的 for 循环或 for 理解（for 理解是一个 for 循环，它为每次迭代产生一些东西）。
在 Scala 中，for 循环和 for 推导是对集合元素的迭代（或者对于非集合 monad 来说更奇怪的事情），但是对于插入排序，您想要找到一个位置，要么将位置交换到该位置，要么插入元素在那个位置。不应该使用 for 循环或 for 理解来查找内容。
此外，Scala 中没有传递引用。而且，事实上，Array它甚至不是一个 Scala 集合，而是一个 Java 的东西，它具有 JVM 赋予它的独特特性，这些特性不能用类重现，所以它不能被替换。
这是插入排序的另一个通用版本：
def less[T <: Comparable[T]](i: T, j: T) = i.compareTo(j) < 0
def swap[T](xs: Array[T], i: Int, j: Int) { val tmp = xs(i); xs(i) = xs(j); xs(j) = tmp }
def insertSort[T <: Comparable[T]](xs: Array[T]) {
for { i <- 1 to xs.size
j <- List.range(1, i).reverse
if less(xs(j),xs(j - 1)) } swap(xs, j, j -1)
}
你需要它做什么？
如果您只想要一个排序的数组，我更喜欢：def sortArray(a: Array[Int]): Array[Int] = a.sortWith(_ < _).
在开始时不要忘记添加：
import scala.util.control.Breaks._
这是我的解决方案，使用列表作为输入
def insertionSortLoop(list :List[Int]) : List[Int] = {
val intArray: Array[Int] = list.toArray
for ( j <- 1 until intArray.length ) {
breakable {
for ( i <- (1 to j).reverse ) {
if (intArray(i-1) < intArray(i)) {
break
} else {
val temp = intArray(i)
intArray(i) = intArray(i-1)
intArray(i-1) = temp
}
}
}
}
intArray.toList
}
我在github有实现。
这是使用 foldLeft 编写的代码示例。
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
})
}
这个例子可以在这个github repo 中找到。
维基百科文章中给出的实现符合您的要求。在这里，复制、粘贴并转换为 Scala 语法：
def insertionSort(a: Array[Int]): Array[Int] = {
for (i <- 1 until a.length) {
// A[ i ] is added in the sorted sequence A[0, .. i-1]
// save A[i] to make a hole at index iHole
val item = a(i)
var iHole = i
// keep moving the hole to next smaller index until A[iHole - 1] is <= item
while (iHole > 0 && a(iHole - 1) > item) {
// move hole to next smaller index
a(iHole) = a(iHole - 1)
iHole = iHole - 1
}
// put item in the hole
a(iHole) = item
}
a
}
尽管在编写 Scala 时，我习惯于更喜欢函数式编程风格（通过组合器或递归）而不是命令式编程风格（通过变量和迭代），这一次，对于这个特定问题，老派的命令式嵌套循环导致更简单的代码读者。对于某些类型的问题（例如排序算法，它通常会改变作为输入传递的项目缓冲区，而不是产生新的排序集合），我不认为回退到命令式样式是错误的
这是我的解决方案：
package bitspoke.algo
import scala.math.Ordered
import scala.collection.mutable.Buffer
abstract class Sorter[T <% Ordered[T]] {
// algorithm provided by subclasses
def sort(buffer : Buffer[T]) : Unit
// check if the buffer is sorted
def sorted(buffer : Buffer[T]) = buffer.isEmpty || buffer.view.zip(buffer.tail).forall { t => t._2 > t._1 }
// swap elements in buffer
def swap(buffer : Buffer[T], i:Int, j:Int) {
val temp = buffer(i)
buffer(i) = buffer(j)
buffer(j) = temp
}
}
class InsertionSorter[T <% Ordered[T]] extends Sorter[T] {
def sort(buffer : Buffer[T]) : Unit = {
for {
i <- 1 until buffer.length
j <- i until 0 by -1
if (buffer(j) < buffer(j - 1))
}
swap(buffer, j, j - 1)
}
}
如您所见，java.lang.Comparable我更喜欢scala.math.OrderedScala View Bounds 而不是Upper Bounds，而不是使用。这肯定是有效的，这要归功于原始类型到丰富包装器的许多 Scala 隐式转换。
您可以编写一个客户端程序，如下所示：
import bitspoke.algo._
import scala.collection.mutable._
val sorter = new InsertionSorter[Int]
val buffer = ArrayBuffer(3, 0, 4, 2, 1)
sorter.sort(buffer)
assert(sorter.sorted(buffer))
伪代码：
Algorithm Insertion-Sort-Descending(A)
for j <- 2 to length[A]
key <- A[j] // element we wish to insert
i <- j - 1 // position to the left side
while i > 0 and A[i] < key // while has not found correct position <-- difference between Ascending and Descending
A[i + i] = A[i] // right shift element
i = i - 1 // decrement i
A[i + 1] = key // found position, place key
考虑到您想要一个不可变的插入排序实现，adijo和@RB_的答案大多是正确的。
但是，对于大于约 50.000 个条目的列表，这些实现会因 StackOverflow 错误而炸毁堆栈。这是因为那里使用的递归方法不是@tailrec。
一种可能的解决方案是使用CPS制作方法 tailrec，如下：
object Sort {
def apply[A: Ordering](list: List[A]): List[A] = {
@tailrec
// In order to make this code tailrec, we are using CPS (continuation passing style)
def insert(entry: A, list: List[A])(k: List[A] => List[A]): List[A] =
list match {
case Nil => k(List(entry))
case head :: _ if entry < head => k(entry :: list)
case head :: tail => insert(entry, tail)(r => k(head :: r))
}
@tailrec
def inner(sorted: List[A], rest: List[A]): List[A] =
rest match {
case Nil => sorted
case head :: tail => inner(insert(head, sorted)(identity), tail)
}
inner(Nil, list)
}
}
值得注意的是，不可变的实现总是比可变的慢。