ArrayIndexOutOfBoundsException異常的快速排序實現

我嘗試快速排序的實現，但得到的ArrayIndexOutOfBoundsException異常的快速排序實現

Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: -1 
at com.JavaReference.QuickSort.swap(QuickSort.java:50) 
at com.JavaReference.QuickSort.randPartition(QuickSort.java:20) 
at com.JavaReference.QuickSort.randSort(QuickSort.java:12) 
at com.JavaReference.QuickSort.randSort(QuickSort.java:13) 
at com.JavaReference.QuickSort.randSort(QuickSort.java:13) 
at com.JavaReference.QuickSort.randSort(QuickSort.java:13) 
at com.JavaReference.QuickSort.randSort(QuickSort.java:13) 
at com.JavaReference.QuickSort.randSort(QuickSort.java:8) 
at com.JavaReference.QuickSort.main(QuickSort.java:59)

這裏是我的源代碼[here.]

我是個新手，編程等在那裏，我要去不對任何意見將是讚賞。

編輯：添加整個堆棧跟蹤

來源

2012-04-03 KodeSeeker

請發送完整的堆棧跟蹤。 – 2012-04-03 07:23:12

@PéterTörök：增加了整個堆棧跟蹤。 – KodeSeeker 2012-04-03 07:26:12

我會在紙上寫入輸入數據，然後嘗試按照您編寫的代碼手工排序。它應該有助於確定問題所在。 – Carlo 2012-04-03 07:27:26

~~我懷疑是線路30：~~

int i =left-1;

由於left最初是0，i將成爲-1。然後在線35上撥打

swap(a,i,j);

~~和砰。~~

好的，從堆棧跟蹤看來，我的第一個猜測是錯誤的。

第二次猜測：從堆棧跟蹤中可以看出數組被分區了4次，然後在第五次嘗試時出現異常。它扔到線50：

int temp= array[a];

a是swap第一個參數。上20行至swap呼叫是

swap(a,right,randPivot);

從而right是-1在該點處。該值來自這裏（13號線）：

randSort(a,left,pivot-1);

如果pivot在這一點上是0，還是發生了。並且它可以變爲0，因爲它被視爲left和right之間的隨機值。（實際上，這是一個錯誤，至於有效的分區，應該在left和right之間落入，非包含）。目前，pivot變爲0的概率隨着最左邊的分區變小而增加。您需要爲此引入一個檢查（或者更一般地說，檢測大小爲1的數組分區，這些數據分區不能進一步分區），以及時停止遞歸。

來源

2012-04-03 07:27:20

您的回答讓我以正確的視角看待代碼，謝謝！ :) – KodeSeeker 2012-04-03 09:37:51

您正在嘗試訪問索引爲-1的數組元素。這總是拋出一個異常。檢查索引（a> = 0）。

來源

2012-04-03 07:34:27 santoine

只是一個提示。此功能：

public static void randSort(int a[],int left,int right)

導致無限遞歸（它會自動永久）。在某些時候，您將調用swap，參數left = 0和right = -1（因爲randPartition在某個點返回0）。

來源

2012-04-03 07:41:43

我認爲它是沒有意義的，讓主軸是左或正確。這是因爲樞軸應該用於分離待分類的兩部分（分而治之）。爲了最有效率，兩個部分的大小應該相等。

因此，如果左和正確不同只有一個，你應該無論如何結束遞歸。

來源

2012-04-03 07:44:59

java.lang.ArrayIndexOutOfBoundsException：-1總是告訴你你試圖在一個不存在於這個數組中的索引處調用一個數組。這裏的值（嘗試做System.out.println（a），它會告訴你a）的值變成一次執行-1。因此，您嘗試調用導致異常的數組[-1]，因爲數組從0開始索引。您需要更改算法，以便只能使用值int [] array調用方法交換，值介於0和array.length-1，數值介於0和array.length

來源

2012-04-03 07:51:42 Franz

好夥計，這是我的壞早些時候，身份證錯過了一個關鍵

\\\Other code 
if(left<right){ 
    int pivot=randPartition(a,left,right);// testing purposes 

    randSort(a,left,pivot-1);........ 
...

在randSort（）函數

，我想這是使權利消極。爲所有的噪音而忍受。

來源

2012-04-03 09:07:07 KodeSeeker

ArrayIndexOutOfBoundsException異常的快速排序實現

回答

相關問題