Scala - 在快速排序中刪除while循環

def QuickSort(arr:Array[Int],first:Int,last:Int): List[Int] = { 
    var pivot:Int = 0 
    var temp:Int = 0 
    if (first < last) { 
     pivot = first 
     var i:Int = first 
     var j:Int = last; 
     while(i<j){ 
      while(arr(i) <= arr(pivot) && i < last) 
       i=i+1 
      while(arr(j) > arr(pivot)) 
       j=j+1 
      if(i<j) 
      { 
       temp = arr(i) 
       arr(i) = arr(j) 
       arr(j) = temp 
      } 
     } 
     temp = arr(pivot) 
     arr(pivot) = arr(j) 
     arr(j) = temp 
     QuickSort(arr, first, j-1) 
     QuickSort(arr, j+1, last) 
    } 
    arr.toList 
    }

您好我是新來的scala並試圖執行快速排序。程序工作正常，但我想刪除while循環，因爲我讀了，雖然並不建議在scala，因爲他們沒有返回任何值。Scala - 在快速排序中刪除while循環

有沒有什麼辦法在上面的代碼中刪除while循環。

來源

2016-01-28 Prabhat Kashyap

那麼你想從循環中返回一個值嗎？ –

的classic quicksort算法，因爲你在這裏編碼，需要一個可變集合（如Array）和元素值的交換，這就需要可變的變量（即var）。這些東西在函數式編程中不受歡迎，並且在Scala社區中不受重視。

下面是一個類似的方法，更符合FP道德的精神。

// pseudo-quicksort -- from Array[Int] to List[Int] 
def pqs(arr:Array[Int]): List[Int] = arr match { 
    case Array() => List() 
    case Array(x) => List(x) 
    case Array(x,y) => if (x < y) List(x,y) else List(y,x) 
    case _ => val (below, above) = arr.partition(_ < arr(0)) 
      pqs(below) ++ List(arr(0)) ++ pqs(above.tail) 
}

更好的方法是使用作爲標準庫提供的排序方法（sortBy，sortWith，sorted）之一。

來源

2016-01-28 07:13:49 jwvh

這裏有一個更簡單的實現：http://stackoverflow.com/a/20880933/5123895 –

好點。謝謝@Łukasz。 – jwvh

不那麼優雅，但沒有同時：

def QuickSort(l: List[Int]) : List[Int] = { 
    if(l.length == 0) return Nil 
    if(l.length == 1) return arr 
    val pivot = arr(arr.length/2) 
    val lesserThanPivot = l.filter(_ < pivot) 
    val equalToPivot = l.filter(_ == pivot) 
    val biggerThanPivot = l.filter(_ > pivot) 

    QuickSort(lesserThanPivot) ++ equalToPivot.tail ++ List(pivot) ++ QuickSort(biggerThanPivot) 

    }

來源

2016-01-28 07:12:37 barczajozsef

你應該替換那些'返回'白'別的'。 –

Scala - 在快速排序中刪除while循環

回答

相關問題