遞歸排序在斯卡拉尾部遞歸

我想在斯卡拉寫尾部遞歸算法。遞歸排序在斯卡拉尾部遞歸

public ArrayList sort(ArrayList<int> toSort) 
{ 
    ArrayList<int> list=toSort; 
     for(int i=0; i<list.size();i++) 
     { int min=100; 
      int pos=-1; 
      for(int j=i+1; j<list.size();j++) 
      { 
       if(list.get(i)>list.get(j) && list.get(j)<min) 
       { 
        min=list.get(j); 
        pos=j; 
       } 
      } 
      if(pos!=-1) 
      { 
       int a=list.get(i); 
       list.set(i,list.get(pos)); 
       list.set(pos,a); 
      } 
     } 
    return list; 
}

我是新的斯卡拉和函數式編程，所以我不知道如何編寫代碼。有人可以幫我一些想法嗎？

非常感謝你提前

來源

2014-01-14 Rodrigo Cifuentes Gómez

這裏是一個代碼「是」在Scala中，即使它是我所寫過的最糟糕的Scala代碼。我想保持1：1到你的代碼。但我希望它的目的是演示如何編寫尾遞歸。沒有更多，沒有更多。

def sort(toSort: util.ArrayList[Int]): util.ArrayList[Int] = { 
    val list = toSort 

    @tailrec 
    def outerLoop(i: Int) { 

    if (i < list.size) { 
     var min = 100 
     var pos = -1 

     @tailrec 
     def innerLoop(j: Int) { 
     if (j < list.size) { 
      if (list.get(i) > list.get(j) && list.get(j) < min) { 
      min = list.get(j) 
      pos = j 
      } 

      innerLoop(j + 1) 
     } 
     } 

     if (pos != -1) { 
     val a = list.get(i) 
     list.set(i, list.get(pos)) 
     list.set(pos, a) 
     } 

     outerLoop(i + 1) 
    } 
    } 

    outerRec(0) 
}

來源

2014-01-14 06:38:33

謝謝你的回答，你對我的編譯錯誤是正確的。你的答案很好，但實際上我正在尋找一個不可改變的解決方案。先生，再次謝謝你。 –

我這麼認爲。 Scala排序如下所示：val list = List（3，2，1）.sorted –

Scala immutable List被實現爲鏈接列表，它與java ArrayList是不同的數據結構，因此使用不同的排序算法。 –

這裏是不可變的tailrec解決方案。這並不複雜，我只是將您的代碼正確地轉換爲不可變的方法。

import annotation.tailrec 

val list = List(1,4,2,7,6,9,8) 

@tailrec 
final def inner(min: Int, pos: Int, item: Int, i: Int, list: List[(Int, Int)]): Map[Int, Int] = list match { 
    case (pItem, p) :: tail if(item > pItem && pItem < min) => inner(pItem, p, item, i, tail) 
    case (pItem, p) :: tail => inner(min, pos, item, i, tail) 
    case Nil if(pos != -1) => Map(i -> min, pos -> item) 
    case Nil => Map.empty[Int, Int] 
} 

@tailrec 
final def outer(list: List[(Int, Int)], acc: Map[Int, Int] = Map.empty[Int, Int]): Map[Int, Int] = list match { 
    case (item, i) :: tail => outer(tail, acC++ inner(100, -1, item, i, tail)) 
    case Nil => acc 
} 

def tailSort(list: List[Int]) = { 
    val zipped = list.zipWithIndex 
    outer(zipped, zipped.map(_.swap).toMap).toList.sortBy(_._1).map(_._2) 
} 

tailSort(list) 

res41: List[Int] = List(1, 2, 4, 6, 7, 8, 9)

來源

2014-01-14 09:08:28

遞歸排序在斯卡拉尾部遞歸

回答

相關問題