scala中的插入排序实现 [英] Insertion sort implementation in scala

问题描述

我正在试用 Scala，我想看看如何在满足以下要求的 Scala 中实现插入排序:

I'm trying out Scala and I want to see how one would implement insertion sort in scala with the following requirements:

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

如果这不是实现插入排序的 Scala 方式，您是否仍然可以提供上述代码并解释该方法有什么问题.这是使用 while 循环的尝试(确实有效)，不，这不是作业问题，为什么会有敌意?

If this isn't the Scala way of implementing insertion sort can you still provide code for the above and explain what is wrong with the approach. edit: This is an attempt using a while loop (doest work) and no it isn't a homework question, why the hostility?

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 语法:

The implementation given in the wikipedia article fits your bill. Here it is, copied, pasted, and converted to Scala syntax:

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中的插入排序实现的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！