Java中Quicksort的問題

所以我一直在測試不同的排序算法，現在我寫了一個Quicksort！它的作品，但排序有點偏離！幾乎總是我得到這樣的輸出：Java中Quicksort的問題

[0, 1, 2, 3, 8, 6, 5, 4, 7, 9, 20, 16, 22, 21, 14, 17, 18, 10, 15, 19, 13, 11, 23, 12, 26, 24, 25, ...

這是我排序的100中的前27個元素。這就是我如何填寫隨機列表：

for(int i =0; i < 100; i ++){ 
      int nr = rand.nextInt(100); 
      if (!numbers.contains(new Integer(nr))){ 
       numbers.add(nr); 
      }else { 
       i--; 
      } 
}

這裏是快速排序的代碼：

public class Quicksort{ 
@SuppressWarnings("unchecked") 
static public <T> ArrayList<T> sortting(ArrayList<T> t){ 
    //System.out.print("-"); 
    T piv; 
    ArrayList<T> left ,right ,newT; 
    left = new ArrayList<T>(); 
    right = new ArrayList<T>(); 
    newT = new ArrayList<T>(); 

    if (!t.isEmpty()){ 
     piv = t.get(t.size()/2); 
     for (int i =0; i < t.size(); i++){ 
      if (0 < ((Comparable<T>) piv).compareTo(t.get(i))){ //left 
       left.add(t.get(i)); 
      }else{ //right 
       right.add(t.get(i)); 
      } 
     } 

     if (left.isEmpty() || right.isEmpty()){ 
      newT.addAll(left); 
      newT.addAll(right); 
      return newT; 
     }else { 
      right = sortting(right); 
      left = sortting(left); 

      newT.addAll(left); 
      newT.addAll(right); 
     } 

     return newT; 
    } 
    return null; 

} 

}

來源

2013-07-18 Bardia ' Luviz' Jedi

你的問題是與此塊：

if (left.isEmpty() || right.isEmpty()){ 
     newT.addAll(left); 
     newT.addAll(right); 
     return newT; 
    }

如果您選擇在樞軸有些觀點恰好是當前子列表中最小的，然後該子列表會自動被認爲是排序的。您應該刪除該檢查並對左側和右側子列表進行排序。

這是好的，因爲然後你會進入一個空列表的遞歸調用，在這種情況下，你返回null。

if (!t.isEmpty()){ ... return newT;} 
return null;

實際上，我不知道，如果ArrayList.addAll()處理null投入正常。如果你擔心這一點，那麼你可以返回一個空的ArrayList而不是null。

來源

2013-07-18 00:44:29 bdares

但如果我刪除檢查我怎麼知道，當算法需要停止/結束 –

好吧我已經嘗試，但仍然沒有工作順便說一句我已經改變了'返回null'到'返回新ArrayList <>（）;'應該是一個空陣！在常見問題解答中，問題在於右側向一個inf循環中溢出了內存。這意味着我看到右側被迫停止，因爲左側是空的，但前面的右側不會停止！ –

粘性你bdares您輸入您指出了一些無能的部分，幫助配發！但是，這不是問題

的問題是，樞不從MEAS數組中刪除，如果樞軸是最小的元素正確的數組==到t導致無限循環並超載RAM！

例如。

5 ,4 ,8 ,6 ,8 will return 5 ,4 ,8 ,6 ,8

所以爲了解決這個樞軸需要刪除和重新附加在陣列的開始

現在

5 ,4 ,8 ,6 ,8 will return 4 ,5 ,8 ,6 ,8

這裏是源代碼，如果你有興趣，和專家提示：所有的方式確保至少有一個小的變化是思考你的迭代

@SuppressWarnings("unchecked") 
static public <T> ArrayList<T> sortting(ArrayList<T> t){ 

    T piv; 
    ArrayList<T> left ,right ,newT; 
    left = new ArrayList<T>(); 
    right = new ArrayList<T>(); 
    newT = new ArrayList<T>(); 

    if (!t.isEmpty()){ 
     if (t.size()==1){  //Finish check -> one elem is sorted 
      return t; 
     }  
     piv = t.remove(t.size()/2); 
     for (int i =0; i < t.size(); i++){   //sorting 
      if (0 < ((Comparable<T>) piv).compareTo(t.get(i))){ //left 
       left.add(t.get(i)); 
      }else{ //right 
       right.add(t.get(i)); 
      } 
     } 
     right = sortting(right); //sub sorting 
     left = sortting(left); 

     newT.addAll(left);  //building newT 
     newT.add(piv); 
     newT.addAll(right); 
     return newT; 
    } 
    return new ArrayList<>(); 
}

來源

2013-07-18 15:10:53

Java中Quicksort的問題

回答

相關問題