在scala中插入排序实现

Question

我正在尝试Scala,我想看看如何在scala中实现插入排序,具有以下要求:

1. 嵌套for循环
2. Array [Int]用于输入
3. 如果可能的话,通过引用方式修改调用中函数内容的方法,否则返回一个数组[Int]

如果这不是实现插入排序的Scala方法,您仍然可以提供上述代码并解释该方法的错误.编辑:这是一个尝试使用while循环(doest工作),不,它不是一个功课问题,为什么敌意？

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
}

Answer 1

这就是我提出的,它似乎是功能性的,通用的,尾递归的(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)}
}

Answer 2

迄今为止我见过的最优雅的插入排序算法实现：

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

Answer 3

维基百科文章中给出的实现符合您的要求。这是复制、粘贴并转换为 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
}