合并排序的 Visual Basic 实现产生混有 0 的结果

Question

我正在尝试通过控制台应用程序在 Visual Basic 中实现基本的合并排序算法。我认为下面的代码注释得很好，足以解释我是如何尝试解决问题的。我的问题是在我的第一个 merge() 之后，我的整数数组中添加了一个零。该数组已正确排序，但我需要帮助找出零的来源。感谢任何帮助。

Module Module1

Sub Main()
    'Keep console open until Escape key is pressed
    Do Until (Console.ReadKey.Key = ConsoleKey.Escape)
        Console.WriteLine("Please enter the length of the array to be sorted")

        Dim input = Console.ReadLine()
        Dim inputLength As Integer
        inputLength = CInt(input)
        Dim array(inputLength) As Integer

        ' Initialize the random-number generator.
        Randomize()

        For index As Integer = 0 To inputLength - 1
            ' Generate random value between 1 and 5000. 
            array(index) = CInt(Int((5000 * Rnd()) + 1))
        Next

        Console.WriteLine("The unsorted array is: ")
        'Write the randomnly filled array
        For index2 As Integer = 0 To inputLength - 1
            Console.Write(array(index2) & " ")
        Next
        'Print dashed line
        Console.WriteLine("------------------------------------------------------")

        MergeSort(array, 0, array.Length - 1)
    Loop

End Sub


Sub MergeSort(ByVal array() As Integer, lowIndex As Integer, highIndex As Integer)

    If (lowIndex < highIndex) Then
        Dim midIndex = Math.Floor((lowIndex + highIndex) / 2)    'ensure that we get integer result i.e. 5/2 yields 2
        'Recursively break apart original array until the tree bottoms out
        MergeSort(array, lowIndex, midIndex)
        MergeSort(array, midIndex + 1, highIndex)
        'Then merge our single element arrays
        Merge(array, lowIndex, midIndex, highIndex)
    End If

End Sub

Sub Merge(ByVal array() As Integer, lowIndex As Integer, midIndex As Integer, highIndex As Integer)
    'creating 2 sub arrays for left hand and right hand part of merge

    Dim n1 = midIndex - lowIndex + 1
    Dim n2 = highIndex - midIndex

    Dim L(n1) As Integer
    Dim R(n2) As Integer

    'creating index variable to keep track of final answer
    Dim k As Integer = lowIndex

    Dim counterI = 0
    Dim counterJ = 0
    'Fill each of the two arrays declared

    While (counterI < n1)
        L(counterI) = array(lowIndex + counterI)
        counterI = counterI + 1
    End While


    While (counterJ < n2)
        R(counterJ) = array(midIndex + 1 + counterJ)
        counterJ = counterJ + 1
    End While

    'Reset index variables
    k = lowIndex
    Dim i As Integer = 0
    Dim j As Integer = 0

    'Go through and compare the two subarrays and fill index k of our answer
    'with the lower value until one of the subarrays is empty
    While (i < n1 And j < n2)

        If (L(i) <= R(j)) Then
            array(k) = L(i)
            i = i + 1
        Else
            array(k) = R(j)
            j = j + 1
        End If
        k = k + 1
    End While

    'If one array is empty we go ahead and fill our answer with remaining array
    'this removes the sentinels from example (I was struggling with index bounds)

    While (i < n1)
        array(k) = L(i)
        i = i + 1
        k = k + 1
    End While

    While (j < n2)
        array(k) = R(j)
        j = j + 1
        k = k + 1
    End While

    'Print our answer
    Console.WriteLine("The sorted array using Merge Sort is: ")
    For index2 As Integer = 0 To array.Length - 1
        Console.Write(array(index2) & " ")
    Next
End Sub

模块结束

Answer 1

inputLength比array.Length少一。当你初始化数组并写入它的初始值时，你从 0 到 inputLength - 1。当你编写排序数组时，你从 0 到 array.Length - 1，它输出数组的一个额外成员。它为零，因为它未初始化。

合并排序的 Visual Basic 实现产生混有 0 的结果

Visual Basic Implementation of Merge Sort yields result with 0 Mixed In

vb.net

algorithm

sorting

mergesort