如何检测快速排序算法已经对所有元素进行了排序

Question

我知道这听起来很奇怪，但我正在开发一个应用程序，当快速排序完成时，我必须在其中执行一些操作，我需要找到开始索引或结束索引或数据透视之间的任何关系，或者任何能告诉我这将是排序数组所需的最后一个分区/交换的东西。。。

fun quickSort2(arr: ArrayList<Int>, start: Int, end: Int, from: String) {
if (start >= end) return
val p = partitions(arr, start, end , from)
quickSort2(arr, start, p - 1, "first")
quickSort2(arr, p + 1, end, "second")
}

分区功能：

fun partitions(arr: ArrayList<Int>, start: Int, end: Int , from: String): Int {
val pivotValue = arr[end]
var pivotIndex = start
for (i in start until end) {
if (arr[i] < pivotValue) {
swap(arr, i, pivotIndex)
pivotIndex++
}
}
swap(arr, pivotIndex, end)
return pivotIndex
}

交换功能：

fun swap(arr: ArrayList<Int>, i: Int, pivotIndex: Int) {
val temp = arr[i]
arr[i] = arr[pivotIndex]
arr[pivotIndex] = temp
}

有没有像if(start <= something && end <=someting)这样的关系可以告诉我是的，这将是最后一个交换或最后一个分区，或者这是数组排序的时候，或者我可以使用多次调用分区的大小来计算，任何可以告诉我，在这个阶段，数组是排序的，

Answer 1

您不需要检查任何内容：只需在整个数组上调用quickSort2一次即可。一旦这个调用返回，就可以确保整个数组已经排序。

这是因为quickSort2总是在较小的子数组上调用自己，并且会检查子数组是否为空(if (start >= end) return(。

为了确保情况确实如此，您可以在quickSort2的开头添加一些日志记录信息，显示输入参数。