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