Groovy qSort和Filter實現給出堆棧溢出錯誤

這是在Groovy中的過濾器的實現我正在嘗試使用。Groovy qSort和Filter實現給出堆棧溢出錯誤

def filter(list, p) { 
    if (list.size() == 0) { return list } 
    if (p(list.head())) { 
     [] + list.head() + filter(list.tail(), p) 
    } else { 
     filter(list.tail(), p) 
    } 
}

這是我嘗試使用的快速排序算法的實現。

def qSort(list) { 
    if (list.size() <= 1) { 
     return list 
    } else { 
     def pivot = list[(int)list.size()/2] 
     def sorted = [] 
     sorted += qSort(filter(list, { it < pivot})) 
     sorted += qSort(filter(list, { it == pivot})) 
     sorted += qSort(filter(list, { it > pivot })) 
    } 
}

這是我想排序的列表，相對隨意。

def list = [5, 3, 2, 1, 8, 4, 5, 8, 23, 4, 6, 8, 3, 23, 76, 8, 9, 2, 2, 1, 1, 2]

我收到此錯誤：

Exception in thread "main" java.lang.StackOverflowError 
at java.lang.Math.getExponent(Math.java:1310) 
at java.lang.StrictMath.floorOrCeil(StrictMath.java:355) 
at java.lang.StrictMath.ceil(StrictMath.java:321) 
at java.lang.Math.ceil(Math.java:405) 
at java.math.BigDecimal.divide(BigDecimal.java:1608) 
at org.codehaus.groovy.runtime.typehandling.BigDecimalMath.divideImpl(BigDecimalMath.java:62) 
at org.codehaus.groovy.runtime.typehandling.IntegerMath.divideImpl(IntegerMath.java:46) 
at org.codehaus.groovy.runtime.dgmimpl.NumberNumberDiv$NumberNumber.invoke(NumberNumberDiv.java:320)

來源

2015-01-26 kschmit90

'（INT）（名單.size（）/ 2）'。大小已經是一個整數。或只是'list.size（）>> 1' – cfrick 2015-01-26 22:12:33

更改，不會做任何事情，如果我刪除類型轉換爲int我得到'在線程中的異常「主」groovy.lang.MissingMethodException：沒有方法簽名：java。 util.ArrayList.getAt（）適用於參數類型：（java.math.BigDecimal）values：[11]' – kschmit90 2015-01-26 22:18:48

什麼是groovy版本？在代碼中使用了stackoverflow，但在2.4中沒有使用cast/divide/...問題。 – cfrick 2015-01-26 22:37:57

它得到越陷越深，當你有n號碼（如n > 1），其都等於樞軸的列表。

如果更改：

if (list.size() <= 1) {

要：

if (list.unique(false).size() <= 1) {

它將工作......有可能是一個不太「哈克的感覺」的解決方案，雖然

來源

2015-01-27 11:35:21

簡單而完美的變化。 – Rao 2015-01-29 03:49:35

Groovy qSort和Filter實現給出堆棧溢出錯誤

回答

相關問題