使用 mergesort gets stackoverflow 对数组进行排序

Question

我在 Kotlin 中有数组 A = arrayOf(Pair(1,1),Pair(0,9),Pair(3,8),Pair(4,0),Pair(6,6),Pair(10,7),Pair(5,1),Pair(7,3))，我想根据对的 X 分量使用归并排序对它进行排序。

到目前为止我有这个

fun merge(U: Array<Pair<Int,Int>>, V: Array<Pair<Int,Int>>, A: Array<Pair<Int,Int>>) {
    var i: Int = 0
    var j: Int = 0
    var size = U.size + V.size

    for (k in 0 until size) {
        if ((i < U.size)&&(j < V.size)) {
            if (U[i].component1() < V[i].component1()) {
                A[k] = U[i]
                i = i + 1
            }
            else {
                A[k] = V[j]
                j = j + 1
            }
        }    
    }
}

fun mergeSort(A: Array<Pair<Int,Int>>) {
    var middle = A.size / 2
    var U = A.copyOfRange(0, middle)
    var V = A.copyOfRange(middle, A.size)
    mergeSort(U)
    mergeSort(V)
    merge(U, V, A)
}

但是，它给了我一个 Whosebug 错误。我不知道是什么原因造成的。有更好的方法吗？

编辑：@ggorlen 指出我遗漏了基本情况，经过检查，我在修改合并排序函数时不小心删除了基本情况。谢谢！

Answer 1

您的递归过程缺少基本情况，否则您的过程将陷入循环，无限期地调用自身并最终导致堆栈溢出。

在编写递归过程时，必须了解有两种情况必须明确定义。

1。 Recursive case : 当递归过程调用自身时(Recursion)

2。基本情况：当递归触底时（在您的情况下，当数组包含单个项目时会发生这种情况，在这种情况下它已经排序，无需递归）

基本情况对于递归过程非常重要属性，因为它负责阻止过程陷入无休止的递归。

使用 mergesort gets stackoverflow 对数组进行排序

Sort an array of pairs using mergesort gets stackoverflow

stack-overflow

arrays

sorting

mergesort

kotlin