如何在执行快速排序时正确地找到旋转元素？

Question

我有一个包含以下元素的数组：var arr = Array[Int](10,16,8,12,15,6,3,9,5)，我正在尝试使用快速排序技术对其进行排序。下面是我用来进行快速排序的代码：

object Quick {
def main(args: Array[String]): Unit = {
    var arr   = Array[Int](10,16,8,12,15,6,3,9,5)
    var low   = 0
    var high  = arr.length-1
    quickSort(low, high)
    arr.foreach(println)

    def quickSort(low:Int, high:Int):Unit = {
        if(low<high) {
            var j = partition(low, high)
            quickSort(low, j)
            quickSort(j+1, high)
        }
    }

    def partition(low:Int, high:Int): Int = {
        var pivot = arr(low)
        var i = low
        var j = high
        while(i<j) {
            do {
                i += 1
            } while(arr(i) <= pivot)
            do {
                j -= 1
            } while(arr(j) > pivot)
            if(i<j) swap(i, j)
        }
        swap(i, j)
        j
    }

    def swap(ai:Int, aj:Int): Unit = {
        var tmp = arr(ai)
        arr(ai) = arr(aj)
        arr(aj) = tmp
    }
}

}

当我运行代码时，它在行：while(arr(i) <= pivot)处中断，其中索引将变为9，我首先处理了这一行，而通过添加条件if(i < arr.length-1) i += 1，同样的情况也发生在第二行do中，而行：while(arr(j) > pivot)中的索引通过以ArrayOutOfBoundsException结尾而变成了-1。我通过添加一个条件来处理它：if(j>0) j-= 1如果我添加了这些条件，代码将进入无限循环，但我删除了它们，结果是索引为:9& -1的ArrayOutOfBoundsException分别表示低和高。

谁能让我知道我在这里做的错误是什么？

Answer 1

我不知道scala，但问题中的代码可能会超出(low，high)的界限。分区循环依赖于loops for elements == pivot来防止这种情况。注释中注明的修复：

        var pivot = arr(low)           // any but arr(high)
        var i = low-1                  // fix
        var j = high+1                 // fix
        while(i<j) {
            do {
                i += 1
            } while(arr(i) < pivot)    // fix (not <=) 
            do {
                j -= 1
            } while(arr(j) > pivot)
            if(i<j) swap(i, j)
        }
                                       // fix (no post loop swap)
        j
    }

您可能会考虑稍微更改一下(可以提高性能)。注意，退出while(true)的唯一方法是返回j。

        var pivot = arr(low)
        var i = low-1
        var j = high+1
        while(true) {
            do {
                i += 1
            } while(arr(i) < pivot)
            do {
                j -= 1
            } while(arr(j) > pivot)
            if(i >= j) return j
            swap(i, j)
        }
    }

Answer 2

我认为你在分区中的代码太复杂了。正确的示例：

def partition(low:Int, high:Int): Int = {
  val pivot = arr(high)
  var i = low - 1
  var j = low
  while (j <= high - 1) {
    if (arr(j) < pivot) {
      i += 1
      swap(i, j)
    }
    j += 1
  }
  swap(i + 1, high)
  i + 1
}

def quickSort(low:Int, high:Int):Unit = {
  if(low<high) {
    val j = partition(low, high)
    quickSort(low, j - 1)
    quickSort(j+1, high)
  }
}

rest代码相同。来自：geeksforgeeks