合并排序堆栈溢出 vb.net

Question

在我的项目中，我想对我的项目 class 之一的列表进行合并排序：

首先，我为这个class

做了比较运算符

Public Class Programme

    Private DateLimite As Date


    Public Shared Operator >(ByVal p1 As Programme, ByVal p2 As Programme) As Boolean
         Return p1.acces_DateLimite > p2.acces_DateLimite
    End Operator

    Public Shared Operator <(ByVal p1 As Programme, ByVal p2 As Programme) As Boolean
         Return p1.acces_DateLimite < p2.acces_DateLimite
    End Operator

    Public Shared Operator >=(ByVal p1 As Programme, ByVal p2 As Programme) As Boolean
         Return p1.acces_DateLimite >= p2.acces_DateLimite
    End Operator

    Public Shared Operator <=(ByVal p1 As Programme, ByVal p2 As Programme) As Boolean
         Return p1.acces_DateLimite <= p2.acces_DateLimite
    End Operator

End Class

之后，我做了归并排序算法

Public Function InsertListe(element As Programme, sequence As List(Of Programme)) As List(Of Programme)
    Dim list = New List(Of Programme)
    If sequence.Count = 0 Then
        list.Add(element)
        Return list
    ElseIf element <= sequence.First Then
        sequence.Insert(0, element)
        Return sequence
    Else
        list.Add(sequence(0))
        list.AddRange(InsertListe(element, sequence.GetRange(1, sequence.Count - 1)))
        Return list
    End If
End Function


Public Function Merge(subSeq1 As List(Of Programme), subSeq2 As List(Of Programme)) As List(Of Programme)
    If subSeq1.Count = 0 Then
        Return subSeq2
    ElseIf subSeq2.Count = 0 Then
        Return subSeq1
    Else
        Return Merge(subSeq1.GetRange(1, subSeq1.Count - 1), InsertListe(subSeq1(0), subSeq2))
    End If
End Function


Public Function MergeSort(sequence As List(Of Programme)) As List(Of Programme)
    Dim n = sequence.Count
    If n = 0 Or n = 1 Then
        Return sequence
    Else
        Return Merge(MergeSort(sequence.GetRange(0, (n + 1) / 2)), _
                     MergeSort(sequence.GetRange((n + 1) / 2, n - ((n + 1) / 2))))
    End If
End Function

但是当我在 'List(Of Programme)' 上调用它时，会抛出 WhosebugException 我找不到原因。我正在查看调用堆栈，即使 n 大于 1，也只会调用 ''MergeSort'' 函数。

提前致谢。

Answer 1

将 Programme class 替换为 UInteger（只是普通数据类型的一个示例）和细微的样式调整后，一切都对我有用：

Public Shared Sub Test()
    Dim oPRNG As New Random
    For ndxTrial As Integer = 1 To 10
        Console.Out.WriteLine("Trial # {0}", ndxTrial)
        Dim nItems As Integer = oPRNG.Next(5, 25)
        Dim auValues As New List(Of UInteger)(nItems)
        For ndxItem As Integer = 0 To nItems - 1
            auValues.Add(CUInt(oPRNG.Next(0, 100)))
        Next
        Console.Out.WriteLine("Random: {0}", FormatList(auValues))
        Console.Out.WriteLine("Sorted: {0}", FormatList(MergeSort(auValues)))
        Console.Out.WriteLine()
    Next
End Sub

Public Shared Function FormatList(ByVal auValues As List(Of UInteger)) As String
    Return String.Format("{{ {0} }}", String.Join(", ", auValues))
End Function

Public Shared Function InsertListe(element As UInteger, sequence As List(Of UInteger)) As List(Of UInteger)
    Dim list As New List(Of UInteger)
    If sequence.Count = 0 Then
        list.Add(element)
        Return list
    ElseIf element <= sequence.First Then
        sequence.Insert(0, element)
        Return sequence
    Else
        list.Add(sequence(0))
        list.AddRange(InsertListe(element, sequence.GetRange(1, sequence.Count - 1)))
        Return list
    End If
End Function


Public Shared Function Merge(subSeq1 As List(Of UInteger), subSeq2 As List(Of UInteger)) As List(Of UInteger)
    If subSeq1.Count = 0 Then
        Return subSeq2
    ElseIf subSeq2.Count = 0 Then
        Return subSeq1
    Else
        Return Merge(subSeq1.GetRange(1, subSeq1.Count - 1), InsertListe(subSeq1(0), subSeq2))
    End If
End Function


Public Shared Function MergeSort(sequence As List(Of UInteger)) As List(Of UInteger)
    Dim n As Integer = sequence.Count
    If n = 0 Or n = 1 Then
        Return sequence
    Else
        Return Merge(MergeSort(sequence.GetRange(0, (n + 1) \ 2)), _
                     MergeSort(sequence.GetRange((n + 1) \ 2, n - ((n + 1) \ 2))))
    End If
End Function

因此，首先要在代码中摆脱那些 浮点数 除法操作——使用 back 斜杠（整数除法）而不是向前：这样你就可以保证正确的四舍五入。

与此相关，还值得注意的是明确您的意图并且永远不要依赖自动类型推导的重要性。而不是

    Dim n = sequence.Count

写入

    Dim n As Integer = sequence.Count

而不是

    Dim list = New List(Of Programme)

写入

    Dim list As New List(Of Programme)

此外，始终在项目属性中启用 Option Strict 和 Option Explicit，并禁用 Option Infer。这将为您节省大量调试神秘错误的时间。

总的来说，我希望这个“项目”只是你的语言学习家庭作业，而不是真正的应用程序，因为选择的算法和选择的容器（.Net 中的 List 只是一个动态重新分配的数组）是次优的超乎想象

合并排序堆栈溢出 vb.net

Merge Sort Stack Overflow vb.net

vb.net

stack-overflow

mergesort