我想了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
}
在中给出的实施维基百科的文章适合您的法案。 这是，复制，粘贴，并转换为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
}
这是我想出了，这似乎是功能性的，通用的，尾递归（ 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)}
}
我插入排序程序的版本如下。 它由两个功能， 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))我们得到了正确的预期输出。
最优雅的插入排序算法的实现至今是I'we看出：
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
嵌套for循环也有可能不是在斯卡拉的答案，无论是问题。 它们使语言在那里for循环代表意义上的“重复，直到条件，改变这个每次迭代”，这是不是 for循环或内涵是在斯卡拉（一个用于理解是一个for循环，其产生的东西每次迭代）。
在Scala中，for循环和内涵是一个集合中的元素（或离奇的东西收不上来的单子）迭代，但插入排序要查找的位置，要么换地方到那个位置，或插入的元素在该位置。 寻找的东西不应该做的循环或内涵。
此外，还有在斯卡拉没有传递通过引用。 而且，事实上， Array甚至不是一个斯卡拉集合，但其具有由不可再生带班的JVM赋予它独特的特性的Java啄，所以它不能被替换。
这里是插入排序的另一个通用版本：
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回购。
虽然，编码斯卡拉的时候，我已经习惯了喜欢函数式编程风格（通过组合子或递归）在命令行式风格（通过变量和迭代），这个时候，对于这个特定的问题，老同学势在必行嵌套循环导致了简单的代码读者。 我不认为回落到势在必行的风格是对某些类别的问题（如排序通常发生变异作为输入传递项目的缓冲区，而不是产生一个新的分类收集算法）错误
这是我的解决方案：
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.Ordered和Scala查看边界，而不是上界。 这当然得益于原始类型，以丰富的封装器的许多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))
Github上链接Scala实现
伪代码：
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
