如何更改我的下列快速排序代碼，以便我可以使用隨機數據透視表？

-1

如何更改我的以下快速排序代碼，以便我可以使用隨機數據透視而不是中間整數透視？如何更改我的下列快速排序代碼，以便我可以使用隨機數據透視表？

public ArrayList<Integer> quicksort(ArrayList<Integer> input){ 

    if(input.size() <= 1){ 
     return input; 
    } 

    int middle = (int) Math.ceil((double)input.size()/2); 

    ##int randomint= arrayList.get(random.nextInt(arrayList.size()));## 
    ##I WANT TO USE THIS RANDOMINT AS A PIVOT## 

    int pivot = input.get(middle); 

    ArrayList<Integer> less = new ArrayList<Integer>(); 
    ArrayList<Integer> greater = new ArrayList<Integer>(); 

    for (int i = 0; i < input.size(); i++) { 
     if(input.get(i) <= pivot){ 
      if(i == middle){ 
       continue; 
      } 
      less.add(input.get(i)); 
     } 
     else{ 
      greater.add(input.get(i)); 
     } 
    } 

    return concatenate(quicksort(less), pivot, quicksort(greater)); 
} 

private ArrayList<Integer> concatenate(ArrayList<Integer> less, int pivot, ArrayList<Integer> greater){ 

    ArrayList<Integer> list = new ArrayList<Integer>(); 

    for (int i = 0; i < less.size(); i++) { 
     list.add(less.get(i)); 
    } 

    list.add(pivot); 

    for (int i = 0; i < greater.size(); i++) { 
     list.add(greater.get(i)); 
    } 

    return list; 
}

我想用randomint作爲關鍵。當我嘗試直接替換randomint時，我得到數組超出限制的異常。謝謝。

來源

2015-12-02 Riccado

可能的重複[什麼導致java.lang.ArrayIndexOutOfBoundsException，我該如何防止它？]（http://stackoverflow.com/questions/5554734/what-causes-a-java-lang-arrayindexoutofboundsexception-and-我想阻止它） –

我想用這個， – Riccado

你的'randomint'實際上是你的支點。 'ArrayList.get（）'返回'ArrayList'的內容。 –

如果更改下面一行：

int randomint= arrayList.get(random.nextInt(arrayList.size()));

到

int randomint= random.nextInt(input.size()); 
int pivot = input.get(randomint);

如果我的懷疑是正確的，這應該給你你正在尋找的隨機擺動。

來源

2015-12-02 15:03:42

是的，它解決了。謝啦兄弟。 :) – Riccado

如何更改我的下列快速排序代碼，以便我可以使用隨機數據透視表？

回答

相關問題