Scala

Question

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 循环，因为我读到 while 和 do while 在 scala 中不推荐，因为它们 return 没有任何价值。

有什么方法可以删除上面代码中的 while 循环。

Answer 1

不太优雅，但没有while:

  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)  

  }

Answer 2

正如您在此处编码的那样，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）。

Scala - 在快速排序中删除 while 循环

Scala - Remove while loop in quick sort

functional-programming

quicksort