拆分集合后如何在合并排序中应用合并逻辑？

Question

我正在尝试使用合并排序技术对数组进行排序，下面是我为此编写的代码：

object MergeSort {
    def main(args: Array[String]): Unit = {
        val arr = Array[Int](2,4,1,6,8,5,3,7)
        val b = mergeSort(arr)
        b.foreach(println)
    }

    def mergeSort(arr:Array[Int]):Array[Int] = {
        if(arr.length<2) arr
        else {
            val mid   = (arr.length)/2
            val (left,right)  = arr.splitAt(mid)
            println("Left: " + left.mkString(", "))
            println("right: "+ right.mkString(", "))
            mergeSort(left)
            mergeSort(right)
            merge(left, right, arr)
        }
    }

    def merge(left: Array[Int], right: Array[Int], arr: Array[Int]):Array[Int] = {
        var brr = new Array[Int](arr.length)
        val nl  = left.length
        val nr  = right.length
        var (i:Int,j:Int,k:Int) = (0,0,0)
        while(i < nl && j < nr) {
            if(left(i) < right(j)) {
                brr(k) = left(i)
                i += 1
            }
            else {
                brr(k) = right(j)
                j += 1
            }
            k+=1
        }
        while(i < nl) {
            brr(k) = left(i)
            i += 1
            k += 1
        }
        while(j < nr) {
            brr(k) = right(j)
            j += 1
            k += 1
        }
        brr
    }
}

我打印了将主数组拆分为多个较小数组的语句。 println("Left: " + left.mkString(", ") & println("right: "+ right.mkString(", "))

的输出

Left: 2, 4, 1, 6
right: 8, 5, 3, 7
Left: 2, 4
right: 1, 6
Left: 2
right: 4
Left: 1
right: 6
Left: 8, 5
right: 3, 7
Left: 8
right: 5
Left: 3
right: 7

拆分机制按预期工作，但最终输出未排序，因为它以与输入数组相同的顺序打印元素：arr = Array[Int](2,4,1,6,8,5,3,7) 代码首先在 brr(k) = left(i) 行给出 ArrayOutOfBoundException 所以我将 brr 的长度初始化为 var brr = new Array[Int](arr.length) 我无法追踪为什么输出没有被排序？如果我错过处理任何案件，谁能告诉我？

Answer 1

问题出在您的 merge 方法中 - 此处您创建了一个临时数组 brr，您使用 left 和 right 值进行了设置。但是，这个 brr 没有在方法 returns 之后的任何地方使用。相反，您应该只使用传递给此方法的原始数组 arr，以便它使用排序后的值进行更新。因此，代码应如下所示：

...
def merge(left: Array[Int], right: Array[Int], arr: Array[Int]):Array[Int] = {
    val nl  = left.length
    val nr  = right.length
    var (i:Int,j:Int,k:Int) = (0,0,0)
    while(i < nl && j < nr) {
        if(left(i) < right(j)) {
            arr(k) = left(i)
            i += 1
        }
        else {
            arr(k) = right(j)
            j += 1
        }
        k+=1
    }
    while(i < nl) {
        arr(k) = left(i)
        i += 1
        k += 1
    }
    while(j < nr) {
        arr(k) = right(j)
        j += 1
        k += 1
    }
    arr
}
...

输出

Left: 2, 4, 1, 6
right: 8, 5, 3, 7
Left: 2, 4
right: 1, 6
Left: 2
right: 4
Left: 1
right: 6
Left: 8, 5
right: 3, 7
Left: 8
right: 5
Left: 3
right: 7
1
2
3
4
5
6
7
8

拆分集合后如何在合并排序中应用合并逻辑？

How to apply merge logic in merge sort after splitting a collection?

algorithm

mergesort

scala