如何检测快速排序完成排序？判断最后Partition/Swap时机的技术方案

首先，咱们先拆解你的需求：你想在快速排序的最后一次partition/swap操作时，或者确认数组完全排序后，执行特定逻辑。结合你给出的Kotlin实现，我给你几个实用的方案：

方案1：最直接的方式——顶层递归结束后执行操作 #

你的quickSort2是递归实现的，当最顶层的调用（也就是quickSort2(arr, 0, arr.size-1, ...)）执行完毕时，整个数组100%已经有序了。这种方式不需要额外判断，直接在顶层调用后写你的逻辑就行，是性能最优的选择：

fun main() {
    val arr = arrayListOf(3,1,4,1,5,9,2,6)
    // 执行快速排序
    quickSort2(arr, 0, arr.size-1, "initial")
    // 这里就是数组完全排序后的时机，执行你的特定操作
    println("数组已排序完成，触发自定义逻辑")
}

方案2：捕捉最后一次Partition操作 #

如果你一定要在最后一次Partition执行时触发逻辑，可以通过跟踪「待处理的子数组数量」来实现。核心思路是：

• 用一个计数器记录当前还在递归处理中的子数组数量
• 每次进入需要Partition的子数组时增加计数，处理完后减少计数
• 当计数回到1时，当前的Partition就是最后一次

修改后的代码示例：

// 全局变量跟踪待处理的子数组数量（也可以封装成类成员变量避免全局污染）
var pendingPartitions = 0

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

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)
    
    // 判断是否是最后一次Partition
    if (pendingPartitions == 1) {
        println("这是最后一次Partition，触发自定义逻辑")
        // 在这里执行你的特定操作
    }
    
    return pivotIndex
}

// swap函数保持不变
fun swap(arr: ArrayList<Int>, i: Int, pivotIndex: Int) {
    val temp = arr[i]
    arr[i] = arr[pivotIndex]
    arr[pivotIndex] = temp
}

// 调用方式
fun main() {
    val arr = arrayListOf(3,1,4,1,5,9,2,6)
    pendingPartitions = 1 // 初始值为1，表示整个数组待处理
    quickSort2(arr, 0, arr.size-1, "initial")
}

方案3：捕捉最后一次Swap操作 #

如果需要精准捕捉最后一次Swap（包括Partition循环中的元素交换，以及结尾的基准值交换），有两种思路：

1. 计数器+事后验证：给swap函数加一个全局计数器，每次调用就递增。在排序结束后，这个计数器的最终值就是总Swap次数，你可以在Swap函数里判断当前计数是否等于总次数——但问题是总次数需要提前计算，而快速排序的Swap次数和数组初始状态强相关，无法提前预知。
2. Swap后检查数组是否有序：每次Swap后调用一个辅助函数检查数组是否完全有序，如果是，则触发逻辑。这种方式直观但性能较差（每次检查是O(n)复杂度），适合小数组或调试场景：

// 辅助函数：判断数组是否有序
fun isSorted(arr: ArrayList<Int>): Boolean {
    for (i in 0 until arr.size - 1) {
        if (arr[i] > arr[i+1]) return false
    }
    return true
}

// 修改swap函数
fun swap(arr: ArrayList<Int>, i: Int, pivotIndex: Int) {
    val temp = arr[i]
    arr[i] = arr[pivotIndex]
    arr[pivotIndex] = temp
    
    // 检查是否是最后一次Swap
    if (isSorted(arr)) {
        println("这是最后一次Swap，触发自定义逻辑")
        // 执行你的特定操作
    }
}

额外说明：关于通过数组大小计算Partition次数 #

你提到的「通过数组大小计算Partition调用次数」来判断排序完成的思路，其实不太靠谱。因为快速排序的Partition次数和基准值选择、数组初始状态有关：

• 最优情况下（每次基准值都选中间值），Partition次数是O(log n)
• 最坏情况下（每次基准值选到最值），Partition次数是O(n)

所以无法通过数组大小直接确定固定的Partition次数，还是用前面的方案更可靠。

内容的提问来源于stack exchange，提问作者Rahul Pawar