0 
object BubbleSort {
  def main(args : Array[String]) : Unit = {
    bubbleSort(Array(50,33,62,21,100)) foreach println
  }
  def bubbleSort(a:Array[Int]):Array[Int]={
    for(i<- 1 to a.length-1){
      for(j <- (i-1) to 0 by -1){
        if(a(j)>a(j+1)){
          val temp=a(j+1)
          a(j+1)=a(j)
          a(j)=temp
        }
      }
    }
    a
  }
}

我有上面的代码，据说是在 Scala 中实现冒泡排序。它主要对给定的数字进行排序，但它是一种实现良好的冒泡排序算法吗？另外这行代码在伪代码中的含义是什么：for(j <- (i-1) to 0 by -1){

我无法理解。

谢谢你的帮助

4

4 回答 4

3

弄清楚一段 Scala 代码的作用的最好方法是在 REPL 中运行它：

scala> 5 to 0 by -1
res0: scala.collection.immutable.Range = Range(5, 4, 3, 2, 1, 0)

因此，该代码从(i-1)0 倒数计数。

更一般地，x to y创建一个从 integerx到 integer的 Range y。该by部分修改此计数。例如，0 to 6 by 2表示“从 0 到 6 计数 2”，或Range(0, 2, 4, 6). 在我们的例子中，by -1表示我们应该倒数1。

至于了解冒泡排序的工作原理，您应该阅读 Wikipedia文章并使用它来帮助您了解代码在做什么。

于 2013-01-09T00:18:06.990 回答
2

您发布的示例基本上是在 Scala 中进行冒泡排序的命令式或 Java 方式，这还不错，但违背了 Scala 中函数式编程的目的。我们可以编写如下相同的代码排序器（基本上结合了 for 循环一行并在源长度上做一个范围）

 def imperativeBubbleSort[T <% Ordered[T]](source: Array[T]): Array[T] = {
    for (i <- 0 until source.length - 1; j <- 0 until source.length - 1 - i) {
      if (source(j) > source(j + 1)) {
         val temp = source(j)
         source(j) = source(j + 1)
         source(j + 1) = temp
      }
    }
    source
   }

Scala Flavor of bubble sort can be different and simple example is below
(basically usage of Pattern matching..)

    def bubbleSort[T <% Ordered[T]](inputList: List[T]): List[T] = {
      def sort(source: List[T], result: List[T]) = {
          if (source.isEmpty) result
          else bubble(source, Nil, result)
      }


    def bubble(source: List[T], tempList: List[T], result: List[T]): List[T] = source match {
          case h1 :: h2 :: t =>
              if (h1 > h2) bubble(h1 :: t, h2 :: tempList, result)
              else bubble(h2 :: t, h1 :: tempList, result)
          case h1 :: t => sort(tempList, h1 :: result)
    }
    sort(inputList, Nil)
   }
于 2013-12-27T19:10:48.753 回答
2

这可能是冒泡排序的最短功能实现

/**
 * Functional implementation of bubble sort
 * sort function swaps each element in the given list and create new list and iterate the same operation for length of the list times.
 * sort function takes three parameters
 * a) iteration list -> this is used to track the iteration. after each iteration element is dropped so that sort function exists the iteration list is empty
 * b) source list -> this is source list taken for element wise sorting
 * c) result -> stores the element as it get sorted and at end of each iteration, it will be the source for next sort iteration
 */

object Test extends App  {
  def bubblesort(source: List[Int]) : List[Int]  = {
    @tailrec
    def sort(iteration: List[Int], source: List[Int] , result: List[Int]) : List[Int]= source match {
      case h1 :: h2 :: rest => if(h1 > h2) sort(iteration, h1 :: rest, result :+ h2) else sort(iteration, h2 :: rest, result :+ h1) 
      case l:: Nil => sort(iteration, Nil, result :+ l)
      case Nil => if(iteration.isEmpty) return result else sort(iteration.dropRight(1), result, Nil )
    }
    sort(source,source,Nil)
  }
  println(bubblesort(List(4,3,2,224,15,17,9,4,225,1,7)))
 //List(1, 2, 3, 4, 4, 7, 9, 15, 17, 224, 225)
}
于 2019-05-15T23:24:53.000 回答
0 
  @tailrec
  def bubbleSort(payload: List[Int], newPayload: List[Int], result: List[Int]): List[Int] = {
    payload match {
      case Nil => result
      case s::Nil => bubbleSort(newPayload, List.empty, s::result)
      case x::xs => x.compareTo(xs.head) match {
        case 0 => bubbleSort(xs, x::newPayload, result)
        case 1 => bubbleSort(x::xs.tail, xs.head::newPayload, result)
        case -1 => bubbleSort(xs, x::newPayload, result)
      }
    }
  }
  val payload = List(7, 2, 5, 10, 4, 9, 12)
  bubbleSort(payload, List.empty, List.empty)
于 2020-07-04T11:46:10.773 回答