索引出界異常的快速排序泛型

這個名單是我寫到目前爲止代碼：索引出界異常的快速排序泛型

import java.util.Collections; 
import java.util.Random; 
import java.util.List; 

public class Sorter<T extends Comparable<T>> { 
public void sort(List<T> list) { 
    if (list.size() <= 10) { 
     insertionSort(list, 0, list.size()); 
    } else { 
     quickSort(list, 0, list.size() - 1); 
    } 
} 

private void quickSort(List<T> list, int leftIndex, int rightIndex) { 
    int i = leftIndex; 
    int j = rightIndex; 
    if (i >= j) { 
     return; 
    } else if (j - i <= 10) { 
     insertionSort(list, i, j+1); 
     return; 
    } 


    int rand = randomizePivot(j, i); 
    T pivot = list.get(rand); 
    Collections.swap(list, rand, j); 

    while (i < j) { 

     while (!list.get(i).compareTo(pivot) && i < j) { 
      i++; 
     } 


     while (!pivot.compareTo(list.get(j)) && i < j) { 
      j--; 
     } 


     if (i < j) { 
      Collections.swap(list, i, j); 
     } 
    } 

    list.remove(rightIndex); 
    list.add(rightIndex, list.get(j)); 
    list.remove(j); 
    list.add(j, pivot); 

    quickSort(list, leftIndex, i - 1); 
    quickSort(list, j + 1, rightIndex); 
} 

private int randomizePivot(int hi, int lo) { 
    Random rand = new Random(); 
    return rand.nextInt(hi - lo + 1) + lo; 
} 

private void insertionSort(List<T> list, int lo, int hi) { 
    for (int i = lo + 1; i < hi; i++) { 
     int j = i - 1; 
     T elem = list.get(i); 
     while (j >= lo && list.get(j).compareTo(elem)) { 
      list.remove(j + 1); 
      list.add(j + 1, list.get(j)); 
      j--; 
     } 
     list.remove(j + 1); 
     list.add(j + 1, elem); 
    } 
} 

}

它「作品」九OT十名。有時，它給了我拋出IndexOutOfBoundsException在這一行：

 list.add(rightIndex, list.get(j));

這就是支點找到其確切位置的零件。確切的錯誤消息，在25項目的列表是：

Exception in thread "main" java.lang.IndexOutOfBoundsException: Index: 24, Size: 24 
at java.util.LinkedList.checkElementIndex(Unknown Source) 
at java.util.LinkedList.get(Unknown Source)

任何人都可以幫忙嗎？錯誤在哪裏？

來源

2013-11-26 Goet

這隻能發生在rightIndex == j 這裏你刪除最右邊的元素，並在下一步嘗試重新插入它。但j指數然後消失了。

保護它像這樣：

if (rightIndex != j) { 
     list.remove(rightIndex); 
     list.add(rightIndex, list.get(j)); 
}

來源

2013-11-26 15:30:23 Ingo

是的，問題在那裏，正如我在評論回覆中指出的那樣。無論如何，謝謝:) – Goet

@ Goet - 很好有這個固定的。有時純邏輯比調試器更強大。隨時提供有用的答案，它也會增加你自己的聲譽。 – Ingo

不要添加以下行insertionSort(list, i, j+1);

一個最簡單的方法是改變所有的方法，使上限總是獨佔（如quickSort(list, left, right)或insertionSort(list, left, right)將從指數left所有元素進行排序，以right - 1， randomizePivot(lo, hi)將返回範圍從lo到hi - 1等的隨機數）。

這是一個也在java標準庫中使用的約定。

來源

2013-11-26 15:01:11 isnot2bad

......這樣做，不僅是我得到了同樣的信息的錯誤，但是當我不這樣做，列表不會導致有序 – Goet

你必須改變的不僅僅是這一行，因爲你的代碼有時將上限解釋爲包含，有時被排除。通過你所有的代碼並檢查上限！ – isnot2bad

是的，修好了！索引是對的，它只是一個簡單而愚蠢的事情：當rigthIndex等於j時，它首先刪除j元素，然後嘗試添加它！一個簡單的工作:) – Goet

大小爲24的列表（Java數組）不能有索引24，因爲索引將從零開始。這意味着大小爲10的數組將具有索引0到9，而不是1到10.這裏看起來像索引24被請求，而列表僅索引0到23。

來源

2013-11-26 15:05:18

當然你的關於數組索引的概念是正確的:)但是列表不是數組，列表的大小是25，但它並不重要：如果它是49，它會給我錯誤的「索引48，大小48」 – Goet

索引出界異常的快速排序泛型

回答

相關問題