QuickSort中的StackOverflowException

Question

我需要使用快速排序来订购一些非常大的列表（数千个项目）。但是，当我尝试这个我得到异常System.StackOverflowException。

从一些快速的谷歌搜索我知道这是要么从一个非常大的列表，但我已经排除了这种可能性通过使用一个小列表上的函数）或从一个子程序递归调用递归无限。尽管当我删除一个子程序Swap（）的调用时，下面的代码确实使用递归，但是异常停止发生，尽管Swap（）实际上没有调用任何其他子例程。

任何人都可以发现任何错误的代码？这是我第一次使用递归。

#Region "QuickSort" 
    'Subroutine for QuickSort, called upon recursively until list is sorted' 
    Private Sub QuickSort(ByRef list(,) As Integer, ByVal min As Integer, ByVal max As Integer) 'min is index of first term, max is index of last term' 
     If min < max Then 'Checks if list is sorted' 
      Dim pivotLoc = Partition(list, min, max) 'Gets the next pivot position' 
      QuickSort(list, min, pivotLoc) 'Sorts the two new sublists' 
      QuickSort(list, pivotLoc + 1, max) 
     End If 
    End Sub 

    Private Function Partition(ByRef list(,) As Integer, ByVal min As Integer, ByVal max As Integer) As Integer 
     Dim pivot = list(min, 0) 'Initially sets the pivot to be the minimum value in the list' 
     Dim leftWall = min 

     For i As Integer = min + 1 To max 'For each item in sublist' 
      If list(i, 0) < pivot Then 'If current item is less than the pivot swap it onto other side of pivot' 
       Swap(list, i, leftWall) 
       leftWall += 1 'Increment leftWall' 
      End If 
     Next 

     Swap(list, min, leftWall) 'When this line exists System.StackOverflowException occurs' 
     Return leftWall 
    End Function 

    'Subroutine that swaps values in list around using temporary storage variables' 
    Private Sub Swap(ByRef list(,) As Integer, ByVal x As Integer, ByVal y As Integer) 
     Dim tempVal = list(x, 0) 
     Dim tempIndex = list(x, 1) 

     list(x, 0) = list(y, 0) 
     list(x, 1) = list(y, 1) 

     list(y, 0) = tempVal 
     list(y, 1) = tempIndex 
    End Sub 
#End Region 

谢谢，亚历克斯。

编辑：如果它可以帮助任何人，这里是我基于它关闭的伪代码：here

Answer 1

这是工作的解决方案：

#Region "QuickSort" 
    'Subroutine for QuickSort, called upon recursively until list is sorted' 
    Private Sub QuickSort(ByRef list(,) As Integer, ByVal min As Integer, ByVal max As Integer) 'min is index of first term, max is index of last term' 
     If min < max Then 'Checks if list is sorted' 
      Dim pivotLoc = Partition(list, min, max) 'Gets the next pivot position' 
      QuickSort(list, min, pivotLoc) 'Sorts the two new sublists' 
      QuickSort(list, pivotLoc + 1, max) 
     End If 
    End Sub 

    Private Function Partition(ByRef list(,) As Integer, ByVal min As Integer, ByVal max As Integer) As Integer 
     Dim pivot = list(min, 0) 'Initially sets the pivot to be the minimum value in the list' 
     Dim pivotIndex = list(min, 1) 
     Dim leftWall = min 

     For i As Integer = min + 1 To max 'For each item in sublist' 
      If list(i, 0) < pivot Then 'If current item is less than the pivot swap it onto other side of pivot' 
       Swap(list, i, leftWall) 
       leftWall += 1 'Increment leftWall' 
      End If 
     Next 

     'Swap(list, min, leftWall) 'When this line exists System.StackOverflowException occurs' 

     'Instead do this' 
     list(leftWall, 0) = pivot 
     list(leftWall, 1) = pivotIndex 

     Return leftWall 
    End Function 

    'Subroutine that swaps values in list around using temporary storage variables' 
    Private Sub Swap(ByRef list(,) As Integer, ByVal x As Integer, ByVal y As Integer) 
     Dim tempVal = list(x, 0) 
     Dim tempIndex = list(x, 1) 

     list(x, 0) = list(y, 0) 
     list(x, 1) = list(y, 1) 

     list(y, 0) = tempVal 
     list(y, 1) = tempIndex 
    End Sub 
#End Region