快速排序分而治之

Question

我正在嘗試執行快速排序使用分而治之技術。我得到的遞歸一個堆棧溢出錯誤調用。這裏是我的代碼：

public static void main(String[] args) { 
    ArrayList<Integer> unsorted = new ArrayList<Integer>(); 

    unsorted.add(23); 
    unsorted.add(5); 
    unsorted.add(1); 
    unsorted.add(-8); 
    unsorted.add(101); 
    unsorted.add(21); 
    unsorted.add(10); 
    unsorted.add(10); 
    unsorted.add(0); 
    unsorted.add(50); 

    ArrayList<Integer> sorted = Quicksort(unsorted); 
    System.out.println(sorted.toString()); 
} 

public static ArrayList<Integer> Quicksort(ArrayList<Integer> unsorted) { 

    if (unsorted.size() <= 1) 
     return unsorted; 

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

    int pivotindex = unsorted.size()/2; 

    for (int i = 0; i < unsorted.size(); i++) { 
     if (unsorted.get(i) < unsorted.get(pivotindex)) 
      less.add(unsorted.get(i)); 
     else 
      more.add(unsorted.get(i)); 
    } 

    ArrayList<Integer> sorted = Quicksort(less); 
    sorted.add(unsorted.get(pivotindex)); 
    sorted.addAll(Quicksort(more)); 

    return sorted; 
} 

我希望它使用ArrayLists來實現。任何人都可以指出我錯在哪裏？

非常感謝。

Answer 1

你應該保持從more和less列出一個單獨的地方你pivot值。

更改條件：

else if(unsorted.get(i) > unsorted.get(pivotindex)) 
     more.add(unsorted.get(i));  

它應該工作的罰款。希望這可以幫助。

編輯：正如在喬希的評論中提到的，如果有多個元素具有與主元相同的值，這將不起作用。對於這一點，你所能做的就是定義一個名爲equal另一個ArrayList和加入這一行：

else 
    equal.add(unsorted.get(i)); 

然後，當你合併陣列後面這份名單與pivot元素一起追加。

感謝您指出了這一點。 :)

注：這種類型將不被保證是穩定（作爲具有可能不按照原來的陣列中的它們的相對位置被放置相同的值的元素）。

Answer 2

這似乎是可以很容易地

ArrayList<Integer> less = new ArrayList<Integer>(); 
ArrayList<Integer> equal = new ArrayList<Integer>(); 
ArrayList<Integer> more = new ArrayList<Integer>(); 

int pivotindex = unsorted.size()/2; 

for (int i = 0; i < unsorted.size(); i++) { 
    if (unsorted.get(i) < unsorted.get(pivotindex)) //Put whatever is less to the left 
     less.add(unsorted.get(i)); 
    else if (unsorted.get(i) == unsorted.get(pivotindex)) //Put whatever is equal in the middle 
     equal.add(unsorted.get(i)); 
    else //Put everything else to the right (everything greater) 
     more.add(unsorted.get(i)); 
} 

ArrayList<Integer> sorted = Quicksort(less); //Sort the left, then add 
sorted.addAll(equal); //Middle is already sorted (all equal), add 
sorted.addAll(Quicksort(more)); //Sort the right, then add 

return sorted; 

Answer 3

以下作品完美地可以理解的解決方案。

public static void main(String[] args) { 
     ArrayList<Integer> unsorted = new ArrayList<Integer>(); 

      unsorted.add(23); 
      unsorted.add(5); 
      unsorted.add(1); 
      unsorted.add(-8); 
      unsorted.add(101); 
      unsorted.add(21); 
      unsorted.add(10); 
      unsorted.add(10); 
      unsorted.add(0); 
      unsorted.add(50); 

      ArrayList<Integer> sorted = Quicksort(unsorted); 
      System.out.println(sorted.toString()); 
     } 

     public static ArrayList<Integer> Quicksort(ArrayList<Integer> unsorted) { 
       System.out.println(unsorted.size()); 
      if (unsorted.size() <= 1) 
       return unsorted; 

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

      int pivotindex = unsorted.size()/2; 

      for (int i = 0; i < unsorted.size(); i++) { 
       if (unsorted.get(i) < unsorted.get(pivotindex)) 
        less.add(unsorted.get(i)); 
       else 
        more.add(unsorted.get(i)); 
      } 
      if(less.isEmpty()) { 
       less.add(more.remove(more.size() - 1)); 
      } 

      ArrayList<Integer> sorted = Quicksort(less); 
      //sorted.add(unsorted.get(pivotindex)); 
      sorted.addAll(Quicksort(more)); 

      return sorted; 
     }