Scala中的非递归快速排序

Question

我正试图在scala中使用quicksort的非递归版本，但每当我尝试实现它时，我都会卡住，最终使用尾递归。在Scala中有没有实现快速排序而不使用递归的简单方法？

感谢所有的帮助。谢谢!

编辑:已添加递归解决方案。在这个解决方案中，sortingHelper方法是尾递归的。

def quickSortRecursive(values: Array[Int]) {
  // Swap the elements so that they aren't impacting recursion performance.
  // This swap helps the pivot get the correct position.
  def swap(i: Int, j: Int) {
    val t = values(i);
    values(i) = values(j);
    values(j) = t
  }

  // A method that takes in lower and upper bounds then sorts them.
  def sortRange(lowerBound: Int, upperBound: Int): (Int, Int) = {
    // Establish the pivot for use in sorting the bounds
    val pivot = values((lowerBound + upperBound) / 2)
    var i = lowerBound
    var j = upperBound

    // Sort the bounds using the pivot
    while (i <= j) {
      while (values(i) < pivot) {
        i += 1
      }
      while (values(j) > pivot) {
        j -= 1
      }
      if (i <= j) {
        swap(i, j)
        i += 1
        j -= 1
      }
    }

    // After the swaps, return the segments as lower and upper bounds
    (i, j)
  }

  @tailrec
  def sortingHelper(segments: List[(Int, Int)]) {
    // Take in the tuples from sortRange and sort them using tail-recursion
    segments.head match {
      case (l, r) =>
        var newSegments = segments.tail

        sortRange(l, r) match {
          case (i, j) =>
            if (l < j) {
              newSegments = (l, j) :: newSegments
            }
            if (i < r) {
              newSegments = (i, r) :: newSegments
            }
        }
        if (newSegments.nonEmpty) {
          sortingHelper(newSegments)
        }
    }
  }

  sortingHelper(List((0, values.length - 1)))
}

Answer 1

虽然实现本身需要巨大的改进，我希望随着Scala的改进，这一点也会实现。我将假设其他一切都是完美的，只专注于从尾递归转换。

要将尾递归代码转换为基于循环的代码，只需捕获递归终止条件并将其作为循环终止条件即可。

def sortingHelper2(segments: List[(Int, Int)]): Unit = {
  var newSegments = segments
  while (newSegments.nonEmpty) {
    val (l, r) = newSegments.head
    newSegments = newSegments.tail
    sortRange(l, r) match {
      case (i, j) =>
        if (l < j) {
          newSegments = (l, j) :: newSegments
        }
        if (i < r) {
          newSegments = (i, r) :: newSegments
        }
    }
  }
}

为了更好地解释，让我们来看一个最简单的尾递归函数，

def sumUpToN(n: Int): Long = {
  @tailrec
  def _sumUpToN(acc: Long, m: Int): Long = {
    if (m > 0)
      _sumUpToN(acc + m, m - 1)
    else
      acc
  }

  _sumUpToN(0, n)
}

要将其转换为基于循环的条件，您只需将此终止/继续条件移动到while循环，

def sumUpToN(n: Int): Long = {
  var acc = 0
  var m = n

  while (m > 0) {
    acc = acc + m
    m = m - 1
  }

  acc
}