在某些情況下

-1

快速排序不工作當我測試我的快速排序我注意到另一個問題。有時它按字母順序排列數組，有時它不會。例如，如果我有p, o, j, l作爲我的陣列，它將它排序爲j, o, l, p，這是錯誤的，因爲l應該在o之前。但是，如果我將a添加到陣列，它排序爲a, j, l, o, p這是正確的。這是爲什麼發生？在某些情況下

代碼：

private ArrayList<String> sort(ArrayList<String> ar, int lo, int hi){ 
     if (lo < hi){ 
      int splitPoint = partition(ar, lo, hi); 
      sort(ar, lo, splitPoint); 
      sort(ar, splitPoint +1, hi); 
     } 
     return ar; 
    } 

    private int partition(ArrayList<String> ar, int lo, int hi){ 
     String pivot = ar.get(lo); 
     lo--; 
     hi++; 
     while (true){ 
      lo++; 
      hi--; 
      while (lo<hi && ar.get(lo).compareTo(pivot) < 0){ 
       lo++; 
      } 
      while (hi>lo && ar.get(hi).compareTo(pivot) >= 0){ 
       hi--; 
      } 
      if (lo<hi){ 
       swap(ar, lo, hi); 
      }else { 
       return hi; 
      } 
     } 
    } 

    private ArrayList<String> swap(ArrayList<String> ar, int a, int b){ 
     String temp = ar.get(a); 
     ar.set(a, ar.get(b)); 
     ar.set(b, temp); 
     return ar; 
    }

來源

2014-02-08 Cristian Gutu

據我所看到的，你不改變主元的位置。你只是交換你好。

最後，您應該將樞軸放在正確的位置，然後將其返回。

來源

2014-02-08 16:52:11

我一直比較和交換，而'LO

據我瞭解，最初lo == pivot。因此，arr [lo]與arr [pivot]的第一次比較應爲零，並且lo將遞增。樞軸應保持在其位置。 –

正確。但我不移動關鍵點，我只是重新排列這些值。奇怪的是它在除了這個之外的其他所有情況下都有效。 –

我認爲在循環的最後一次迭代中存在危險。

假設你有一個數組2,1。

你的樞軸爲2

所述LO指數增加，直到它找到的1的樞軸上方的元件或滿足喜。在這種情況下，將滿足HI和LO都和高保真將指向1

在這一點上你的分區函數返回，並報告陣列已經被劃分爲：

{2},{1}

但是，這是不正確，因爲1是<比樞軸所以應該在第一個分區。

也許當你遇到嗨，你應該執行一個額外的測試，以查看hi中的元素是否應該包含在左邊或右邊的分區中？

來源

2014-02-08 17:42:12

在某些情況下

回答

相關問題