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

Question

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

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
}

Answer 1

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

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

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