快速排序方法arrayOutofBounds異常

Question

我想獲得一個快速排序方法來排序一些或部分數據。我認爲我的分區方法是正確的，我的遞歸調用快速排列左邊的段和右邊的段給了我一個數組越界的例外，但我似乎無法弄清楚。這裏是我寫的代碼，並正在錯誤的

private void quickSorter(String[] data, int firstIndex, int numberToSort) { 
    if (numberToSort > 1) { 
     int pivot = partition(data, firstIndex, numberToSort); 
     int right = firstIndex + numberToSort -1; 
     if (firstIndex < pivot -1) 
     quickSorter(data, firstIndex, pivot -1); 
     if (pivot < right && right <data.length) 
     quickSorter(data, pivot , right); 
    } 
} 
private void swap(String[] data ,int tooBigNdx, int tooSmallNdx) { 
    String temp = data[tooBigNdx]; 
    data[tooBigNdx] = data[tooSmallNdx]; 
    data[tooSmallNdx] = temp; 

} 

@Override 
public int partition(String[] data, int firstIndex, int numberToPartition) { 
    int ndx = firstIndex; 
    String pivot = data[ndx]; 
    int tooBigNdx = ndx; 
    int tooSmallNdx = firstIndex + numberToPartition -1; 
    while (tooBigNdx < tooSmallNdx) { 
    while (tooBigNdx < tooSmallNdx && (data[tooBigNdx].compareTo(pivot) < 0 || data[tooBigNdx].equals(pivot))) 
     tooBigNdx++; 

    while (tooSmallNdx > ndx && (data[tooSmallNdx].compareTo(pivot) > 0 || data[tooSmallNdx].equals(pivot))) 
     tooSmallNdx--; 
    if (tooBigNdx < tooSmallNdx) { 
     swap(data, tooBigNdx,tooSmallNdx); 
    tooBigNdx++; 
    tooSmallNdx--; 
    } 
    } 
    if (pivot.compareTo(data[tooSmallNdx]) > 0 || pivot.equals(data[tooSmallNdx])) { 
    swap(data, ndx,tooSmallNdx); 
    return tooSmallNdx; 
    } else return ndx; 


} 

編輯：

測試數據集是隨機生成的，每次和5個字母的單詞。我總是得到一個arrayoutofBounds異常，但它的數量越界越大，這取決於數據集。

java.lang.ArrayIndexOutOfBoundsException: -1 
    at sortcomparison.BasicSorter.partition(BasicSorter.java:62) 
    at sortcomparison.BasicSorter.quickSorter(BasicSorter.java:37) 
    at sortcomparison.BasicSorter.quickSorter(BasicSorter.java:40) 
    at sortcomparison.BasicSorter.quickSorter(BasicSorter.java:40) 
    at sortcomparison.BasicSorter.quickSorter(BasicSorter.java:40) 
    at sortcomparison.BasicSorter.quickSort(BasicSorter.java:31) 
    at sbccunittest.BasicSorterTester.standardSortTest(BasicSorterTester.java:166) 
    at sbccunittest.BasicSorterTester.testQuickSort(BasicSorterTester.java:56) 
    at sun.reflect.NativeMethodAccessorImpl.invoke0(Native Method) 
    at sun.reflect.NativeMethodAccessorImpl.invoke(Unknown Source) 
    at sun.reflect.DelegatingMethodAccessorImpl.invoke(Unknown Source) 
    at java.lang.reflect.Method.invoke(Unknown Source) 
    at org.junit.runners.model.FrameworkMethod$1.runReflectiveCall(FrameworkMethod.java:44) 
    at org.junit.internal.runners.model.ReflectiveCallable.run(ReflectiveCallable.java:15) 
    at org.junit.runners.model.FrameworkMethod.invokeExplosively(FrameworkMethod.java:41) 
    at org.junit.internal.runners.statements.InvokeMethod.evaluate(InvokeMethod.java:20) 
    at org.junit.internal.runners.statements.RunBefores.evaluate(RunBefores.java:28) 
    at org.junit.internal.runners.statements.RunAfters.evaluate(RunAfters.java:31) 
    at org.junit.runners.ParentRunner.runLeaf(ParentRunner.java:263) 
    at org.junit.runners.BlockJUnit4ClassRunner.runChild(BlockJUnit4ClassRunner.java:69) 
    at org.junit.runners.BlockJUnit4ClassRunner.runChild(BlockJUnit4ClassRunner.java:48) 
    at org.junit.runners.ParentRunner$3.run(ParentRunner.java:231) 
    at org.junit.runners.ParentRunner$1.schedule(ParentRunner.java:60) 
    at org.junit.runners.ParentRunner.runChildren(ParentRunner.java:229) 
    at org.junit.runners.ParentRunner.access$000(ParentRunner.java:50) 
    at org.junit.runners.ParentRunner$2.evaluate(ParentRunner.java:222) 
    at org.junit.runners.ParentRunner.run(ParentRunner.java:292) 
    at org.eclipse.jdt.internal.junit4.runner.JUnit4TestReference.run(JUnit4TestReference.java:50) 
    at org.eclipse.jdt.internal.junit.runner.TestExecution.run(TestExecution.java:38) 
    at org.eclipse.jdt.internal.junit.runner.RemoteTestRunner.runTests(RemoteTestRunner.java:467) 
    at org.eclipse.jdt.internal.junit.runner.RemoteTestRunner.runTests(RemoteTestRunner.java:683) 
    at org.eclipse.jdt.internal.junit.runner.RemoteTestRunner.run(RemoteTestRunner.java:390) 
    at org.eclipse.jdt.internal.junit.runner.RemoteTestRunner.main(RemoteTestRunner.java:197) 

Answer 1

不應該

int right = firstIndex + numberToSort -1; 

是

int right = firstIndex + numberToSort - 1 - pivot; 

記住，第二個參數是不是一個指數，它是一個計數。

你另一種選擇是將其更改爲一個索引號（我覺得會更直觀。）

Answer 2

我覺得你的問題是運算符優先級在while循環&& , ||

之間與解決插入語。

對於第二個問題，我想在第三，而替換：

while (tooSmallNdx > ndx && (data[tooSmallNdx].compareTo(pivot) > 0 || data[tooSmallNdx].equals(pivot))) 

有了：

while (tooSmallNdx > ndx && data[tooSmallNdx].compareTo(pivot) > 0)