Kotlin递归快排超时无响应问题排查

问题背景 #

你遇到的问题很典型：针对百万条电话簿数据的递归快速排序，在设置90秒超时时间时会出现程序冻结、不抛出异常的情况，但1秒超时却能正常运行。排查后发现，当递归深度较大且超时条件触发时，程序就会卡壳。先回顾下你的核心代码：

原递归快速排序实现 #

fun quickSort(data: List<PhEntry>, maxTime: Long = 0L): List<PhEntry> { 
    if (System.currentTimeMillis() > maxTime) throw Exception("") 
    if (data.size < 2) return data 
    val pivot = data[data.lastIndex / 2] 
    val equal = data.filter { it.name == pivot.name } 
    val greater = data.filter { it.name > pivot.name } 
    val lesser = data.filter { it.name < pivot.name } 
    return quickSort(lesser, maxTime) + equal + quickSort(greater, maxTime) 
}

计时调用函数 #

fun sortTimer(data: List<PhEntry>, time: Long = 0L, sortFunc: (sortedData: List<PhEntry>, time: Long) -> List<PhEntry>): Pair<List<PhEntry>?, Long> { 
    val startTime = System.currentTimeMillis() 
    return try{ 
        val result = sortFunc(data, startTime + time) 
        Pair(result, System.currentTimeMillis() - startTime) 
    } catch (e: Exception) { 
        Pair(null, System.currentTimeMillis() - startTime) 
    } 
}

问题根源分析 #

出现冻结的核心原因有两个：

1. 递归栈 unwind 开销过大：当递归深度达到几十层甚至上百层时，触发超时抛出异常后，异常需要沿着整个递归栈逐层向上传播、清理栈帧，这个过程在百万级数据场景下会非常耗时，看起来就像程序“卡住”了。
2. 内存与GC压力：原递归版本每次调用都会通过filter创建3个新列表，百万条数据会产生大量临时对象，导致GC频繁运行，进一步加剧超时后的卡顿。

解决方案 #

方案1：改用迭代版快速排序（推荐） #

迭代版用栈模拟递归调用，既避免了深递归栈的问题，又能在每一轮迭代开头就检查超时，一旦触发立刻终止，无需等待栈 unwind。同时采用原地排序，大幅减少内存开销。

迭代版实现

fun iterativeQuickSort(data: MutableList<PhEntry>, maxTime: Long = 0L): List<PhEntry> {
    if (data.size < 2) return data.toList()
    
    // 用栈存储待排序的区间[startIndex, endIndex]
    val sortStack = ArrayDeque<Pair<Int, Int>>()
    sortStack.push(0 to data.lastIndex)
    
    while (sortStack.isNotEmpty()) {
        // 每轮迭代先检查超时，触发则立即抛出异常
        if (System.currentTimeMillis() > maxTime) {
            throw Exception("Sorting timed out")
        }
        
        val (start, end) = sortStack.pop()
        if (start >= end) continue
        
        // 执行分区操作，返回pivot的最终位置
        val pivotPos = partition(data, start, end)
        
        // 将左右子区间压入栈，保证左区间优先处理（和递归逻辑一致）
        sortStack.push(pivotPos + 1 to end)
        sortStack.push(start to pivotPos - 1)
    }
    
    return data.toList()
}

// 原地分区函数，处理重复元素避免最坏情况
private fun partition(data: MutableList<PhEntry>, start: Int, end: Int): Int {
    // 沿用原逻辑选中间位置作为pivot
    val pivot = data[(start + end) / 2]
    // 将pivot交换到末尾，简化分区逻辑
    data.swap((start + end) / 2, end)
    
    var leftPtr = start
    for (rightPtr in start until end) {
        when {
            data[rightPtr].name < pivot.name -> data.swap(leftPtr++, rightPtr)
            data[rightPtr].name == pivot.name -> {
                // 随机交换相等元素，避免大量重复数据时的性能退化
                if ((leftPtr + rightPtr) % 2 == 0) data.swap(leftPtr++, rightPtr)
            }
        }
    }
    // 将pivot放到正确位置
    data.swap(leftPtr, end)
    return leftPtr
}

// 扩展函数：交换列表中两个位置的元素
private fun <T> MutableList<T>.swap(i: Int, j: Int) {
    val temp = this[i]
    this[i] = this[j]
    this[j] = temp
}

修改计时调用函数

适配迭代版的可变列表参数：

fun sortTimer(data: List<PhEntry>, time: Long = 0L, sortFunc: (sortedData: MutableList<PhEntry>, time: Long) -> List<PhEntry>): Pair<List<PhEntry>?, Long> {
    val startTime = System.currentTimeMillis()
    val mutableData = data.toMutableList()
    return try {
        val result = sortFunc(mutableData, startTime + time)
        Pair(result, System.currentTimeMillis() - startTime)
    } catch (e: Exception) {
        Pair(null, System.currentTimeMillis() - startTime)
    }
}

方案2：优化递归版（仅作临时过渡） #

如果必须保留递归逻辑，可以在递归调用前提前检查超时，减少栈 unwind的概率，但本质上还是无法解决深递归的问题：

fun quickSort(data: List<PhEntry>, maxTime: Long = 0L): List<PhEntry> {
    if (System.currentTimeMillis() > maxTime) throw Exception("Sorting timed out")
    if (data.size < 2) return data
    
    val pivot = data[data.lastIndex / 2]
    val equal = data.filter { it.name == pivot.name }
    val greater = data.filter { it.name > pivot.name }
    val lesser = data.filter { it.name < pivot.name }
    
    // 递归前先检查超时，避免进入递归后再触发
    if (System.currentTimeMillis() > maxTime) throw Exception("Sorting timed out")
    val sortedLesser = quickSort(lesser, maxTime)
    
    if (System.currentTimeMillis() > maxTime) throw Exception("Sorting timed out")
    val sortedGreater = quickSort(greater, maxTime)
    
    return sortedLesser + equal + sortedGreater
}

效果验证 #

迭代版的优势非常明显：

• 原地排序大幅降低内存开销，GC压力骤减
• 超时检查响应即时，触发后立刻抛出异常，不会出现冻结
• 针对重复元素的优化避免了最坏情况的性能退化，百万条数据的排序效率会显著提升

内容的提问来源于stack exchange，提问作者One Face