我正在寫一個課題，是要丟入範圍很大，數字也很大的數值陣列
然後用各種排序方法來計算其排序所需要的時間
範圍是10^2到10^6
要用一千組數字的排序時間總合再除以一千取平均值
因為程式碼都有，所以我問題不是在於程式碼的寫法
而是在於其中一個QuickSort上
我設定一個數字k表示目前運算範圍為10的k次方
當k是2到3時，都可以正常的印出結果，排序出來也是正確的
但是在k等於4時，卻老是會卡在9523的這個數字上
然後就會出現
類型 'System.StackOverflowException' 的未處理例外狀況發生於 AHW1.exe
這一個錯誤訊息，程式無法繼續執行
說明上是要我檢查是否造成了無限迴圈或是無限遞迴
但是我很確定並沒有，因為當數字為一千時就可以正常排序一千次不出錯
只有在大於一萬時跑出這個錯誤
我確認過結束條件，很肯定結束條件是一定會發生的
(原本的QuickSort是有可能會無限遞迴，不過我修改過了)
我想可能畢竟還是遞迴太多次把堆疊占滿了
可是這樣一來我就沒辦法執行出我要的成果了
才一萬而已就超過，我的目標可是一百萬耶...
附上QuickSort的程式部分
Public Sub Quicksort(ByRef a() As Long, ByVal l As Long, ByVal r As Long)
If l < r Then
Dim s As Long
s = Partitions(a, l, r)
Quicksort(a, l, s - 1)
Quicksort(a, s + 1, r)
End If
End Sub
Public Function Partitions(ByRef a() As Long, ByVal l As Long, ByVal r As
Long) As Long
Dim p, i, j, temp As Long
p = a(l)
i = l
j = r + 1
Do
Do
i = i + 1
Loop Until a(i) >= p Or i = r
Do
j = j - 1
Loop Until a(j) <= p Or j = l
temp = a(i)
a(i) = a(j)
a(j) = temp
Loop Until (i >= j)
temp = a(i)
a(i) = a(j)
a(j) = temp
temp = a(l)
a(l) = a(j)
a(j) = temp
Return j
End Function
都是照著書本上的虛擬碼來打的(確認過功能性了)
(後面看似重複的部分，是我懶得去弄swap交換的偷懶寫法就是了)
用到Long是因為(理想中)數字高達一百萬的緣故
卡住的地方是在partition部分，當i=9523時出現的
(連跑兩次都是在同一個數字出錯)
請問，遇到這樣的問題，我有什麼方法能夠解決它呢？
--
其實我寫的MergeSort雖然也是用遞迴，但是就沒有出現這個錯誤訊息
只是，排序出來的結果根本就不對，明明都照著書本打了的說...
後來就不管它了，當作沒看到，只算它的時間就好了....
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 122.126.49.7
※ 編輯: Peruheru 來自: 122.126.49.7 (11/30 03:22)