前端之家

  1. 首页
  2. 问答

如何在执行快速排序时正确找到枢轴元素？

• 问答

我有一个包含以下元素的数组：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,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处理了该操作 在第二次操作中也发生了同样的情况，其中行while(arr(j) > pivot)的索引以-1结尾变成ArrayOutOfBoundsException。我通过添加条件来处理它：if(j>0) j-= 1 如果我添加了这些条件，但我删除了这些条件，代码将进入无限循环，这将导致ArrayOutOfBoundsException的索引分别为9和-1，分别为低和高。

任何人都可以让我知道我在这里犯的错误吗？

ludcy2009 回答：如何在执行快速排序时正确找到枢轴元素？

我不了解scala，但是问题中的代码可能超出了（低，高）的范围。分区循环依靠停止元素==枢轴来防止这种情况。注释中指出的修复程序：

        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)
        }
    }
,

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

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)
  }
}

其余代码相同。 算法来自：geeksforgeeks

algorithmarraysquicksortscalasorting
本文链接：https://www.f2er.com/3073248.html

大家都在问