我在 Visual Basic 中实现链表快速排序时遇到了一些困难，问题是经典的堆栈溢出。因为它是一种递归算法，所以我认为它是我所缺少的相当简单的东西，但我已经盯着它看了好几个小时，在纸上追踪它——它只能处理三个或更少的项目，有时是四个。任何帮助将非常感激。
我遵循的算法是
- 从列表中选择一个元素，称为枢轴。
- 重新排序列表，使所有值小于枢轴的元素都在枢轴之前，而所有值大于枢轴的元素都在它之后（相等的值可以去任何一种方式）。在此分区之后，枢轴处于其最终位置。这称为分区操作。
- 递归地将上述步骤应用于具有较小值的元素的子列表和具有较大值的元素的子列表。
变量“countABC”保存列表中的项目数。
这是节点类的代码：
Public Class Node
'Each node contains the values for one value and is stored
'in the dynamic linked list.
Public Name As String
Public NextNode As Node
Public PKey As Integer
Public Sub New()
'Initializes a new node
Name = ""
NextNode = Nothing
PKey = 0
End Sub
End Class
Public start As Node
Public Sub New()
'Initializes a new linked list by setting start as the first node
start = New Node
End Sub
对于添加例程：
Public Sub AddABC(ByVal Name As String, ByVal PKey As Integer)
'Adds items to a dynamic linked list ordered in alphabetical order
Dim NewNode As New Node
Dim ptr As Node = start.NextNode
Dim prev As Node = start
NewNode.PKey = PKey
While ptr IsNot Nothing AndAlso ptr.Name < NewNode.Name
prev = ptr
ptr = ptr.NextNode
End While
NewNode.Name = Name
NewNode.NextNode = ptr
prev.NextNode = NewNode
countABC += 1
End Sub
以及排序所需的两个函数（连接列表用于连接）
Public Function SortAlphabetically() As AllColumns
'This is a quicksort routine that creates a new linked list
'(that is not saved) in alphabetical order
If countABC > 1 Then
Dim pivotPkey As Integer = Math.Ceiling(countABC / 2)
Dim pivot As New Node
Dim ptr As Node = start.NextNode
While ptr IsNot Nothing
If ptr.PKey = pivotPkey Then
pivot = ptr
End If
ptr = ptr.NextNode
End While
Dim lower As New AllColumns
Dim higher As New AllColumns
ptr = start.NextNode
While ptr IsNot Nothing
If ptr.Name < pivot.Name Then
lower.AddABC(ptr.Name, ptr.PKey)
Else
higher.AddABC(ptr.Name, ptr.PKey)
End If
ptr = ptr.NextNode
End While
Return (Joinlists(lower.SortAlphabetically, pivot,
higher.SortAlphabetically))
Else
Return Me
End If
End Function
Private Function Joinlists(ByVal lower As AllColumns,
ByVal pivot As Node,
ByVal higher As AllColumns) As AllColumns
'Joins two dynamic linked lists together with a pivot value
'separating them
Dim list As AllColumns = lower
list.AddABC(pivot.Name, pivot.PKey)
Dim ptr As Node = higher.start.NextNode
While ptr IsNot Nothing
list.AddABC(ptr.Name, ptr.PKey)
ptr = ptr.NextNode
End While
Return list
End Function
感谢阅读，我希望我已经很好地解释了这个问题并且没有遗漏任何东西（这是可能的，因为它是一个更大的程序的一部分）。
编辑
这是完整的类定义和第一个子类，希望能更好地解释它：
Public Class AllColumns
Public countABC As Integer = 0
Public Class Node
'Each node contains the values for one value and is stored in the dynamic linked list.
Public Name As String
Public NextNode As Node
Public PKey As Integer
Public Sub New()
'Initialises a new node
Name = ""
NextNode = Nothing
PKey = 0
End Sub
End Class
Public start As Node
Public Sub New()
'Initialises a new linked list by setting start as the first node
start = New Node
countABC = 0
End Sub
是不是越来越低被声明为“New Allcolumns”，它们将有自己的 countABC 值，当节点放入列表时会增加？
我不认为例程是导航到枢轴然后对它之后的所有值进行排序，例程的这一部分是实际的排序，并且“ptr”设置为“start.nextnode”即。事先在列表中的第一项。
ptr = start.NextNode
While ptr IsNot Nothing
If ptr.Name < pivot.Name Then
lower.AddABC(ptr.Name, ptr.PKey)
Else
higher.AddABC(ptr.Name, ptr.PKey)
End If
ptr = ptr.NextNode
End While
Return (Joinlists(lower.SortAlphabetically, pivot,
higher.SortAlphabetically))
一开始我应该说得更清楚，道歉。